如何选择k为k-匿名？

Question

我已经在谷歌上手工抓取了多页搜索结果，但是当你试图“匿名”你的数据集时，我没有找到一个关于如何找到最优的k的建议。我所能发现的是一个显而易见的事实，即“更高的k=更安全，但更多的信息丢失”，但对于如何解决这个问题，却没有给出一个单一的想法。

一个2的k不就足够了吗？(只要给出至少l=2的L多样性)？或者我们应该高达15，20，30,100？我对这个话题相当陌生，网上的资料没有提供任何直觉。

你知道组织/公司/大学是否有公开提供的指南来讨论k的价值选择？或者其他资源？

Answer 1

适当的隐私级别完全取决于上下文。显然，k=1和k=n通常是无用的(对于n大小的数据集而言)。一个不提供匿名性，另一个不保留任何实用程序(除了非常基本的信息，比如数据集的大小)。但两者之间可能会有有趣的价值。

在这种匿名与实用工具的权衡中，适当的隐私级别可以被限制在任意一个方向上：

• 如果对匿名数据集进行一定的分析，我们能容忍的最大k值是多少？
• 考虑到我们想要的隐私保障，我们要求的最低k是多少？

例如，让我们考虑由“我被抓了吗？”API接口实现的k-匿名模型。要检查您的密码是否被破坏，您可以发送一个截断的密码散列，并返回已泄漏密码的完整散列列表。每个前缀被破坏的密码数对应于k-匿名模型中的隐私级别k。

在这里，k上的上限是通过响应中返回的哈希列表的大小来给出的。为了保持API的效率，这个列表应该尽可能小。一个合理的上限将在千字节范围内的某个地方，表示k<2000。通过隐私/安全要求给出了一个下限。给定已知的已泄漏密码，API和任何窃听者都不应该能够可靠地确定被截断的哈希发送到了哪个已泄露的密码。没有明确的安全下限，因为任何查询都必然会泄漏一些信息。然而，k<10显然是不安全的，k<100可能仍然允许恶意API提供程序以相当好的概率猜出真正的密码。这就留下了一个范围为100≤k≤2000，可以适用于此用例。

实际上，HIPB使用k-1500 [C7，2]级别，尽管有额外的填充以防止进一步的信息泄漏。

这是一个很高的k-匿名水平，动机是相当严重的安全影响泄漏密码。在其他情况下，低得多的k是合适的。例如，基本人口统计数据的敏感性要低得多，而且可能在5≤k≤20左右的适当水平。在许多领域，由于可用数据集的规模较小，隐含地需要一个较低的k值--唯一合理的选择是根本不披露过于敏感的数据。

应该指出的是，k -匿名和相关方法本身并不能在任何k个方面实现非常强的隐私保障，而且所需的数据编辑或抽象对许多用途都是有害的。在某些情况下，采用概率方法(如差别隐私)可能更合适。