Hi, Habr! In this article, I will give a simple algorithm that allows a group of N people to secretly generate each of the group members the number of another participant — the donated person — to exchange gifts for the New Year in the Secret Santa event.

First of all, what is Secret Santa? The Wikipedia article tells it better than me, I will only briefly say that this is a ceremony that came to us from the West, in which a group of people conspire to give gifts to each other for each other in such a way that each of the participants gives and receives one gift, with this one does not know his donor, but the bestowed is known (hence the "secret Santa"). The cost of gifts is usually stipulated in advance so that all gifts are approximately equivalent. If you wish, you can agree that after the exchange of gifts is completed, the donors will open.

His "Secret Santa" is also on Habrahabr called "Club of Anonymous Santa Clauses" .

Unfortunately, for the organization of the Secret Santa simply generate a list of pairs of donor-donated enough. Donations should be made anonymously, and each participant should know only the number of the donated and not a bit of information about other participants, so, for example, you cannot simply assign one of the participants to generate a list and inform each remaining participant of his donor - the one who generated the list will know everything about everyone, including your donor.

As a rule, participants get out of the situation by resorting to the help of a "third party" - a disinterested person who is not participating in the ceremony, who is asked to generate the numbers of the presented gifts and secretly inform each participant of a single number. Such a "third party" can be not only a person, but also a specialized website, among which is the already mentioned "ADM Club" Habrahabra.

If we put the condition of decentralization (the absence of a "third party"),
then "Secret Santa" turns into an interesting problem from the point of view of cryptography, well-studied and repeatedly solved: here is an example of the mathematical model of Secret Santa , and here is a specific solution algorithm , where participants use asymmetric encryption to ensure data hiding.

In this article I will describe another such algorithm. Its slight advantage over other methods from the field of hardcore cryptography is that it is very simple to perform: all that participants need to do is to write down sets of positive integers, as well as cross out individual elements from them and enter new ones.

Like the other decentralized algorithms for the Secret Santa, this algorithm does not require a "third party" - the participants need only communicate with each other. All that is required for each participant is to receive a set of natural numbers from the participant with the previous number twice, change it in a certain way and pass on to the next one. After the exchange of sets is completed, each participant in a certain way generates from the sets in his possession a single natural number - the number of the gift given.

I’ll say right away that this approach doesn’t have many advantages compared to simply attracting a “third party”, but there are still a couple of advantages:

• It's just fun to play NG in Secret Santa with cryptography. Well suited company geeks.
• It is not required to look for a person from the outside, to organize his communication with each of the participants.
• You do not need to register on any site, you need only the participants themselves and a minimum of technical means of communication in plain text. In the physical meeting of the participants do not need anything but a pen and paper. To communicate at a distance, anything is suitable - email, SMS, IRC ...

Algorithm Description

For a start, a small agreement on how to present a specific set, matching donors and donors, from a mathematical point of view.

Assigning gifts to the Secret Santa is nothing more than assigning a number from 1 to N to each of the participants in a group of N people, meaning the number of the presented gift (assuming that all participants are numbered from 1 to N). Wherein:

• No one should get their own number (it’s not allowed to give to yourself);
• There should not be numbers that have not been lost to anyone (all should be gifted);
• The number of each participant goes to exactly one donor (each must receive exactly 1 gift).
• Two participants may fall to give gifts to each other - in principle, this is perfectly normal, but sometimes the participants may agree to transfer lots in this case.
• Other additional restrictions may be imposed on the numbers, depending on the situation (for example, if several families are involved in Santa, they may agree to transfer lots if someone from the participants is given a gift to a member of his family).

This shows that any list of couples donator-donated for Secret Santa can be represented as a sequence of N numbers (the i-th place is the number of the person to whom the i-th member gives a gift), which is a permutation of order N without fixed points.

The first stage of the algorithm

So, each participant is assigned a number from 1 to N, for example, in alphabetical order of names. This information is public and communicated to all participants.

