0
$\begingroup$

I am trying to think of a way to generate secret and unique random numbers within a range.

Say we have a public range [1-n], how could we have a maximum of n users choose a random number within this range and ensure that no one else chooses the same number.

The difference between this question and others is that we want to keep the chosen number a secret this time.

It would be okay to have a third party facilitate the process, however, I would still like the third party to not learn anything about the final number generated for the user.

Is this feasible?

$\endgroup$
  • $\begingroup$ How many numbers are you wanting? One in total or one per user? $\endgroup$ – Paul Uszak Mar 2 at 16:11
  • $\begingroup$ I would like it to be one per user. $\endgroup$ – user101 Mar 2 at 16:16
  • $\begingroup$ What are you planning to do with these numbers once you have assigned them? $\endgroup$ – Squeamish Ossifrage Mar 2 at 20:14
1
$\begingroup$

A first cursory reading suggests that a format-preserving cipher like NIST SP 800-38G FF1, which makes an easy way to pick permutations of odd-sized blocks with short keys, might help. But you asked that nobody learn anything about the final number generated by the user. Here's a simple-minded protocol with approximately five minutes of effort put into it. Maybe if you put more effort into it you could find a secure multiparty computation that doesn't require a trusted third party.

Pick an authenticated cipher $E_k$ like crypto_secretbox_xsalsa20poly1305. Pick a DH function $(a, P) \mapsto [a]P$ with standard base point $B$, like X25519. Enlist the help of a dealer Dale and an independent trusted third party Trent.

  1. Each user generates secret scalar $p_i$ and publishes $P_i = [p_i]B$.
  2. Dale picks a permutation $\pi$ of $\{1,2,\dots,n\}$ uniformly at random. (You could use FF1 for this, but you might as well just do a Knuth shuffle unless $n$ is so gigantic this protocol isn't feasible anyway.)
  3. Trent picks a permutation $\tau$ of $\{1,2,\dots,n\}$ uniformly at random.
  4. For each $i$, Dale picks a blinding factor $b_i$ uniformly at random and sends $P'_i = [b_i] P_i$ and $\pi(i)$ to Trent. Dale should make sure to send these messages to Trent in the order given by $\pi$.
  5. On receipt of $P'_i$ and $\pi(i)$, Trent computes $u_i = \tau(\pi(i))$, picks $q_i$ uniformly at random, computes $k_i = H([q_i]P'_i) = H([p_i q_i b_i]B)$, computes $c_i = E_{k_i}(u_i)$, and returns $Q_i = [q_i]B$ and $c_i$ to Dale.
  6. Dale sends $Q_i$, $b_i$, and $c_i$ to the corresponding user, encrypted with their respective public key the usual way if need be.
  7. Each user computes $k_i = H([p_i b_i]Q_i) = H([p_i q_i b_i]B)$ and opens $c_i$ with $k_i$ revealing their unique number $u_i$.

In this protocol:

  • Each user learns only their own number $u_i = \tau(\pi(i))$: without knowledge of $\tau$ or $\pi$, which are independent uniform random permutations, they can't invert $\tau$ or $\pi$; and without the other users' secret keys or blinding factors $b_i$ they can't decrypt any traffic over the channels between Dale, Trent, and the other users even if eavesdropped.
  • Dale, knowing only $\pi$, $P_i$, $b_i$, $Q_i$, and $c_i$, can't compute any $u_i$ without knowledge of $p_i$, $q_i$, $\tau$, or $k_i$: the number is chosen by a uniform random permutation $\tau$ known only to Trent, and encrypted with the user's public key $P_i$ using an ephemeral key pair $(q_i, Q_i)$ known only to Trent and a secret session key $k_i$ shared only by Trent and the user.
  • Trent, knowing only $\tau$, $P'_i$, and $\pi(i)$, can't compute $i$ or which $P_i$ the blinded key $P'_i$ corresponds to without knowledge of $\pi$ or $b_i$, and so can't tell which user $i$ gets $u_i$: the number $\pi(i)$ is chosen by a uniform random permutation $\pi$ known only to Dale, and the public key $P'_i$ is blinded with the uniform random secret $b_i$ known only to Dale.

CAVEAT CRYPTATOR: I'm a pseudonymous bird on the internet and scratched this out without review or careful thought about it.

$\endgroup$
  • $\begingroup$ So are the parties involved me (a user knowing $i$ and $u_i$), Dale (knowing neither $i$ nor $u_i$),and Trent (knowing $u_i$ but not $i$)? What constraints are put on users or the other two? Do users need to be pre-assigned $i$ values? Can user $i$ spoof user $j$ and learn $u_j$? $\endgroup$ – Future Security Mar 2 at 19:05
  • $\begingroup$ The assumption is that Trent and Dale have a known-good telephone book assigning to each user a public key in sequence, for example the order in which the users scrawled their names in the telephone book in crayon. $\endgroup$ – Squeamish Ossifrage Mar 2 at 20:13
  • $\begingroup$ If Dale and Trent collude, they can identify the relationship of users and their corresponding numbers. $\endgroup$ – user101 Mar 11 at 22:56
  • $\begingroup$ @user546 Yes. This is why I used the word independent, and even highlighted it in italics. $\endgroup$ – Squeamish Ossifrage Mar 11 at 22:57
0
$\begingroup$

Use a PRP (pseudorandom permutation) with an input/output range of $[0, n - 1]$.

Things are just easier when we start at zero. Add 1 if you want. Or apply whatever injective function you want, say base-64 encoding, to transform a number into an identifier of whatever format you want.

One could use AES as a 128-bit permutation. (But any good block cipher works.) It has a 128-bit input, a 128-bit output, and it's bijective. You put in an integer from the range $[0, 2^{128}-1]$ and get an output $[0, 2^{128}-1]$.

If you were to calculate the sequence

$$\mathrm{AES}_k(0), \mathrm{AES}_k(1), \mathrm{AES}_k(2), \dots, \mathrm{AES}_k(2^{128}-1)$$

Then you get a sequence of each number in the range $[0, 2^{128}-1]$ appearing exactly once. The sequence is indistinguishable from a randomly chosen shuffling of the numbers from that range. (If the key is secret and chosen from a unfirom distribution, then it is so by the definition of a PRP.)

If you use a PRP then the only state you need to maintain is a counter and a secret key.


The challenge is finding a PRP on a set of the size you want. Normally block ciphers operate on a range which is a power of two.

The solution is to look at "format preserving encryption" methods. It's quite easy to make a smaller block cipher from a large one. Use a Feistel structure, pick a PRF, split the input bit sequence in half, use four rounds with a different key for each round.

Non-power of two ranges for format preserving encryption are most easily acheived by using cycle walking.


Alternatively, if you've got space free to store a list of $n$ numbers, then you can just use the Fisher-Yates shuffling algorithm.

$\endgroup$
  • $\begingroup$ Oh. I think I misread read each user chooses a random number as each user is assigned a random number. As in a web server assigns each user a unique ID without revealing to any user what another's ID was. $\endgroup$ – Future Security Mar 2 at 18:43
  • $\begingroup$ Whoever knows $k$ also knows which user has which number, contradicting the requirement that the third party facilitator not know anything about the final number chosen fore each user. $\endgroup$ – Squeamish Ossifrage Mar 2 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.