Secret Santa algorithm that does not rely on a trusted 3rd party? With a trusted 3rd party, running Secret Santa is easy: The 3rd party labels each person $1,\dotsc,n$, and then randomly chooses a derangement from among all possible derangements of $n$ numbers.  Person $i$ will then give a gift to the number in position $i$ of the derangement.  The trusted 3rd party is responsible for keeping the derangement secure, and for telling each person whom to give a gift to.
The question is: Is there an algorithm that would allow Secret Santa to be played without a trusted 3rd party?
I thought perhaps a clever use of secret keys and a one way hash function could accomplish it, but I've failed to find an algorithm so far.
So I'm looking for a description of a valid algorithm or a (informal) proof that one does not exist.
EDIT
I believe my problem is different from the possible duplicate.  I want a solution that will work for a distributed group of players.  That is, you cannot assume the players are in the same room and have the ability to shuffle envelopes or notecards or anything like that.  
To make this concrete, a valid solution must work across a group instant messenger or over group emails.
Also, to clarify again, it must be a random derangement and not merely a random n-cycle.
 A: How about this:


*

*Everybody generates a random private-public key pair.

*Everybody publishes their public key anonymously (see below).

*Collaboratively choose a random seed:
a. Everybody chooses a random seed component.
b. Everybody publishes a hash of their seed component openly.
c. Everybody publishes their actual seed component openly.
d. The seed is the sum of the components published in step (c).

*Use seed to derive a derangement of the public keys in a deterministic way. (Everybody can now do this for themselves).

*Everybody encrypts their name with their secret santa's public key and publishes the ciphertext.

*Everybody tries to decrypt all of the messages from the previous step with their own private key. When one of the decryptions succeed, they've found their target.
This assumes that "encrypting" with a public key uses some randomness to produces a non-deterministic result, so someone who has only the public key cannot tell whether a given cleartext and ciphertext match up or not. (This is a standard property of real public-key protocols, though not of textbook RSA).
The procedure does inherently make the cycle structure of the derangement public. In particular, everybody who is mutually santa with someone will know it. It is probably desirable to restrict oneself to "super-derangements" that don't have any $2$-cycles.
A variant that doesn't reveal the cycle structure, at the cost of not having a hard bound on the running time would be:


*

*Everybody chooses a random number and hashes it to produce a "santa ID".

*Everybody publishes their santa ID anonymously.

*Collaboratively choose a random seed.

*Use the seed to deterministically choose a bijection between santa IDs and target names.

*If anyone got themselves as target, complain openly, proving that it is so by revealing the number they hashed to get their ID. Everybody starts over from step 1 with new random numbers for everything. On average, $e$ iterations will be needed before a derangement is found.

Both of the above need a sub-algorithm for publishing things anonymously:


*

*Everybody generates a public-private key pair just for the publication sub-algorithm and publishes the public key.

*Everybody selects a random permutation $(K_i)_{1\le i\le n}$ of all the public keys from step 1.

*Everybody wraps their message in a series of encryptions:
$$ M_0 = \text{the message to publish} \\
 M_k = \operatorname{encypt}(K_k, M_{k-1}) \quad\text{for }1\le k\le n $$

*Everybody publishes their own $M_n$.

*Everybody tries to decrypt all the messages from the previous round. Publish all contents where decryption succeeds.

*After repeating the previous step $n$ times, everybody's original messages will be on the table, and nobody knows where any of them comes from (except their own).
A large enough collusion might be able to break the anonymous publishing step by traffic analysis, but if everybody except a few players collude, the game has lost much of its meaning anyway.
A: Here's one possible strategy. Number the people $1, 2, \dots, n$. They do the following things, in order. (Whenever someone chooses a random number, I assume it's uniformly random from some fixed range $[1,N]$, say $[1,2n]$, excluding all values they've seen before.)


*

*Person $1$ picks a random number $x_1$ and passes it to person $2$.

*Person $2$ picks a random number $x_2$, scrambles the list $(x_1,x_2)$, and passes it to person $3$.

*Person $3$ picks a random number $x_3$, scrambles the list $(x_1,x_2,x_3)$, and passes it to person $4$.

*And so on, with person $n$ receiving a permutation of the list $(x_1, x_2, \dots, x_{n-1})$.

*Person $n$ picks a random number $x_n$, scrambles the list $(x_1, \dots, x_n)$, and passes that to person $1$.

*Person $1$ records the position of $x_1$ (that's their secret Santa target), replaces $x_1$ by a new random number $y_1$, and passes the resulting list to person $2$.

*Person $2$ records the position of $x_2$ (that's their secret Santa target), replaces $x_2$ by a new random number $y_2$, and passes the resulting list to person $3$.

*And so on, until we get to person $n$, whose target is the position of $x_n$.


This does not guarantee that the permutation is a derangement. But everyone can check if they got themselves as a target; if they complain, we can start over. (On average, we'll have to start over $e$ times.)
No information is shared about other people's targets: in steps 1 through 4, person $k$ sees the values $x_1, x_2, \dots, x_{k-1}$, which are not helpful, because in steps 5 through 8, person $k$ is given a permutation of the values $y_1, y_2, \dots, y_{k-1}, x_k, \dots, x_n$: from their perspective, these are uniformly chosen from the complement of $\{x_1,\dots, x_{k-1}\}$.
Another awkward moment, though, is that person $n$ picks the final permutation, so they get to choose their secret Santa target if they cheat and don't do it randomly. However, we can have the other people collaboratively choose a random seed for person $n$ to use (say, they send them numbers $r_1, \dots, r_{n-1}$, and then $r_1 + \dots + r_{n-1}$ has to be the seed) and then this cheating can be exposed after everyone opens their presents.