Then the first participant randomly creates a large set (at least 2N needed) of natural numbers so that no 2 of them match. This set is not initially communicated to anyone. The first participant writes these numbers for convenience in ascending order, selects any one of them randomly, deletes the selected number from the set and transfers the remaining set to the second participant. As a result, the first participant has 2 things recorded: the starting set of numbers and the number chosen by him.

Let's give an example with 5 participants.

The first participant generates the initial set: 3, 46, 50, 89, 94, 95, 101, 500, 783, 5003, 5765, 7003

Selected: 783
Transferred to the second participant: 3, 46, 50, 89, 94, 95, 101, 500, 5003, 5765, 7003

In the same way, the second participant chooses an arbitrary number from the set, removes it from the set and transfers the remaining set to the next participant. The 3rd, 4th and 5th participants do the same. Fifth, the last, the participant chooses a number for himself, but does not transmit anything to anyone yet.

Let's continue the example:

The second participant receives (we repeat): 3, 46, 50, 89, 94, 95, 101, 500, 5003, 5765, 7003
Second participant chooses: 3

The third participant receives: 46, 50, 89, 94, 95, 101, 500, 5003, 5765, 7003
The third participant chooses: 94

The fourth participant receives: 46, 50, 89, 95, 101, 500, 5003, 5765, 7003
The fourth participant chooses: 5765

The fifth participant receives: 46, 50, 89, 95, 101, 500, 5003, 7003
The fifth participant selects: 101

Residue of the set: 46, 50, 89, 95, 500, 5003, 7003

The first stage of the algorithm is over. Comment: as a result, each of the participants has a number that is not known to everyone else (more precisely, each participant knows a large set of numbers, about which he knows that subsequent participants chose their number from him - but this does not provide any information that allows you to know exactly who are you. numbers). If we now find a way to somehow communicate the entire set of selected numbers to each of the participants, then the task of assigning donors will be solved: each participant only needs to take the number of the selected number in this set of selected numbers as the final result.

Suppose that we have already found a way to tell everyone a set of selected numbers (in general, we will do this at the 2nd stage of the algorithm) and the participants learned the numbers of their presented numbers. The problem is that one or more participants may get their own numbers, which makes the whole final result incorrect. This is a big minus of the algorithm, since the probability of getting into this situation is quite high, although it falls with an increase in N. There are at least 2 outputs:

• A participant who has received his own number requests all to transfer lots from the beginning. This procedure must be repeated until everyone confirms that they got the correct number.

  
  
• A participant who has received his own number asks all to apply a random permutation without fixed points to the final results. This permutation is generated openly and reported to all participants. Each participant must apply this permutation to the number of its donated. This procedure must be repeated until everyone confirms that they got the correct number. This method is suitable only for a physical meeting, since with remote communication it is impossible to guarantee the randomness of a permutation (whoever is asked to generate a permutation, for example, can freely generate a permutation that converts his gift number to any other gift number he wishes).

In the example with 5 participants, this is how the selected numbers will look like:

1st participant picked (repeat): 783
2nd participant chose (repeat again): 3
3rd party chose (repeat again): 94
4th participant chose (we repeat): 5765
5th participant chose (repeat again): 101

The list of selected numbers in ascending order (I repeat - suppose that we know how to secretly communicate it to all participants): 3 94 101 783 5765

Total numbers donated:

1st participant: chose 783, set 3 94 101 783 5765 - number of the gift 4
2nd participant: chose 3, set 3 94 101 783 5765 - the number to be donated 1
3rd participant: chose 94, set 3 94 101 783 5765 - the number to be presented 2
4th participant: chose 5765, set 3 94 101 783 5765 - number to be donated 5
5th participant: chose 101, set 3 94 101 783 5765 - number to be endowed 3

Flipping is not required.

The second stage of the algorithm

So, how do you tell everyone a set of "dedicated" numbers? This is the task of the second stage. The first participant can find out this set if the last participant tells him the remaining set at the end (in the example it is 46, 50, 89, 95, 500, 5003, 7003). The first participant then needs to exclude this set from the starting one, and the result of the exclusion will be the desired set of numbers selected by the participants. Note that the first participant with such an action still does not know any information that allows him to disclose the numbers inherited by the other participants.

