The problem presented here (of generating a random cyclic permutation) is also useful for Secret Santa. A simpler solution than the one presented here, with similar requirements, is presented in Section 5.1 of the paper Cryptographic Protocols with Everyday Objects by Heather, Schneider, and Teague, where it is called the "Father Cryptmas Protocol". Thanks to Ryan Lahfa for the pointer.

The killer game is played as follows: each player is given a "victim" (another player) which he has to "kill" in some way (which depends on the variant played). Whenever a player manages to kill his victim, he gets the victim's victim as his new victim, and the killed player is eliminated. The aim of the game is to kill without being killed; the winner is the last man standing.

The usual way to play the game is to ask some trusted third party to generate the list of killer-victim relations and to give each player a piece of paper indicating his victim. Of course, it would be quite natural to use a computer to generate the game instead, in order to avoid the need to ask someone to create the game and not be able to play. What I will present is this post is an even nicer system: a way for players to organize together a killer game by themselves, in such a way as to prevent anyone from getting any information about the generated game. No computer needed: you only need paper, a pen, and a deck of n cards (where you number the players from 1 to n).

As for security, the main requirement isn't to prevent deliberate trickery but rather accidental remembering of information. In other words, we want to organize a game between people who are honest but who wouldn't like to remember things about the game inadvertently (ie. we don't want to depend on their having a bad memory). Hence, we assume that players don't really try to cheat or form coalitions to cheat together, but that they just want to generate the game without having to try to not remember what they have done.

The problem can be separated in two steps:

1. First, generate the permutation mapping each player to its victim. (It is a permutation since each player is the victim of exactly one player.) We can't accept any permutation: the permutation needs to have only one orbit. (Otherwise, the game will have multiple winners.)
2. Second, generate the papers giving to each player its victim. This isn't straightforward at all, because we can't just ask one player to write them down: the papers need to be written in a way which prevent anybody from knowing their contents.

The first step, in fact, is easy to solve. If you take a deck of n cards and shuffle it collaboratively (ie. every player gets a chance to shuffle the deck, to prevent cheating), the permutation mapping the i-th card of the deck to the i+1-th one (modulo n) is a permutation with only one orbit; moreover, if the order of cards is chosen uniformly at random, the resulting permutation is also chosen uniformly at random among all such permutations. Thus, the players have a way to create together securely a suitable permutation.

What remains is to generate pieces of paper mapping players to their victims. We will assume that, for each player, we have a blank piece of paper on which we will apply the following operations:

1. Write the number of the victim on the paper.
2. Fold the paper in such a way that the victim number cannot be read.
3. Write on the outside of the paper the number of the player which should kill the victim.
4. Fold the paper to make both numbers unreadable, and put the paper in an urn.

Now, the idea is that each player but the first one will apply the following procedure:

• Input: The deck of cards and a piece of paper folded once.
• Output: The deck of cards without the top card and another piece of paper folded once.
• Procedure:
  1. Draw the first card of the deck, secretly, memorize its value, and discard the card (in a discard pile which will not be examined).
  2. Write the value on the folded piece of paper, fold it a second time and put it in the bin.
  3. Take a new piece of paper, write the value on it, and fold it once.

What is supposed to happen is that the players pass the deck of cards (with a piece of paper) to each other, producing papers as we go. The order of players is determined at random collaboratively (ie. the players draw a random number together, for example by committing to a value and XORing the values). The question of the first and last card still needs to be settled, and it is the role of the first player. More precisely, the first player starts off the process and ends it in the following way:

• At the beginning, take the deck of cards, and follow the algorithm above without the last step to prepare the first piece of paper (folded once).
• At the end, take the empty deck of cards and the last piece of paper (folded once), and apply the last step with the value memorized for the initial step.

Of course, once we have run all that, all that we have to do is to empty the urn, unfold each paper once, and give each paper to the player indicated on it. Players then open their paper and find their target.

What remains is that we want to ensure that, by following this scheme, players don't get information about the game. But the beautiful thing is that players only see one player value, so they really can't have no information about any player's relation to other players. In fact, to put it in a nutshell, the idea is that the papers represent couples of a value and its image by the permutation, and that we generate them by asking each player to write down a given number twice: once as value, and once as image.

As for actually playing the game, what's really funny is that you don't have any information about the game's progress, because nobody knows what the players are up to. Players kill themselves in a decentralized way, and, at some point, a player should discover that the person he killed was his own killer, which means that he won the game.

This scheme was successfully implemented two years ago to play a game in my Math spé class. Of course, the protocol wasn't respected to the letter (we didn't have enough people to generate the game, so players got multiple turns writing numbers down, which we tried to space as much as possible), and we had to work our way around a few practical difficulties, but everything went smoothly. The generated permutation was correct (an entirely unexpected thing given the fact that the deck used was a standard deck with a conversion rule to match value and suit to player number and then to player name, with a lot of opportunities for mistakes), and the game was played up to its conclusion (which was once again very fortunate, given the fact that there wasn't anyone able to correct errors or to make things move should the game get stuck somewhere).

Of course, the best thing was that I was able to play the game even though I was the one who had made the whole scheme up.