1
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 4
    $\begingroup$ Something like CTR-mode should easily allow this. $\endgroup$
    – SEJPM
    Dec 9, 2019 at 19:08

1 Answer 1

Reset to default
3
$\begingroup$

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").
Improve this answer
$\endgroup$
5
  • $\begingroup$ Could you elaborate this answer with the construction? Is it $\operatorname{HMAC}(K,i)$? $\endgroup$
    – kelalaka
    Dec 9, 2019 at 20:03
  • $\begingroup$ @kelalaka: I elaborated a bit, but I'm not at all sure I understand what you want. $\endgroup$
    – Luis Casillas
    Dec 9, 2019 at 22:09
  • $\begingroup$ Do we construct $\operatorname{HMAC}(k, nonce\mathbin\|counter)$ as in CTR or just $\operatorname{HMAC}(k,counter)$, or something else? $\endgroup$
    – kelalaka
    Dec 9, 2019 at 22:15
  • 1
    $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes ♦
    Dec 9, 2019 at 22:48
  • 2
    $\begingroup$ @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. $\endgroup$
    – Luis Casillas
    Dec 10, 2019 at 1:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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