Alok Menghrajani

Security engineer at Square. Previously co-author of Hacklang and pushed for adoption of 100% https at Facebook.

Home | Contact me | Github | Twitter | Facebook

Seven cryptographers would like to exchange presents with each other. They are geographically located in different places, so they can't use a traditional white elephant scheme (everyone brings a wrapped gift and puts it on a table, people then draw names and take turn picking a gift).

Can you figure out a cryptographically equivalent scheme?

Specifically, design a distributed algorithm where:

  • The algorithm results in every cryptographer knowing who they need to get a present for (they can tailor their presents) but not knowing who is getting them a present (there's a surprise factor).
  • Each cryptographer has a public/private key pair.
  • Each cryptographer knows the public key of the other six participants, as well as their address (so they can mail the presents).

             ___.-~"~-._   __....__
           .'    `    \ ~"~        ``-.
          /` _      )  `\              `\
         /`  a)    /     |               `\
        :`        /      |                 \
   <`-._|`  .-.  (      /   .            `;\\
    `-. `--'_.'-.;\___/'   .      .       | \\
 _     /:--`     |        /     /        .'  \\
("\   /`/        |       '     '         /    :`;
`\'\_/`/         .\     /`~`=-.:        /     ``
  `._.'          /`\    |      `\      /(
                /  /\   |        `Y   /  \
          jgs  /  /  \  |         |  /`\  \
              /  |   |  |         |  |  |  |
             /___|  /___|        /___|  /__|
             '"""   '"""         '"""  '"""

Happy holidays! I will post a solution here in a few weeks...

First solution

Another solution