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&lt;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.
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 mental-poker.

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


Everyone generates a random encryption key.
Everyone but Alice uses their key to encrypt their secret unique number.
Alice uses her key to encrypt every item in the list $[0,...,x]$, except her own number. She then shuffles the list.
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.
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.
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:


Alice: key $a$, Bob: $b$, Eve: $e$
Bob: $E_b(52)$, Eve: $E_e(193)$
Alice: $[E_a(0), ... E_a(17), E_a(19), ... E_a(200)]$, shuffle.
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)))$.
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)))$.
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.