# Do 'nonsequential' PRNGs exist?

It is my understanding that PRNGs typically use a seed and can then generate random values one after the other. This is what I mean by being 'sequential'.

How about a PRNG which allows me to retrieve e.g. the third value, without computing the first and second? Basically, I'm looking for a function $$g: \mathbb{N} \rightarrow (\mathbb{N} \rightarrow \mathbb{R})$$ such that for all seeds $$n \in \mathbb{N}$$, $$g(n)$$ is a function who's values follow some specified distribution while computing $$g(n)(m)$$ takes constant time.

• Something like CTR-mode should easily allow this. – SEJPM Dec 9 '19 at 19:08

How about a PRNG which allows me to retrieve e.g. the third value, without computing the first and second?

That is a popular informal description of what a pseudo-random function is—a function constructed out of a random seed that, for any input, produces a pseudorandom output in a repeatable fashion (i.e., same input always gives you the same pseudorandom output).

The suggestion in the comments to use CTR mode is along these lines—CTR mode is the application of a PRF to a sequence of counter values. I.e, if $$f : K \to I \to O$$ is a pseudorandom function family, $$k \in K$$ is a randomly selected secret key, and $$i_0, \dots, i_n \in I^*$$ is a sequence of distinct values in the domain of $$f_k$$, then the sequence $$f_k(i_0), \dots, f_k(i_n)$$ cannot be efficiently distinguished from a sequence of values drawn at random from $$O$$.

Some practical choices of PRF would be:

• HMAC
• Any block cipher (e.g., AES). These are pseudorandom permutations—bijective PRFs—which means that they cannot be distinguished from a general PRF unless the number of queries exceeds the so-called "birthday bound" (search for "PRF-PRP switching lemma").
• Could you elaborate this answer with the construction? Is it $\operatorname{HMAC}(K,i)$? – kelalaka Dec 9 '19 at 20:03
• @kelalaka: I elaborated a bit, but I'm not at all sure I understand what you want. – Luis Casillas Dec 9 '19 at 22:09
• Do we construct $\operatorname{HMAC}(k, nonce\mathbin\|counter)$ as in CTR or just $\operatorname{HMAC}(k,counter)$, or something else? – kelalaka Dec 9 '19 at 22:15
• I don't see any benefit of having an additional nonce (but if it fits in the same block with the counter there aren't any disadvantages either I suppose). If the seed value is too large for a key (i.e. the amount of entropy per bit is low) then having an entropy extraction routine in front of the counter mode would probably be a better idea. – Maarten Bodewes Dec 9 '19 at 22:48
• @kelalaka: Any sequence of values that don't get used twice under the same key will do. Both a bare counter and a nonce/counter pair can be made to work, it's a practical matter dictated by specific applications. For example with CTR-style ciphers we conventionally ask for nonces because that allows callers to encrypt multiple variable-length messages without them having to statefully track how many blocks they've encrypted so far with the same key. They just supply a random value or a message counter (simpler than a block counter) and the cipher API hides the variable message length math. – Luis Casillas Dec 10 '19 at 1:13