Comparing information without leaking it
Comparing information without leaking it
复制标题
DOI：
10.1145/229459.229469
复制
发表时间：
1996-05-01
影响因子：
22.7
通讯作者：
Winkler, P
中科院分区：
文献类型：
--
作者：
Fagin, R;Naor, M;Winkler, P
在这种情况下，通常使用的协议类似于游戏“20个问题”，但被称为微妙的对话探测。罗恩可能会问摩西，摩西的投诉者是否是男性；如果答案是肯定的，摩西可能会问罗恩，投诉者的姓氏是否在字母表中以M开头。这一直持续到罗恩和摩西确定他们心中是否有同一个人。然而，当他们没有这样做的时候(特别是当第一个不出现在游戏的后期)，可能交换了大量的信息。在提出一些更好的协议之前，我们指出，两个或更多各方可能希望在不泄露信息的情况下进行比较的无数其他原因。显然，每当两个人怀疑他们心中有同一个人提名某个职位、邀请共进晚餐或为一场灾难负责，但两人都不愿冒着尴尬的风险透露名字，情况就很像罗恩和摩西的情况。
The protocol typically used in a situation like this is akin to the game “20 Questions,” but is known as delicate conversational probing. Ron might ask Moshe if Moshe’s complainer is male; if the answer is Yes, Moshe might ask Ron if Ron’s complainer’s surname begins with a letter preceding M in the alphabet. This goes on until Ron and Moshe determine whether they have the same person in mind. When they do not, however (particularly when the first No occurs late in the game), a great deal of information may have been exchanged. Before suggesting some superior protocols, we point out that there are myriad other reasons why two or more parties might wish to compare information without leaking it.Obviously, whenever two persons suspect that they have the same person in mind to nominate for some post, invite for dinner, or blame for a disaster, but neither is willing to risk embarrassment by revealing the name, the situation is much like the one with Ron and Moshe.