wolever · December 9, 2022 07:41 · Nov 29, 2016 · Nov 29, 2016 · Nov 29, 2016 · Nov 29, 2016
diff --git a/bcsx.rst b/bcsx.rst
@@ -61,4 +61,6 @@ 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).
+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.
diff --git a/bcsx.rst b/bcsx.rst
@@ -1,4 +1,4 @@
-By `shazow`__ and `wolever`__
+By `shazow`__ and `wolever`__.
 
 __ https://twitter.com/shazow
 __ https://twitter.com/wolever

diff --git a/bcsx.rst b/bcsx.rst
@@ -1,4 +1,4 @@
-By @`shazow`__ and @`wolever`__
+By `shazow`__ and `wolever`__
 
 __ https://twitter.com/shazow
 __ https://twitter.com/wolever

diff --git a/bcsx.rst b/bcsx.rst
@@ -1,3 +1,8 @@
+By @`shazow`__ and @`wolever`__
+
+__ https://twitter.com/shazow
+__ https://twitter.com/wolever
+
 Problem
 -------
 

diff --git a/bcsx.rst b/bcsx.rst
@@ -0,0 +1,59 @@
+Problem
+-------
+
+How can N secret santa gift exchange participants agree on a gift-giver -> gift-recipient bijection such that:
+
+1. 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)
+2. No participant will know who is assigned to give them (or anyone else) a gift
+3. No participant will be assigned to give themself a gift
+4. No participant can influence who they will be assigned
+5. 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:
+
+1. Each participant secretly generates a public/private key pair, then anonymously publishes their public key (to, for example, a block chain)
+2. After each participant has published their public key, the public keys are deterministically shuffled[0]
+3. 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).
No results found