email - 匿名比较两个电子邮件地址列表

Question

给定两个列表:

A 公司:

user1@example.com

user2@example.com

user3@example.com

user4@example.com

公司 B:

user2@example.com

user4@example.com

user5@example.com

有没有办法匿名比较它们以获得共同电子邮件地址的数量(即 2)，而两家公司都不知道哪些地址是共同的？

背景:

假设公司 A 和公司 B 想知道他们的用户群中有哪一部分是共同的。为简单起见，他们只是将其基于电子邮件地址，而不关心使用多个地址或不同地址变体的人 (user+misc@example.com)。

出于隐私考虑，两家公司都不能向对方提供电子邮件地址的简单列表。如果他们使用相同的简单散列，例如MD5，每个公司都可以很容易地知道哪些成员是共同的(不需要)。如果他们使用加有公司特定 secret 的散列，地址将不再具有可比性，因此无法回答该问题。

是否有一些技巧可以使用 key 加密或其他一些数学方法来完成我想要做的事情？

Answer 1

我相信这个问题在密码学领域可以得到更好的理解。

是secure multi-party computation的问题.

我不知道有任何针对此问题的防弹解决方案，但我可以想到以下几点:

1. 选择一个交换哈希函数(H):

   H(H(string, seed1), seed2) = H(H(string, seed2), seed1)

2. 各方(公司 A 和公司 B)必须选择一个 secret 种子:

   SEED_A, SEED_B

3. 公司 A 使用 SEED_A 对所有电子邮件地址进行哈希处理，公司 B 使用 SEED_B 对所有电子邮件地址进行哈希处理。

4. 他们交换哈希值。

5. 每家公司在从对方收到的集合上再次应用哈希函数。

6. 此时数据应该已经是乱码，公司应该无法识别他们自己的电子邮件地址(因为它们已经被散列两次 - 第二次使用未知 key )。

7. 所有电子邮件地址都应该公开列出，那些具有相同哈希值的应该算作属于两家公司的电子邮件地址(除了两家公司都不能说出哈希值的来源)。

这是理论。希望我没有遗漏任何东西，算法也没有缺陷。

至于实现，这里是我可以使用的最简单的 PHP 脚本:

$a = array("user1@example.com", "user2@example.com", "user3@example.com", "user4@example.com");
$b = array("user2@example.com", "user4@example.com", "user5@example.com");

function enc($str, $seed) {
    for ($i = strlen($str) - 1; $i >= 0; $i--) {
        $str[$i] = $str[$i] ^ $seed[$i % strlen($seed)];
    }
    
    return $str;
}

/* Company A */
$hashesForB = array();
$SEED_A = 'SALT FOR COMPANY A';

foreach ($a as $address) {
    $hashesForB[] = enc($address, $SEED_A);
}

/* Company B */
$hashesForA = array();
$SALT_B = 'THIS IS THE SALT FOR COMPANY B';

foreach ($b as $address) {
    $hashesForA[] = enc($address, $SALT_B);
}

/* Company A */
$hashesForB_2 = array();

foreach ($hashesForA as $hash) {
    $hashesForB_2[] = enc($hash, $SEED_A);
}

/* Company B */
$hashesForA_2 = array();

foreach ($hashesForB as $hash) {
    $hashesForA_2[] = enc($hash, $SALT_B);
}

$common = count(array_intersect($hashesForA_2, $hashesForB_2));

print $common; // it will output 2

Click here for the DEMO

如您在上面的代码中所见，我使用 XOR 算法进行(伪)散列(实际上，任何基于加法的散列函数都可以完成这项工作)。

显然，出于多种原因，这不是最佳选择:

• 异或将在使用相同盐的新调用时返回原始输入
• 熵不是你所希望的最好的
• 数据没有被截断

不过，您可以使用建议 here 来实现您自己的哈希函数, here , here或 here .