CODEWITHSUNDEEP
algorithmcryptographyshuffle
Billy Moon
Billy Moon

Reputation: 58531

Shuffle using cryptography without either party knowing box contents

I am looking for a way to shuffle an array of known values (like a deck of cards) between two clients who don't trust each other, in a way that can be verified by both parties, and no advantage can be gained.

So far I am thinking...

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

This all seems overly complex to me - and I can't imagine how to make it work for A, B and C in such a way that no party needs to be trustworthy, or reliable (might not provide keys later - interfering with transactions between other parties).

Summary

Ideally, I need an algorithm to shuffle a deck of cards, between two untrustworthy parties, in such a way the deck, and the cards can be verified later by all parties, so long as there are at least 2 interested parties providing each other their secrets at the end.

Upvotes: 3

Views: 724

Answers (1)

BlueRaja - Danny Pflughoeft
BlueRaja - Danny Pflughoeft

Reputation: 85996

This is the famous Mental Poker Problem. One solution involves commutative encryption (ie. E1(E2(M)) == E2(E1(M))).

From the wiki article:

  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.

This allows the cards to be shuffled, without allowing either side to cheat, and without either side knowing what cards the other has (if you remove the last requirement and only want fair shuffling, the problem becomes much easier).

The encryption used must be secure against known plaintext attacks.

Upvotes: 6

Related Questions