验证秘密的等价性

Question

Alice &鲍勃是秘密的四人代理人，他们可能在美国，俄罗斯或中国工作。他们想要制定一个计划：

1. 如果他们都是为同一方工作，请相互证明以便他们可以自由交谈。

2. 如果他们正在为不同的方面工作，不暴露他们在哪一边的任何额外的信息。

哦，并且由于他们所做的事情很敏感，没有可以为他们做比较的可信第三方。

什么协议能够满足这两个需求？

理想情况下，任何协议也可以推广到多个参与者和多个国家，但这不是必需的。

我困惑过了一段时间，我无法找到一个满意的解决方案，这主要是由于条件2

编辑：下面是促使我寻找一个解决原来的问题。 “查理”有一些他与我分享的个人照片，我后来发现他也与“鲍勃”分享了他们。我们都想知道我们是否有相同的照片，但同时，如果查理没有与我们任何一个人分享某张照片，他可能有一个很好的理由不会泄漏，我们也不想泄漏信息。

我的第一个想法是我们每个人都连接所有的照片，并提供MD5总和。如果他们匹配，那么我们有相同的照片，但如果他们没有，那么任何一方都不知道对方有哪些照片。不过，我很快意识到这个方案仍然会泄漏信息，因为鲍勃可以为每张照片的子集生成MD5，如果其中任何一张匹配了我的总和，他就会知道我没有的照片。我还没有找到一个令人满意的解决方案来解决这个问题，但我想我会推广它，以避免人们关注我的具体情况。

Answer 1

对于这两个问题，您可以使用Secure two-party computation等效算法。有很多方案，例如Damgard，Fitzi，K​​iltz，Nielsen和Toft的方案：Unconditionally Secure Constant Round Multi-Party Computation for Equality, Comparison, Bits and Exponentiation。

当然，代理人可以尝试从另一方冒充代理人，以获得1/3机会来发现另一代理人的真实面，但这似乎是不可避免的。

一个更简单的照片的问题，这应该是几乎一样的安全多方计算好方案，如下：

1. Alice和Bob排序他们的照片，并生成一个SHA-512散列。
2. Alice将她的散列的第一位发送给Bob。
3. Bob将该位与他的散列的第一位进行比较。如果不同，他们知道他们收到了不同的照片。否则，他们继续。
4. Bob将他的散列的第二位发送给Alice。
5. Alice检查这一点并决定是否继续。
6. 继续，直到协议中止或检查所有位。

Answer 2

RSA不在这里工作吗？每个国家都知道自己的私钥，发布公钥，只有相同的国家才能解密信息。然而，我想第二个人会知道，第一个人不是和他们在同一方。

嗯。

Answer 3

Public Key Cryptography怎么样？

Answer 4

所以他们保证是四倍代理？那就是他们保证秘密为一个派别工作，而假装工作一秒钟，假装工作三分之一，假装工作四分之一？它们仅限于美国，俄罗斯或中国？如果是这样的话，那意味着至少会有一个派系假装为同事工作。这似乎否定了他们成为四人代理人的能力，因为他们当中有一个不能为美国人工作，同时暗中为美国人工作，同时为美国人秘密工作，同时为美国人秘密工作。

你说理想的解决方案会推广到任意数量的状态和间谍堆栈。特务的程度可以高于，等于或低于州的数量？这可能很重要。另外，爱丽丝是否总是保证与鲍勃具有相同的代理人水平？即他们总是会成为三重代理人，或总是由五元代理人？模数操作员想起...

更多详情请。

作为一个潜在的答案，你可以枚举状态到一个位域。美国= 1俄罗斯= 2，中国= 4，马达加斯加= 8，图瓦= 16等。构建一个基本上是与门的设备。爱丽丝建造并带来一半，鲍勃建立并带来另一半。用布分开，每按一下他们真正为之工作的状态的按钮。如果与门的输出高，那么它们在同一侧。如果没有，那么他们就悄悄地取下布，然后与他们的机器的两半分开，以便不能通过指纹确定按钮。

这不是理论性的或严谨的，而是实用的。

Answer 5

有趣。

我认为，不管是什么方案，它都需要涉及一个随机失败的组件。这是因为相互矛盾的要求。你需要一个计划，即使他们在同一方面，偶尔也是行不通的。因为如果它一直有效，他们会立即能够确定它们不在同一侧。

你的观点'B'也含糊不清。你说你不想公开他们在哪一方。这是否意味着信息不能指向具体是其中一方？如果爱丽丝认为鲍勃来自其中一人，这可以吗？

另外，你有没有尝试过发邮件给cryptography mailing list？可能会在那里得到更好的回应。这是一个有趣的思考:)

Answer 6

这里是我来解决最靠近：

假设有一个函数doubleHash这样

doubleHash(a+doubleHash(b)) == doubleHash(b+doubleHash(a))

爱丽丝生成一个62位秘密并将2位国家代码附加到它的末尾，将其哈希并给出Bob doubleHash（a）。

Bob做同样的事情，并给予爱丽丝doubleHash（b）。

Alice将原始秘密附加到Bob给予她的散列上，将其散列并将其发布为doubleHash（a + doubleHash（b））。

Bob做同样的事情，并发布doubleHash（b + doubleHash（a））。

如果两个哈希匹配，那么它们来自同一个国家。另一方面，如果它们不匹配，那么Bob就不能解密哈希，因为他不知道Alice的秘密，反之亦然。

