Choose a random number that is different from a bunch of other secret numbers

I'm looking for an algorithm where n participants each have a different secret number between $[0..x]$ (and where $x$ is known) and where the participants then select randomly another, non-secret, number between $[0..x]$ which must not clash with the secret of any participant and which must not reveal any number used by any participant.

That each participant has a secret number and that no two participants have the same number is a given.

Proofs that participants are acting honestly is not necessary. You can assume that the parties are semi-honest (i.e., they will not deviate from the protocol).

So, for example (this part I'm not interested in):

• Alice has the number $18$
• Bob has the number $52$
• Eve has the number $193$

At this point each participant knows:

• its own number
• that each participant has a different number
• that each participant knows only its own number

Considering that as our starting point, now Alice, Bob and Eve have to reach a consensus allowing to pick randomly one (and only one) public number between $[0..200]$, which does not clash with any of the three private numbers, without revealing any information about the private/secret number of any participant.

Is there a practical algorithm allowing to do this? By "practical" I mean something that can be used today and that would run in very reasonable times.

Maybe some homomorphic scheme?

You can assume that $x$ will be small and $n<x$, but unfortunately $n$ will be large enough that a random number will have a significant probability of clashing with some participant's secret number. In other words, $n/x$ is a relatively large fraction.

-
"Proofs that participants are acting honestly is not necessary." - Do you mean adversaries are assumed to be semi-honest, or that simulatability is not required? $\;$ –  Ricky Demer Jun 17 at 16:34
For practical applications, how large will $x$ be? Can the "not clash" guarantee be probabilistic? In other words, if $x>>n$ (where $n$ is the number of participants), with very high probability, a randomly generated value will not clash. If that is sufficient for your needs, then a multi-party random number generation algorithm would suffice. –  mikeazo Jun 17 at 16:37
@RickyDemer: I mean that it's not necessary "inside" the crypto system because there are, in my use case, other means to verify that the participants have been honest after the "vote". For example picking the private/secret number and then participating in choosing a random public number is all done using a seed to a CSPRNG. A non-malleable commitment to that seed can be published (hence not revealing the seed) and then, say a few days later, everybody can release their seed. (if someone doesn't, the vote isn't valid). –  Cedric Martin Jun 17 at 17:27
@mikeazo: x will be small, between 40 and 60 or something. The number of participant will not be very high, but high enough so that clashes are to be expected very often. –  Cedric Martin Jun 17 at 17:32
@RickyDemer: Basically I need the secrets to stay secrets only for a small amount of time but during that amount of time they need to be really secret. After a while everything can be published publicly. Which is convenient because is probably simplifies the implementation (for example by not requiring adding ZKNP etc.). –  Cedric Martin Jun 17 at 17:35

5 Answers

I think this would work, although whether it's practical is another matter. For large $x$ it won't be. It's basically an application of .

First, choose a secure commutative encryption algorithm that is not vulnerable to known plaintext or chosen ciphertext attacks.

1. Everyone generates a random encryption key.

2. Everyone but Alice uses their key to encrypt their secret unique number.

3. Alice uses her key to encrypt every item in the list $[0,...,x]$, except her own number. She then shuffles the list.

4. Everyone passes their encrypted secret number/list to the next person (e.g. clockwise), who encrypts it, shuffling the list when they have it. Repeat until all the numbers and the list have been passed around. At that point both Alice's list and everyone else's number has been encrypted by everyone.

5. Remove all the encrypted numbers from the list. Since the encryption is commutative, each encrypted number will match itself in the list, but because everyone has shuffled the list, they don't know what those numbers originally were.

6. Pick the first number from the list. Have everyone decrypt it with their key and pass the result around, until they've made a whole round. Now everyone should have the same random number, which they can verify by comparing their results.

(If the number would only be decrypted once, the final decrypter could cheat and pick any number, hoping it doesn't match the others'.)

I.e. with your example values:

1. Alice: key $a$, Bob: $b$, Eve: $e$
2. Bob: $E_b(52)$, Eve: $E_e(193)$
3. Alice: $[E_a(0), ... E_a(17), E_a(19), ... E_a(200)]$, shuffle.
4. Alice $\mapsto$ Bob: $[E_a(i), ...]$, Bob: $[E_b(E_a(i)), ...]$, shuffle.

Bob $\mapsto$ Eve: $E_b(52)$, Eve: $E_e(E_b(52))$.

Eve $\mapsto$ Alice: $E_e(193)$, Alice: $E_a(E_e(193))$.

Alice $\mapsto$ Bob: $E_a(E_e(193))$, Bob: $E_b(E_a(E_e(193)))$.

Bob $\mapsto$ Eve: $[E_b(E_a(j)), ...]$, Eve: $[E_e(E_b(E_a(j))), ...]$, shuffle.

Eve $\mapsto$ Alice: $E_e(E_b(52))$, Alice: $E_a(E_e(E_b(52)))$.

5. Now the list, $E_a(E_e(E_b(52)))$ and $E_b(E_a(E_e(193)))$ can be revealed and the Bob and Eve's numbers removed. Since the encryption is commutative, $E_a(E_e(E_b(52)))$ will match $E_e(E_b(E_a(52)))$ somewhere in the list, as will $E_b(E_a(E_e(193)))$.

6. Everyone takes the first number in the list, say $E_e(E_b(E_a(42)))$. They each decrypt it, e.g. Bob: $D_b(E_e(E_b(E_a(42)))) = E_e(E_a(42))$. They pass them around like in step 4, so that eventually e.g. Bob gets $E_b(42)$, which he can decrypt and announce, comparing to Alice and Eve's results.

-
@D.W., I've moved the math into a full blown example, which I think will be clear. Who does the removal doesn't matter – they don't really have to be removed, everyone can just pick the first number in the list that matches none of the encrypted secrets, all of which are public at that point. –  otus Jun 25 at 9:08
Very nice! Thank you for elaborating. This looks to me like the best answer I've seen. –  D.W. Jun 25 at 17:38
@D.W: (and otus) yup this is very nice and I'm pretty sure that it solves my issue. Now as I don't want a TTP I'll need to find a way to implement that answer of yours without a TTP. I'll read the link you provided and then probably come up with another question! –  Cedric Martin Jun 25 at 17:57
@CedricMartin, you are aware that this scheme (from otus) doesn't require a TTP, right? –  D.W. Jun 25 at 18:02
@CedricMartin, the standard commutative encryption algorithms (e.g., Pohlig-Hellman) do not require a TTP to hold any keys. The prime $p$ is public and shared by everyone; each participant's exponent is secret and is their key and is generated by them and known only to them. No TTP is needed. If you have questions how to use commutative encryption in practice, I suggest reading the existing questions, then posting a new question if it's not covered by the ones that are already on this site. –  D.W. Jun 25 at 22:56

Here is a quick idea that came to mind:

$n$ be the number of participants. Let $p := 0.5 / n$.

Have every participant choose a number not equal to his own, and announce it publicly. After all the numbers were announced, each participant answers with no, if one of the announced numbers match their private one or if a random Bernoulli experiment with sucess probability of $p$ gives a success. Otherwise announce yes.

The probabilities are chosen, such that at least 50% of the time there is at least someone who says no to the announced numbers. If everyone says yes, the chosen numbers are ok.

Now, I realise that there would be an attack, where someone could probe the network by repeadelty announcing the same numbers to see if the same people say no. Depending on $x$ and $n$ this could be circumvented by never saying yes to any number one has already said no to.

Alternatively, this could be done one number at a time, as to not burn as many numbers for every no. So generate a number for participant 1, vote on it, reroll or go to participand 2.

Then again, this might not be applicable to "without revealing any information about the private/secret number"

Another idea I had was to see if one could use the Socialist millionaire problem.

-
I mean the "secret number between [0..x]". $\:$ I also notice that the probability I mentioned is not relevant, since an adversary would have a larger probability even if the functionality described in the opening post was performed by a trusted party. $\:$ However, for n=2 and x=3 (the simples non-trivial case), if the adversary's secret number is 2 and the honest party's secret number is either 0 or 1 and the $\:$ (continued ...) $\;\;\;\;$ –  Ricky Demer Jun 17 at 21:09
(... continued) $\:$ functionality is performed by a trusted third party then that guarantees choosing a non-clashing number and the adversary has only a half change of learning the honest party's secret number, but if your idea is repeated enough to have a sufficiently large probability of choosing a non-clashing number then the adversary has greater than a 5/6 change of learning the honest party's secret number. $\;\;\;\;$ –  Ricky Demer Jun 17 at 21:10
This is not a great scheme. The problem is that any time a participant vetos a candidate random number, everyone learns what that participant's secret number was (it must have been the same as the candidate random number we were considering). See my answer for a scheme that is a bit better, because it doesn't reveal which participant vetoed the candidate. –  D.W. Jun 24 at 18:32

What you're looking for is that zero knowledge proof, that some public number is not equal to a couple of secret numbers.

It is possible to prove that two numbers are not equal, but it is not that easy to do so, and it is mostly theoretic work. Let's consider two integers $a$ and $b$ for simplicity and prove their inequality:

P.S. There are also, for example, ZK proofs for commited values being in a certain range. For example, Camenisch et al. Efficient Protocols for Set Membership and Range Proofs. Additionally, since you dropped the word "vote" in a comment, you should have a look at Groth's Non-interactive Zero-Knowledge Arguments for Voting, where such a technique is already used in a voting scenario.

-
Hm, you're right about that, there is a ZK proof. But even thinking about it makes my head hurt... I'll change my answer accordingly, and add how to go about it. –  tylo Jun 24 at 8:24
Thanks, nice edit! Here's one more intereseting fact. Proving that two numbers are different can actually be done efficiently, using the proper scheme. See my answer (you use a scheme that is homomorphic for 2-DNF formulas, noticing that $C$ computes a 2-DNF formula). –  D.W. Jun 24 at 18:14

Yes, this should be solvable and should be doable in a reasonable amount of computation time, using a pretty cool homomorphic cryptosystem.

Here is one approach: the participants jointly pick a random number $y$, publicly commit to $y$, and then they all prove/check in zero knowledge that $y$ is different from their numbers. If it isn't, they go back to the beginning and try again, until they have found a choice that differs from all their numbers.

The zero-knowledge proof part can be made efficient using the following paper:

Boneh, Goh, and Nissim build a public-key encryption algorithm $E(\cdot)$ that allows you to evaluate any 2-DNF formula on encrypted values. In other words, if you have $E(x_1),\dots,E(x_m)$, where $x_1,\dots,x_m$ are boolean values, and if you have a 2-DNF formula $\Psi$, then you can compute $E(\Psi(x_1,\dots,x_m))$ from $E(x_1),\dots,E(x_m)$. The computation can be done quite efficiently. This is a very cool kind of homomorphic property, and it is very useful here.

In particular, if we have two numbers $y,z$, notice that the condition $y \ne z$ is a 2-DNF formula on the bits of $y,z$: $y\ne z$ is equivalent to

$$(y_1 \land \neg z_1) \lor (\neg y_1 \land z_1) \lor \dots \lor (y_\ell \land \neg z_\ell) \lor (\neg y_\ell \land z_\ell),$$

where $y_i$ is the $i$th bit of $y$ and $z_i$ the $i$th bit of $z$.

Moreover, if we have $n+1$ numbers $y,z_1,\dots,z_n$, and the ciphertexts of each bit of each number were encrypted separately using the Boneh-Goh-Nissim, we can check the condition $(y \ne z_1) \land \dots \land (y \ne z_n)$. Here is how. Let the bit $b_i$ be $1$ if $y \ne z_i$, and $0$ otherwise. Notice that we can compute $E(b_i)$ and the encryptions of the bits of $y,z_i$, using the ideas above and the homomorphicity of $E(\cdot)$. Define $k=b_1+b_2+\dots+b_n$. Notice that we can also compute the ciphertext $E(k)$ from $E(b_1),\dots,E(b_n)$, by the homomorphism properties of $E(\cdot)$. Now the condition $(y \ne z_1) \land \dots \land (y \ne z_n)$ holds if and only if $k=n$. Thus, to check the condition, we can decrypt $E(k)$ and check whether we get $n$ or not.

In addition, in the case where we know $z_1,\dots,z_n$ are distinct, the procedure does not reveal anything about the underlying $z_1,\dots,z_n$, beyond whether $y$ is equal to one of them. That's because $k$ will be either $n$ or $n-1$; it will be $n$ if $y$ is different from all of them, or $n-1$ if $y$ is equal to one of them. So the decryption of $E(k)$ does not disclose anything beyond whether $y$ is equal to one of the $z_i$'s (and if it is, it does not disclose which $z_i$ it is equal to).

Therefore, we immediately obtain a solution, using a threshold version of the Boneh-Goh-Nissim scheme:

1. The parties jointly generate a public/private keypair for the Boneh-Goh-Nissim cryptosystem, such that each party ends up with a share of the private key, no party (or coalition of parties) knows the private key, and everyone knows the public key. Their paper describes how to do that. This only needs to be done once.

2. Each party writes his/her private number in binary notation, separately encrypts each bit with the Boneh-Goh-Nissim cryptosystem, and then publishes all of those ciphertexts. In more detail, call party $i$'s secret number $z_i$. Write it in binary as the bits $z_{i,1},\dots,z_{i,\ell}$, then publish $E(z_{i,1}),\dots,E(z_{i,\ell})$, where $E(\cdot)$ represents Boneh-Goh-Nissim encryption under the public key established in step 1. Each party separately does this. This is also a one-time step that never needs to be repeated.

3. The parties now jointly generate a random number $y$, using standard methods. They encrypt each bit of $y$ separately, using the Boneh-Goh-Nissim scheme. (For instance, you can have one party do the encryption and then prove that he/she did it correctly.)

4. Now, check whether $y$ is equal to any of $z_1,\dots,z_n$. This can be done using the techniques described above. They can all compute $E(k)$, then they use the threshold decryption procedure to jointly decrypt $E(k)$ and learn $k$. The value of $k$ (either $n$ or $n-1$) reveals whether $y$ is different. If $y$ is different, they are done, and they output $y$. Otherwise, they go back to step 3 and try again.

How long will this procedure take? If there are $n$ parties, and the range of values covers $x$ possible values, then each iteration has a $1 - n/x$ probability of success and a $n/x$ probability of leading to a retry. Therefore, on average we need to retry $x/n$ times. For instance, if you're trying to pick a random number from $[0..200]$, then as long as there are no more than 100 parties, on average only 2 iterations are needed.

How much side information is disclosed? None of the parties ever discloses their secret number. However, any time we have to retry the procedure, an eavesdropper does learn that the number $y$ we were using must be the secret number of one of the parties (but the eavesdropper doesn't learn which party it was). This is a downside. This downside can be removed using more sophisticated methods (e.g., a way for the parties to jointly choose the random number $y$ without any of them knowing the value of $y$, but they all know the encryption of the bits of $y$), if you care.

As DrLecter helpfully points out:

BGN requires pairings over composite order bilinear groups (which are terribly slow to work with), [so] it may be worth to mention Freemans' product group approach, that among others allows to transfer BGN into a prime order setting and nicely increases performance by several orders of magnitude.

-
+1. As BGN requires pairings over composite order bilinear groups (which are terribly slow to work with) it may be worth to mention Freemans' product group approach, that among others allows to transfer BGN into a prime order setting and nicely increases performance by several orders of magnitude. –  DrLecter Jun 24 at 19:37

If you trust all the participants to behave (semi-)honestly, here is another scheme that can be used and is a bit simpler. The basic idea is:

1. The $n$ participants jointly generate a random number $y$ from the desired range (e.g., $[0..x]$). They publish $y$ amongst themselves.

2. Now they each have a chance to veto that choice of $y$. Each participant privately checks whether $y$ is equal to their own secret number. If it is, they veto this choice of $y$; otherwise, they don't veto it. We execute a distributed protocol to see whether any participants wants to veto it, in a way that only reveals whether anyone is vetoing without revealing who.

The first step can be done through standard methods.

Given (semi-)honest participants, the second step can also be done, using homomorphic cryptography. Let's assume $E(\cdot)$ is an additively homomorphic threshold public-key cryptosystem (you can also use a multiplicatively homomorphic scheme). Here is the distributed protocol for veto-ing:

1. Party $i$ chooses a number $t_i$ as follows. If party $i$ wants to veto, she chooses $t_i$ to be a large random number (actually even $t_i=1$ would also work). If party $i$ does not want to veto, she chooses $t_i=0$.

2. Party $i$ encrypts $t_i$ to obtain the ciphertext $E(t_i)$, and then publishes $E(t_i)$ to all the other participants.

3. Everyone can compute $c=E(t_1+t_2+\dots+t_n)$, using the homomorphic property of $E(\cdot)$.

4. The parties use the threshold decryption operation to jointly decrypt $c$, obtaining some plaintext. If the decrypted plaintext is zero, then no one wants to veto (and we can use the random number $y$ that was selected). If the decrypted plaintext is non-zero, then someone wants to veto (and we'll have to choose a new random number $y$), but no information is revealed about who wanted to veto.

This requires the parties to once, in advance, jointly generate a private/public keypair for $E(\cdot)$ so that they each have a share of the private key, and it requires all $n$ of them to agree to be able to decrypt.

This procedure requires on average $x/n$ iterations, if you are choosing $y$ from a space of $x$ possible values.

This protocol does not disclose any participant's secret number, but if you ever retry, an eavesdropper (and the participants) do learn that the chosen value $y$ must have been one of the participant's secret numbers, which is a downside.

-