问题:
公司A拥有不希望泄露给公司B的 secret 数据。
公司B拥有他们不想泄露给公司A的 secret 数据。
secret 数据是双方的IP地址。
但是，两家公司都想知道他们拥有重叠IP的数量(两家公司在数据库中拥有的IP地址)。
如果不使用第三方，那么如果没有一方破坏其 secret 数据集，我就无法想出解决此问题的方法。是否编写了任何类型的哈希算法来解决此问题？
最佳答案
首先，我将描述一个简单但不是很安全的想法。然后，我将描述一种我认为可以轻松提高安全性的方法。基本思想是让每个公司将单向函数的编码发送给另一家公司。
发送程序
作为热身，我们首先假设一家公司(假设A)以某种语言开发了一个普通的计算机程序，然后将其发送给B。然后，B将运行它，提供其自己的电子邮件地址列表作为输入，程序将报告A也使用了其中的电子邮件地址。此时，B知道它与A共享了多少电子邮件地址。然后，该过程可以重复，但与A和B的角色相反。
发送SAT实例
用普通的编程语言直接实现该程序将产生一个几乎很容易进行逆向工程的程序。为了减轻这种情况，首先，让我们将问题重新制定为决策问题，而不是让程序直接报告计数:另一公司是否在输入中至少包含k个电子邮件？ (这涉及选择某个值k进行测试；当然，如果双方都同意，则可以对k的许多不同值执行整个过程。(但请参见最后一节以了解可能的结果。)现在可以表示该程序而是作为SAT instance，它接受电子邮件地址列表作为输入(某种形式的位串编码)，并输出单个位来指示其中k个或多个是否也属于创建该实例的公司。
从计算上来说，为SAT实例提供输入并读取输出位很容易，但是当实例很大时，(原则上)很难朝“另一个方向”走-即，找到令人满意的...分配。输入，即将输出位驱动为1的电子邮件地址列表:SAT是NP难题，所有已知的精确技术在问题大小上花费的时间呈指数形式。
使用散列使其更困难
[编辑:实际上，有超过(n选择k)个可能的散列要进行或运算，因为电子邮件地址列表中的任何有效子序列(允许有空格)至少包含k个共享的子序列，都需要将其输出位上。如果每个电子邮件地址最多使用b位，那么存在的可能性远远超过2 ^((n-k)b)*(n选择k)个可能性。仅对其中的一小部分进行采样可能是可行的，而且我不知道是否可以将未采样的样本转换为“不在乎” ...]
我在这里提出的SAT实例肯定很大，因为它必须是所有(n个选择k个)可能的允许位串的异或(OR)。 (让我们假设电子邮件地址必须以某种特定顺序列出，以消除n因子。)但是，它具有非常规则的结构，可以使其易于分析，从而可以大大减少解决该问题所需的时间。 。为了解决这个问题，我们需要做的就是要求接收者对原始输入进行哈希处理，并提供此哈希值作为输入。生成的SAT实例仍然看起来像(n选择k)个可能的有效位串(现在表示字符串列表的哈希，而不是原始字符串列表的哈希)的或(或)-但是，通过选择足够大的哈希值并将logic minimisation应用于结果实例，我相信可以删除所有剩余的讲述模式。 (如果在该领域有更多知识的任何人都可以确认或拒绝，请进行编辑或评论。)
可能的攻击
这种方法的一个缺点是，没有什么可以阻止接收器多次“运行”(向SAT实例提供输入)。因此，选择太低的k可使接收者通过使用其自身地址的不同k组合和剩余输入位的伪值(例如无效的电子邮件地址)多次重新运行SAT实例来轻松隔离与发送者共享的电子邮件地址。例如。如果k = 2，则接收者可以简单地尝试运行所有n ^ 2对自己的电子邮件地址和其余所有无效的电子邮件地址，直到找到一对将输出位打开为止。然后，可以将这些电子邮件地址中的任何一个与所有剩余的电子邮件地址配对，以在线性时间内检测到它们。
关于algorithm - 比较 secret 数据而不泄露源，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33104133/