4

Just like picking one of the papers in a bowl is used to anonymously distribute a given set of numbers among individuals which lets nobody (including the person who distributes them) know who got what. Is it possible to achieve the same with cryptography.

The requirements in a setup where there is 1 distributor and "n" receivers are

  1. The distributor creates "n" number of random keys of a big enough size so as to prevent the receivers from easily guessing them.
  2. Each receiver should only get one key.
  3. The receivers are only aware of their key and not that of others. The distributor is just aware of the list of keys but doesn't know who got what after the distribution.
zokaria
  • 41
  • 3
  • 1
    Your question lacks clarity regarding the confidentiality of the number or the privacy of individuals' identities. If you foucs on the confidentiality, then you can employ distributed encryption schemes or mix-net to achieve your requirement. And if you are concerned about anonymity, then things can get a bit tricky in this setting. In the context of anonymity, you should consider at least three extra secure requirements: non-repeatability (which means the party cannot get more than one number), authentication (the party is validity) and openability (ensure the ownership of numbers). – ming alex Nov 07 '23 at 07:20
  • 1
    Trying to formalize your question a bit, I'd assume your goals are that (1) the numbers from 1 to $n$ should be distributed among $n$ participants so that everyone gets a different number; (2) no participant should be able to control which number they or anyone else gets (more strongly: each permutation of the $n$ numbers should be equally likely and no single participant should be able to change the probability of any permutation); and (3) each participant should only learn which number they receive, not what anyone else receives. Does this look about right? – Ilmari Karonen Nov 07 '23 at 10:47
  • (Ps. All of the above is assuming no collusion between participants, although more generally it would probably also be desirable if a subset of colluding participants could not learn or change anything that they could not anyway learn or change just by comparing and possibly exchanging their respective numbers after the distribution has been done. Let's call this goal (4).) – Ilmari Karonen Nov 07 '23 at 10:48
  • You can try to frame it as a secure multiparty computation (MPC) task as the following ideal functionality F which takes no input and outputs $k_i$ to receiver $i$ and outputs $k_{\pi(1)},\dots,k_{\pi(n)}$ to the distributor. This is achievable with standard techniques and also the best you can hope for. For example, for your third point, the distributor can team up with half of the receivers and narrow down the keys of the other receivers to a set of size $n/2$ instead of $n$. – lamontap Nov 08 '23 at 16:29

1 Answers1

2

You can use some sort of message flooding protocol to hide the origin.

  1. Everyone establishes peer-to-peer communication with everyone else and starts forwarding received messages to everyone else.

  2. Each party creates a commitment ballot and introduces it into circulation. Because everyone is forwarding everyone else's messages, new messages can be brought into circulation without revealing the origin.

  3. Once there are exactly N ballots in circulation, each party confirms (in the clear) that his ballot is on the list, without telling which one it is. If one party introduced more than one ballot, it will be detected at this point. We don't know who produced two ballots and we cannot recover from the situation, but at least we can detect it and abort.

  4. If all parties have certified the list, everyone reveals his ballot's secret in another round of message flooding. The parties don't know who revealed which secret because everyone still forwards everyone else's messages and new messages are introduced slowly and randomly into the message flood.

  5. Once all secrets have been revealed, a permutation is calculated from the revealed secrets and applied to the list. Everyone then knows his own position on the sorted list, but not the other parties' positions.

Pros

  • No central authority required.

Cons

  • Needs peer-to-peer connections between all parties.
  • Vulnerable to denial of service attacks. A malicious party can introduce two commitment ballots, causing the protocol to abort.
  • De-anonymization is possible through collusion between participants or large-scale eavesdropping at network provider level.
Rainer P.
  • 121
  • 2
  • 2
    Can you clarify step 4? Would revealing ballots not allow everyone to see which position everybody else occupies? – tucuxi Nov 07 '23 at 11:21
  • 2
    Much better now. I understand that commitment ballots could be something like SHA3(secret), so that secrets revealed in step 4 can be matched to commitments. – tucuxi Nov 07 '23 at 11:32
  • 1
    This does not distribute "random keys of a big enough size so as to prevent the receivers from easily guessing them", while maintaining their confidentiality. – fgrieu Nov 07 '23 at 15:18