3

我正在寻找一种方法来在两个彼此不信任的客户之间洗牌一系列已知值(如一副纸牌),以一种双方都可以验证的方式,并且不会获得任何优势。

到目前为止,我在想...

for each item in array:
  A tells B random number to use (Ra1) <~ prevent B from using pre-calculated password
  B creates secret random number, and shows hash to A <~ can prove this number is used
  B adds his own secret random number (Ra1+Rb1) <~ prevent A from using pre-calculated password
  B encrypts a random array value using the combined password (Ra1+Rb1), removing from the stack
  B gives encrypted value to A
  A re-encrypts the value <~ prevent B from recognizing his package later
  A stores at random index in new array of unknown items

A shows the full array to B <~ B can be confident that the array will not be tampered with
A does not know what is in each package, nor does B
B can now choose a package for himself, and A can then provide the password for that package, allowing B to recognize his package, and know the contents.
A can also choose a package, and request the key to unlock it form B.

After all transactions are agreed, and secrecy is no longer required, all secrets are revealed by both parties, who can both then verify the contents of the boxes

这一切对我来说似乎过于复杂——我无法想象如何让它为 A、B 和 C 工作,这样任何一方都不需要值得信赖或可靠(以后可能不提供密钥——干扰之间的交易)其他方)。

概括

理想情况下,我需要一种算法来洗牌,在两个不值得信任的各方之间,以这样的方式洗牌,只要有至少 2 个利益相关方相互提供他们的卡片,所有各方都可以稍后验证这些卡片。最后的秘密。

4

1 回答 1

6

这就是著名的心理扑克问题。一种解决方案涉及交换加密(即 E 1 (E 2 (M)) == E 2 (E 1 (M)))

来自维基文章:

  1. 爱丽丝和鲍勃就某一“一副”牌达成一致。在实践中,这意味着他们同意一组数字或其他数据,使得该组的每个元素都代表一张卡片。
  2. Alice 选择一个加密密钥 A 并使用它来加密一副牌中的每张牌。
  3. 爱丽丝洗牌。
  4. 爱丽丝将加密和洗牌的套牌传递给鲍勃。加密到位后,Bob 无法知道哪张卡是哪张卡。
  5. Bob 选择一个加密密钥 B 并使用它来加密加密和洗牌后的每张牌。
  6. 鲍勃洗牌。
  7. Bob 将双重加密和洗牌的套牌传回给 Alice。
  8. Alice 使用她的密钥 A 解密每张卡。尽管如此,Bob 的加密仍然存在,因此她无法知道哪张卡是哪张卡。
  9. Alice 为每张卡(A1、A2 等)选择一个加密密钥并单独加密它们。
  10. 爱丽丝把牌递给鲍勃。
  11. Bob 使用他的密钥 B 对每张卡进行解密。尽管如此,Alice 的个人加密仍然存在,因此他无法知道哪张卡是哪张卡。
  12. Bob 为每张卡(B1、B2 等)选择一个加密密钥并单独加密它们。
  13. 鲍勃把牌递给爱丽丝。
  14. 爱丽丝为每个玩的人发布了套牌。
    [...]
    该算法可以针对任意数量的玩家进行扩展。

这允许洗牌,不允许任何一方作弊,并且任何一方都不知道对方有什么牌(如果你去掉最后一个要求,只想要公平洗牌,问题就变得容易多了)

所使用的加密必须对已知的明文攻击是安全的。

于 2012-08-24T21:38:34.183 回答