Unfortunately, it is impossible to simply take and report a calculated set further down the chain - if only because the penultimate participant will instantly calculate the number selected by the last participant from this information, and therefore recognize its intended user.

The solution to this problem is as follows. As already mentioned, the last participant sends the first remaining set to the first one. The first participant has the following data:

Starter set: 3, 46, 50, 89, 94, 95, 101, 500, 783, 5003, 5765, 7003

Selected number: 783

The last remaining set: 46, 50, 89, 95, 500, 5003, 7003

The first participant calculates, as already mentioned above, the set of numbers selected by all participants: 3, 94, 101, 783, 5765 and recognizes the number of the gift given to him - 4.

Now, from this point on, each participant, starting from the first, will inform the next participant a set of N numbers. Everyone who receives such a set should consider it as the set of numbers selected by all participants and, accordingly, calculate the number of their gift. But at each step, the next set will not be the original set of selected numbers, but the modified one, but giving the same result of calculating the number of the presented one as the original one. At the same time, the modified set will exclude any possibility to find out the numbers chosen by others.

To compile such a modified set, the participant must take the set he received from the previous participant (in the case of the first participant, the set calculated as above) and replace his number (selected at the 1st stage) with any other number he received at the 1st stage set, with the following restrictions:

• The replaced number should not be included in the set just received from the previous participant;
• The replaced number must have the same sequence number in the modified set as the replacement number in the original set.

In the example, the first participant substitutes in the set 3, 94, 101, 783, 5765 the number he chooses - 783. The numbers that he is allowed to substitute for 783 are 500 and 5003. Suppose he chose the substitution 783 for 5003 and passes the set to the second participant 3, 94, 101, 5003, 5765.

The remaining members do the same. Let's finish the example.

Second participant:
Set at the 1st stage - 3, 46, 50, 89, 94, 95, 101, 500, 5003, 5765, 7003
Selected number - 3
Set on the 2nd stage - 3, 94, 101, 5003, 5765

You can substitute 3 - 46, 50, 89
We choose to substitute 50, we pass on a set of 50, 94, 101, 5003, 5765

Third party:
Set at the 1st stage - 46, 50, 89, 94, 95, 101, 500, 5003, 5765, 7003
Selected number - 94
Set on the 2nd stage - 50, 94, 101, 5003, 5765

You can substitute instead of 94 - 89, 95
We choose to substitute 89, we pass on a set of 50, 89, 101, 5003, 5765

Fourth participant:
Set on the 1st stage - 46, 50, 89, 95, 101, 500, 5003, 5765, 7003
Selected number - 5765
Set on the 2nd stage - 50, 89, 101, 5003, 5765

You can substitute instead of 5765 - 7003
We choose to substitute 7003 (there are no special alternatives), pass on the set 50, 89, 101, 5003, 7003

Fifth participant:
Set at the 1st stage - 46, 50, 89, 95, 101, 500, 5003, 7003
Selected number - 101
Set on the 2nd stage - 50, 89, 101, 5003, 7003

The exchange of sets is completed, participants can do the calculation of the number of the donated person.
You can make sure that none of the participants with this approach can learn anything about other people's numbers.

Everything, the algorithm is complete. Offhand, I see 2 more flaws in it, in addition to the frequent redeployments mentioned above because of the chance for a participant to drop its own number:

• The randomness of the choice of a number from a set is not guaranteed. No one bothers the first participant, for example, to choose the last number in the set and thus practically ensure that the number donated equals N. This problem is eliminated if, as already mentioned, the participants agree at the very end of the algorithm to additionally apply to the results a random permutation known to all without fixed points, but its randomness must also be somehow guaranteed.

  
  
• The algorithm does not know how to create any additional restrictions on the numbers given (for example, prohibiting any 2 participants or certain 2 participants from mutually making a gift to each other).

Thank you all, who read to the end, and Happy New Year :) A cookie to someone who finds more problems in the algorithm or solves existing ones!