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?
