In 1997, Moni Naor and Omer Reingold described efficient constructions for various cryptographic primitives in private key as well as public-key cryptography.
Their result is the construction of an efficient pseudorandom function.
they define the function where x = x1 ... xn is the bit representation of integer x, 0 ≤ x ≤ 2n−1, with some extra leading zeros if necessary.
at any given point is comparable with one modular exponentiation and n-modular multiplications.
This function can be computed in parallel by threshold circuits of bounded depth and polynomial size.
The Naor–Reingold function can be used as the basis of many cryptographic schemes including symmetric encryption, authentication and digital signatures.
Assume that an attacker sees several outputs of the function, e.g.
Assume for simplicity that x1 = 0, then the attacker needs to solve the computational Diffie–Hellman (CDH) between
In general, moving from k to k + 1 changes the bit pattern and unless k + 1 is a power of 2 one can split the exponent in
This attacker wants to predict the next sequence element.
Such an attack would be very bad—but it's also possible to fight it off by working in groups with a hard Diffie–Hellman problem (DHP).
Example: An attacker sees several outputs of the function e.g.
Then, the attacker wants to predict the next sequence element of this function,
There are other attacks that would be very bad for a pseudorandom number generator: the user expects to get random numbers from the output, so of course the stream should not be predictable, but even more, it should be indistinguishable from a random string.
with access to an oracle for evaluating the function
Suppose the decisional Diffie–Hellman assumption holds for
, Naor and Reingold show that for every probabilistic polynomial time algorithm
and sufficiently large n The first probability is taken over the choice of the seed s = (p, g, a) and the second probability is taken over the random distribution induced on p, g by
, instance generator, and the random choice of the function
[2] One natural measure of how useful a sequence may be for cryptographic purposes is the size of its linear complexity.
The linear complexity of an n-element sequence W(x), x = 0,1,2,...,n – 1, over a ring
is the length l of the shortest linear recurrence relation W(x + l) = Al−1 W(x +l−1) + ... + A0 W(x), x = 0,1,2,..., n – l −1 with A0, ..., Al−1 ∈
, sufficiently large l, the linear complexity of the sequence
[3] The bound of this work has disadvantages, namely it does not apply to the very interesting case
is exponentially close to uniform distribution for almost all vectors a ∈
holds, where and Although this property does not seem to have any immediate cryptographic implications, the inverse fact, namely non uniform distribution, if true would have disastrous consequences for applications of this function.
[4] The elliptic curve version of this function is of interest as well.
In particular, it may help to improve the cryptographic security of the corresponding system.
, then each vector a defines a finite sequence in the subgroup
The Naor–Reingold elliptic curve sequence is defined as If the decisional Diffie–Hellman assumption holds, the index k is not enough to compute