问题:
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-hard 问题，所有已知的精确技术在问题大小上都需要时间指数。
使用哈希使其更难
[编辑:实际上有很多比 (n 选择 k) 个可能的散列一起进行或运算，因为电子邮件地址列表中包含至少 k 个共享地址的任何有效子序列(允许有间隙)都需要打开输出位.如果每个电子邮件地址最多占用 b 位，那么就有不止 2^((n-k)b)*(n 选择 k) 种可能性。可能只对其中的一小部分进行采样是可行的，我不知道未采样的是否可以以某种方式变成“无关紧要”...]
我在这里提出的 SAT 实例肯定会非常大，因为它必须是所有 (n 选择 k) 个可能的允许位串的析取 (OR)。 (假设电子邮件地址需要按某种特定顺序列出，以消除 n 因子因素。)但是，它具有非常规则的结构，可能使其易于分析，从而可以显着减少解决问题所需的时间.为了解决这个问题，我们需要做的就是要求接收者对原始输入进行哈希处理，并提供这个哈希值作为输入。生成的 SAT 实例仍然看起来像 (n 选择 k) 个可能的有效位串(现在表示字符串列表的散列，而不是字符串的原始列表)的析取 (OR) -- 但是，通过选择足够大的散列大小并应用一些 logic minimisation对于结果实例，我相信可以删除任何剩余的告密模式。 (如果有在该领域有更多知识的人可以确认或否认这一点，请编辑或评论。)
可能的攻击
这种方法的一个弱点是没有什么可以阻止接收器多次“运行”(提供输入)SAT 实例。因此，选择太低的 k 允许接收者通过使用自己地址的不同 k 组合多次重新运行 SAT 实例，以及剩余输入位的虚拟值(例如无效的电子邮件地址)，轻松地隔离与发送者共享的电子邮件地址.例如。如果 k=2，那么接收者可以简单地尝试运行所有 n^2 对自己的电子邮件地址和其余无效的电子邮件地址，直到找到打开输出位的一对；然后可以将这些电子邮件地址中的任何一个与所有剩余的电子邮件地址配对，以在线性时间内检测它们。
关于algorithm - 在不泄露来源的情况下比较 secret 数据，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33104133/