wolever/bcsx.rst

## bcsx.rst

      
    Raw
  

              bcsx.rst
            
          
    By shazow and wolever.
Problem

How can N secret santa gift exchange participants agree on a gift-giver -> gift-recipient bijection such that:

Every participant will be assigned a unique recipient (ie, the giver -> recipeint mapping is a bijection; this also implies that each participant will have exactly one other participant assigned to give them a gift)
No participant will know who is assigned to give them (or anyone else) a gift
No participant will be assigned to give themself a gift
No participant can influence who they will be assigned
The system can proved to be fair (ie, the above properties hold) after the exchange takes place

Proposed Solution

To implement such a fair system:

Each participant secretly generates a public/private key pair, then anonymously publishes their public key (to, for example, a block chain)
After each participant has published their public key, the public keys are deterministically shuffled[0]
Each participant encrypts their identity (for example, their name and email) to the public key after their own and publishes the encrypted message

At this point, each participant will be able to decrypt exactly one of the encrypted messages – this will contain the identity of the person they will be giving a gift to.
After gifts have been exchagned, each participant will reveal their private key to prove that they gave a gift to the correct person.
[0]: for example, by lexagraphically sorting the public keys. Note that this would allow a participant some degree of control over their position in the list, potentlaly allowing participants to collude. To defend against this, the shuffling algorithm could be modified to take into consideration some value which can only be known after the last key is published. For example, the hash of the blockchain block which the last key occures in:
def shuffle(last_block_hash, keys):
  return sorted(keys, key=lambda key: hash(key) ^ last_block_hash)
Example

Imagine Alice, Bob, and Charlie want to exchange gifts.
First, each will generate a public/private key pair and anonymously publish the public keys:
public_keys = [pk_a, pk_b, pk_c]
Next, they will deterministically shuffle the public keys:
>>> shuffle_keys(public_keys)
[pk_b, pk_a, pk_c]
And each participant encrypts their identity to the key which appears after their own, then publishes the encrypted value. For example, if Alice has pk1, Bob has pk2, and Charlie has pk3, then:
Alice   (owner of pk_a) publishes: encrypt(pk_c, "You're giving a gift to Alex")
Bob     (owner of pk_b) publishes: encrypt(pk_a, "You're giving a gift to Bob")
Charlie (owner of pk_c) publishes: encrypt(pk_b, "You're giving a gift to Charlie")
Now each particpant can decrypt the message encrypted to their public key, which will tell them who they're giving a gift to. For example, Alice can decrypt the message which says "You're giving a gift to Bob".
Finally, after the gift exchange, each participant can reveal their public key to prove that they gave a gift to the correct person.
Discussion

This algorithm assumes the avaiability of a blockchain-like system which each participant can reliably read from and write to. Specifically, it does not defend against attacks from bad actors who can tamper with a participant's view of, or writes to, the blockchain.
Additionally, bad actors can be detected, but there is no protection against denial of service attacks. For example, if Eve publishes two public keys, Alice will notice either that too many keys were published, or that her key was not included in the encrypted messages (at which point she can phone her friends and tell them to stop being idiots).
Timing-based de-anonymization attacks should also be considered. For example, if it becomes known that Charlie was the last to publish his key ("I'll do it tomorrow, promise!"), it will be easy to determine which key is his.