4

In the Christmas spirit I read Cryptographic Secret Santa from MathOverflow, and then followed the link to another page titled Cryptographic Secret Santa.

On this latter page the author explains an algorithm he would use to assign Secret Santas without need for trust to a central authority.

In the end however the author writes:

Although it's feasible for this mechanism, being used by a group of hacker friends, to be implemented with command line tools (pgp, ssh-keygen) and email lists for publishing - it's very desirable to have some sort of application (web application) to make it easier for non hacker friends to join the game.

Now when we reach the notion of Web Application, the absence of the need to trust goes out of the window: you will have to trust the Web Application. Even if you have the source code, you cannot be sure that the Web Application is compiled from the same version of the source code made available to you.

At this points, let depart from the realm of practical, and consider purely theoretical case. Let's assume that all clients do their own encryption, decryption, signing and verification, so they do not need to trust the server.

In this theoretical case the idea described in the article might work, but there is at least one hiccup that I can spot.

To make sure this process is correct where each participant have one and only one anonymous public key published. The number of keys should be equal to the number of participants, and each one should confirm that he/she has published the key and it's being listed (never pointing out which one is it though).

At the end of the publishing we should have an associated list with the identity public keys and the participant names, and a separate list of anonymous public keys that only each participant know which one is his/her public key, but not the others.

Stated like this it appears that the keys need to be submitted anonymously, but then an anonymous party can supply redundant keys and there will be no way to tell which keys are legit, and which are submitted by a malicious participant. Note, that a person that was invited to participate legitimately still can maliciously submit multiple anonymous key, and no one would know - that is if the server is not to be trusted with the information which anonymous key is whose

As such, it looks like this breaks down the entire proposed algorithm.

Questions:

  • Is my reasoning sound and the algorithm is no good in a sense that there is no way around trusting the web application if we use it as described?
  • Is there an "easy fix" that would allow it to work?
  • done! – lloyd Dec 19 '17 at 6:37
  • @lloyd but it has the very same issue: one can publish multiple keys. – Andrew Savinykh Dec 19 '17 at 6:40
  • yes so then it requires some mechanism like consensus. Possibly an invite mechanism or as suggested the keys are public so on a single server someone can have publish rights to that server with something like a token or API key. Or I guess have a restricted number of keys that can be issued. Not sure what an easy fix to third party trust issues would look like. "Trust, but Verify" – lloyd Dec 19 '17 at 7:38
0

You always need a secure way to distribute public keys. I believe the paper assumes you are able to do this.

However having that mechanism does not mean you can trust any single entity. You might trust me to give you my public key but you do not trust me not to rig the secret santa. Hence why this is still useful - you trust each individual to pass you their public keys but this is the only trust you have to have.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.