algorithm - 在任何一方都不知道盒子内容的情况下使用密码学随机播放

Question

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

到目前为止我在想...

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 工作(以后可能不会提供 key - 干扰与其他方之间的交易)。

总结

理想情况下，我需要一种算法来在两个不可信的方之间洗牌，这样一副牌，并且所有各方稍后都可以验证这些牌，只要至少有 2 个感兴趣的方提供最后彼此分享他们的 secret 。

Answer 1

这就是著名的Mental Poker Problem .一种解决方案涉及 commutative加密 (即 E₁(E₂(M))== E₂(E₁(M))).

来自维基文章:

1. Alice and Bob agree on a certain "deck" of cards. In practice, this means they agree on a set of numbers or other data such that each element of the set represents a card.
2. Alice picks an encryption key A and uses this to encrypt each card of the deck.
3. Alice shuffles the cards.
4. Alice passes the encrypted and shuffled deck to Bob. With the encryption in place, Bob cannot know which card is which.
5. Bob picks an encryption key B and uses this to encrypt each card of the encrypted and shuffled deck.
6. Bob shuffles the deck.
7. Bob passes the double encrypted and shuffled deck back to Alice.
8. Alice decrypts each card using her key A. This still leaves Bob's encryption in place though so she cannot know which card is which.
9. Alice picks one encryption key for each card (A1, A2, etc.) and encrypts them individually.
10. Alice passes the deck to Bob.
11. Bob decrypts each card using his key B. This still leaves Alice's individual encryption in place though so he cannot know which card is which.
12. Bob picks one encryption key for each card (B1, B2, etc.) and encrypts them individually.
13. Bob passes the deck back to Alice.
14. Alice publishes the deck for everyone playing.
    [...]
    This algorithm may be expanded for an arbitrary number of players.

这允许洗牌，而不会允许任何一方作弊，并且任何一方都不知道对方有什么牌(如果您删除最后一个要求并且只希望公平洗牌，问题就会变得容易得多) .

使用的加密必须是安全的 known plaintext attacks .