# Are there on-line ways to use a block cipher to generate unique $n$ bits that guarantee collision-freeness for $2^n$ times?

$$n$$ is a run-time variable chosen each time the user runs the implementation.

One way I can think is to use any block cipher, say AES, as a seeded CSPRNG to randomly shuffle list of numbers $$0, 1, \ldots, 2^n-1$$. This way I guarantee collision-freeness up to $$2^n$$ numbers. But this approach is too expensive as it will require me to swap $$2^n$$ numbers.

Another way I can think of is to use the block cipher to generate ciphertext $$c = \mathrm{enc}(\mathrm{0x000}\ldots, \mathrm{key})$$, where $$\mathrm{len}(c) \ge n$$. Then take the 1st $$n$$ many bits of $$c$$; let's call it $$c_n$$. Then do: $$c_n \oplus 0, c_n \oplus 1, \ldots, c_n \oplus 2^n-1$$. This is efficient, but the problem is that, i think, the sequence is not random. E.g. $$c_n \oplus 0$$ is generally going to be closer to $$c_n \oplus 1$$ than, say, $$c_n \oplus 100$$.

The question: Is any faster approach, where I can use any block cipher for about once only, to generate the next number, such that, as I repeat the process, I get $$2^n$$ many unique numbers without collisions?

In a sense, I guess I may call it: an online version of shuffling the numbers $$0, 1, \ldots, 2^n-1$$, without needing to maintain a list in memory that is $$2^n$$ long.

Ideally, if the perfect online shuffle is found, it must have this distribution (where $$i$$ is any number in $$\{0, 1, \ldots, 2^n-1\}$$ and $$N_j$$ is a random variable that will take the value of a number in that set in the $$j^{th}$$ call of the ideal on-line shuffler):

$$\begin{split} \Pr(N_0 = i) &= 1/2^n \\ \Pr(N_1 = i) &= 1/(2^n - 1) \\ \Pr(N_2 = i) &= 1/(2^n - 2) \\ \vdots & \\ \Pr(N_{2^n-1} = i) &= 1/(2^n - (2^n-1)) = 1\\ \end{split}$$

• Is there some requirement not satisfied by the classical method: enciphering an $n$-bit counter with an $n$-bit block cipher? If so, please state it.
– fgrieu
Commented Sep 22, 2021 at 13:34
• @fgrieu - Not sure (I guess it's just ignorance). $n$ in my case is variable (defined at run time by user). I didn't think of it. Is ChaCha20 one such algorithms, where I can specify arbitrary blocksize at run time and have the effect above? Commented Sep 22, 2021 at 13:48
• Yeah, I think the key stream generated by counter mode would fit this problem perfectly. If you only have encrypt then it is defined by CTR-mode encryption of all-zero blocks. Commented Sep 22, 2021 at 14:22
• @MaartenBodewes - Interesting. Since ChaCha20 internally has 512 byte blocks (at least how implemented usually, e.g. libsodium's), is it possible to optimise the implementation for $n < 512$? such that the sequence is identical but memory/cpu consumption is less than that of a $512$? Commented Sep 22, 2021 at 14:27
• Ah, so the missing requirement is $n$ variable at run time, which forces to use techniques of Format reserving Encryption. Please add that in the question, a range for $n$ (overly large $n$ make little sense, since collisions among independent uniformly random values of $n\ge256$ bit are not observable anyway); and perhaps whatever limit there may be to the number of $n$-bit values an adversary may obtain for a given sequence/key. Note: ChaCha20 is not a block cipher, much less of variable block width as needed, but it might be used as a building block for one.
– fgrieu
Commented Sep 22, 2021 at 14:42

Are there on-line ways to use a block cipher to generate unique $$n$$ bits that guarantee collision-freeness for $$2^n$$ times?
The obvious way to do this is select a Format Preserving Encryption mode of your block cipher, say, FF1. That is a mode that takes an arbitrary length block (in your case, $$n$$ bits); you would insert the key and encrypt a counter. With a fixed key (and nonce), the encryption is invertable, and has an output exactly the same length as the input - that gives you precisely what you are asking for.
The only downside I can see is that FF1 may have security issues for truly tiny blocks (in your case, $$n \le 6$$). Of course, if the user asks for that small of an $$n$$, you could fall back on the 'permute the values from 0 to $$2^n-1$$ strategy...)