问在不泄露来源的情况下比较秘密数据

EN

首先，我将描述一个简单但不太安全的想法。然后，我将描述一种我认为可以轻松地使其更加安全的方法。基本思想是让每个公司的向另一个公司发送一个单向函数的编码。

发送程序

作为热身，让我们首先假设一家公司(假设A)用某种语言开发了一个普通的计算机程序，并将其发送给B；然后B将运行该程序，并提供自己的电子邮件地址列表作为输入，该程序将报告A也使用了其中有多少电子邮件地址。在这一点上，B知道它与A共享了多少电子邮件地址。然后这个过程可以重复，但A和B的角色颠倒了。

发送SAT实例

用普通的编程语言直接实现这个程序将产生一个几乎很容易进行反向工程的程序。为了缓解这个问题，首先，不让程序直接报告计数，让我们将问题重新表述为决策问题:另一家公司的输入中是否至少有k封电子邮件？(这涉及选择要测试的某个值k；当然，如果双方都同意，则可以对许多不同的k值执行整个过程。(但请参阅最后一节以了解可能的结果)。现在，程序可以表示为一个SAT instance，它接受电子邮件地址列表的输入(一些位串编码)，并输出一个位，指示其中的k个或更多个是否也属于创建该实例的公司。

向SAT实例提供输入并读取输出位在计算上很容易，但是当实例很大时，(原则上)很难进行“另一个方向”--即，找到一个令人满意的输入分配，即一列电子邮件地址，它将把输出位驱动到1: SAT是一个NP-hard问题，所有已知的精确技术在问题大小上都需要时间指数。

使用散列使其更难处理

[EDIT:实际上有多个可能的散列(n选择k)个可能的散列被编辑在一起，因为在包含至少k个共享1的电子邮件地址列表中的任何有效的_ ORed ____(允许间隙)需要打开输出位。如果每个电子邮件地址最多占用b位，则有比2^((n- k) b)*(n选择k)更多的可能性。可能只对其中的一小部分进行采样是可行的，我不知道是否可以以某种方式将未采样的转换为“不关心”...]

我在这里提出的SAT实例肯定会非常大，因为它必须是所有(n选择k)可能允许的位串的析取(OR)。(让我们假设要求以某种特定的顺序列出电子邮件地址，以消除n阶乘因子。)然而，它有一个非常规则的结构，可以使它易于分析，从而可以极大地减少解决它所需的时间。为了解决这个问题，我们需要做的就是要求接收方对原始输入进行哈希处理，并将此哈希值作为输入提供。得到的SAT实例看起来仍然像(n choose k)个可能的有效位串的析取(OR) (现在表示字符串列表的散列，而不是原始的字符串列表) --但是，通过选择足够大的散列大小并对结果实例应用一些logic minimisation，我确信可以删除任何剩余的告示模式。(如果任何在该领域有更多知识的人可以证实或否认这一点，请编辑或评论。)

可能的攻击

这种方法的一个缺点是，没有什么能阻止接收器多次“运行”(向其提供输入) SAT实例。因此，选择k过低允许接收方通过多次重新运行SAT实例来轻松隔离与发送方共享的电子邮件地址，方法是使用其自身地址的不同k-组合以及剩余输入位的虚拟值(例如无效电子邮件地址)。例如，如果为k=2，则接收者可以简单地尝试运行所有n^2对自己的电子邮件地址和其余的无效电子邮件地址，直到找到一对打开输出位的电子邮件地址；然后这些电子邮件地址中的任何一个都可以与所有剩余的电子邮件地址配对，以在线性时间内检测到它们。

您应该能够使用homomorphic encryption来执行计算。我设想在两个站点上创建类似位掩码的东西，执行加密，然后对结果执行XOR。我认为this source指出了一些关于可以执行支持异或的加密的信息。