但是，这样的方案依赖于doubleHash函数的存在，我不确定这样的事情是否可能。

Answer 7

对于你的照片问题，为你的照片的所有子集创建散列;随机选择其中的一个子集，并随机生成一定数量的散列值进行混洗。鲍勃也是这样做的，你们交换了这些集合。如果Bob向您发送的哈希值与您通过散列照片子集生成的哈希值相比所产生的哈希值的比例与您的期望值显着不同，那么很可能您的照片语料库与他的显着不同。如果您认为随机哈希的比例很高，那么您可能无法检测到您的照片集中的细微差异;如果比例较低，则可能会泄露有关丢失照片的信息;你将不得不为折衷选择一个合适的点。

Answer 8

最简单的事情，我能想到的与将可能的工作是这样的照片：

1. 哈希所有的照片，和4096位散列。
2. 按照散列值对照片进行排序。 （哈希是最后一个，只是一个大数字的字符串表示）
3. 使用该排序顺序，使用流式系统对这些照片进行管道和散列，就好像它们是单个文件一样。
4. 分享你的哈希。
5. 如果哈希匹配，则具有相同的文件。 （不正确的正匹配的低风险低，但在4K散列，它有点不太可能）

有当然，也有一些不足的位置：

1. 不要共享你有多少张照片有。这样做可以允许拥有更多照片的派对对数据进行智能排列，并从他们怀疑可能没有的散列集合中删除照片，并以数字作为指导，并找到（以极大的计算开支为代价）一组与您的散列匹配的图像。
2. 他们可以在没有数字的情况下做1，但更难，而且如果他们实际上没有照片，他们就会走运。
3. 他们可以使用随机数字生成器创建一个假哈希，并将其发送给您，当您拥有相同的数据时，给您的印象是您拥有不同的数据集。

上述弱点也是在你的国家代码识别系统普遍，当然除了，你有远少熵的方式来获得，其远容易欺骗系统。 （因此，通过纯粹的暴力来弄清楚他们是谁，或者通过暴力破解你自己，无论你的散列算法有多么华丽） 如果情况并非如此，那么你应该已经通过你工作的机构发现，因为可靠和安全的东西将会是一种安全的背景检查方式。

Answer 9

的照片场景是不可能实现的：

你的方案为您命名的原因是不可能的。

考虑一个函数f，它需要两组照片s1和s2。 如果s1 = s2，则f（s1，s2）返回true，如果s1！= s2则返回false。 也就是说，这个函数实现你想要的方案。

鲍勃可以随时提供他拥有的照片的子集，并了解哪张照片的查理没有。 没有办法解决这个问题，任何拥有你想要的属性的函数都不能拥有你想要的安全性。

间谍情景更是不可能的：

由于Kent Fredric指出间谍方案具有更大的固有缺陷。 它具有照片场景中的所有问题，加上只有四个秘密的额外弱点。

在照片场景中，Bob很可能会随机猜测Charlies照片中的一张。 Bob在间谍场景中猜测Alices选择（1/4）是微不足道的。 间谍只有四个他们可以属于的国家，因为他们都是四个代理人，他们都知道每个国家的所有密码字。因此，鲍勃可以假装为中国人工作来测试爱丽丝。

不同类型的解决方案：

一些海报已经注意到，能够实现安全性，如果你减弱f的精度提高。 当然，如果不准确的话是什么意思。我提出了一种不同类型的解决方案。

• 不要让它们多次比较相同的 照片。

希望开始比较的一方必须首先证明这是一个新的比较，并且不使用之前的任何图片。

编辑：问题与双哈希

我提出有关doublhash协议的一些假设，但...

1. 对于照片方案中，doublehash协议不大于f好，因为62位密码必须由一组照片构成，以便进行比较以获得有意义的结果。原始问题中提到的子集攻击在这里仍然适用。尝试使用所有照片的子集来暴力化你可以产生的秘密，因此鲍勃可以看到他是否能够产生与艾丽丝相同的秘密。

使用doublehash属性Bob仍然可以暴力破解这个秘密。

doubleHash(s1+doubleHash(b)) != doubleHash(aliceSecret+doubleHash(a)) 

doubleHash(s2+doubleHash(b)) != doubleHash(aliceSecret+doubleHash(a)) 

doubleHash(s3+doubleHash(b)) == doubleHash(aliceSecret+doubleHash(a)) 

宾果，aliceSecret == s3。

DoubleHash是仅作为强，因为它是难以暴力破解A或B

Implementating DoubleHash

相反doubleHash（A + doubleHash（b）中），试图doubleHash（一个，MD5（二））。 DoubleHash（A + doubleHash（B））是不好的，因为鲍勃可能产生冲突的哈希值，像这样：

doubleHash((12 + doubleHash(34)) + doubleHash(5678)) 
= doubleHash((34 + doubleHash(12)) + doubleHash(5678)) 
= doubleHash(5678 + doubleHash(12 + doubleHash(34)) 
= doubleHash(5678 + doubleHash(34 + doubleHash(12)) 

下面是使用新配方doubleHash的实现，

Doublehash(a, hashOfB){ 
    hashOfA = md5(a) 
    combinedHash = hashOfA xor hashOfB 
    return md5(combinedHash) 
} 

人们还可以使用在blind signatures之后的数学暗示doubleHash的版本。