Naor–Reingold pseudorandom function

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. Let p and l be prime numbers with Template:Nowrap, and select an element $g\in {𝔽}_p^{\ast }$ of multiplicative order l. Then for each (n+1)-dimensional vector $a=(a_0,a_1,\dots ,a_n)\in {𝔽}_l^{n+1},$ they define the function$$f_a(x)=g^{a_0\cdot a_1^{x_1}{a}_2^{x_2}\cdots a_n^{x_n}}\in {𝔽}_p,$$where Template:Nowrap is the bit representation of the integer x, Template:Nowrap, with some extra leading zeros if necessary.

Example

Let Template:Nowrap and Template:Nowrap; then Template:Nowrap. Select $g=4\in {𝔽}_7^{\ast }$ of multiplicative order 3 (since Template:Nowrap). For Template:Nowrap, Template:Nowrap and Template:Nowrap (the bit representation of 5 is 101), we can compute Template:Nowrap as follows:$$f_a(5)=4^{1\cdot 1^1{2}^0{1}^1}=4^1=4\in {𝔽}_7.$$

Efficiency

The evaluation of function Template:Nowrap in the Naor–Reingold construction can be done very efficiently: at any given point, it 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.

Security of the function

Assume that an attacker sees several outputs of the function, such as $f_a(1)=g^{a_1},$ $f_a(2)=g^{a_2},$ $f_a(3)=g^{a_1{a}_2},\dots ,$ $f_a(k)=g^{a_1^{x_1}{a}_2^{x_2}\mathrm{...}{a}_n^{x_n}},$ and wants to compute $f_a(k+1)$. Assume for simplicity that $x_1=0$; then the attacker needs to solve the computational Diffie–Hellman (CDH) problem between $f_a(1)=g^{a_1}$ and $f_a(k)=g^{a_2^{x_2}\mathrm{...}{a}_n^{x_n}}$ to get $f_a(k+1)=g^{a_1{a}_2^{x_2}\dots a_n^{x_n}}$. 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 $f_a(k+1)$ so that the computation corresponds to computing the Diffie–Hellman key between two of the earlier results. This attacker wants to predict the next sequence element. Such an attack would be very bad—but it is 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, such as $f_a(5)=4^{1^1{2}^0{1}^1}=4^1=4$, as in the previous example, and $f_a(1)=4^{1^0{2}^0{1}^1}=4^1=4$. Then, the attacker wants to predict the next sequence element of this function, $f_a(6)$. However, the attacker cannot predict the outcome of $f_a(6)$ from knowing $f_a(1)$ and $f_a(5)$.

Other attacks could also 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. Let ${𝒜}^f$ denote the algorithm $𝒜$ with access to an oracle for evaluating the function $f_a(x)$. Suppose that the decisional Diffie–Hellman assumption holds for ${𝔽}_p$; then Naor and Reingold show that for every probabilistic polynomial time algorithm $𝒜$ and sufficiently large n,$$\text{Pr }[{𝒜}^{f_a(x)}(p,g)\to 1]-\text{Pr }[{𝒜}^R(p,g)\to 1]$$is negligible.

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 $ℐ𝒢(n)$, instance generator, and the random choice of the function $R_a(x)$ among the set of all $\{0,1{\}}^n\to {𝔽}_p$ functions.

Linear complexity

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)$ over a ring $ℛ$ with $x=0,1,2,\dots ,n-1$ is the length $l$ of the shortest linear recurrence relation $W(x+l)=A_{l-1}W(x+l-1)+\cdots A_{0}W(x),$ where $x=0,1,2,\dots ,n-l-1$ with $A_0,\dots ,A_{l-1}\in ℛ$, which is satisfied by this sequence.

For some $\gamma >0$ and $n\ge (1+\gamma )\log (l)$, for any $\delta >0$ and sufficiently large l, the linear complexity of the sequence $f_a(x{)}_{x=0}^{2^{n-1}}$, denoted by $L_a$ satisfies$$L_a⩾\{\begin{array}{cc}{l}^{1-\delta }& \text{if }\gamma \ge 2\\ l^{\left(\frac{\gamma }{2-\delta }\right)}& \text{if }\gamma <2\end{array}$$for all except possibly at most $3(l-1{)}^{n-\delta }$ vectors $a\in ({𝔽}_l{)}^n$. The bound of this work has disadvantages; namely, it does not apply to the very interesting case $\log (p)\approx \log (n)\approx n.$

Uniformity of distribution

The statistical distribution of $f_a(x)$ is exponentially close to uniform for almost all vectors $a\in ({𝔽}_l{)}^n$.

Let ${𝐃}_a$ be the discrepancy of the set $\{f_a(x)|0\le x\le 2^{n-1}\}$. Thus, if $n=\lceil \log (p)\rceil$ is the bit length of $p$, then for all vectors $a\in ({𝔽}_l{)}^n$, the bound ${𝐃}_a\le \mathrm{\Delta }(l,p)$ holds, where$$\mathrm{\Delta }(l,p)=\{\begin{array}{cc}{p}^{\left(\frac{1-\gamma }{2}\right)}{l}^{\left(\frac{-1}{2}\right)}{\log }^{2}p& \text{ if }l⩾p^{\gamma }\\ p^{\left(\frac{1}{2}\right)}{l}^{-1}{\log }^{2}p& \text{ if }{p}^{\gamma }>l⩾p^{\left(\frac{2}{3}\right)}\\ p^{\left(\frac{1}{4}\right)}{l}^{\left(\frac{-5}{8}\right)}{\log }^{2}p& \text{ if }{p}^{\left(\frac{2}{3}\right)}>l⩾p^{\left(\frac{1}{2}\right)}\\ p^{\left(\frac{1}{8}\right)}{l}^{\left(\frac{-3}{8}\right)}{\log }^{2}p& \text{ if }{p}^{\left(\frac{1}{2}\right)}>l⩾p^{\left(\frac{1}{3}\right)}\end{array}$$and$$\gamma =2.5-\log 3=0.9150\dots .$$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.

Sequences in elliptic curves

The elliptic-curve version of this function is also of interest. In particular, it may help to improve the cryptographic security of the corresponding system. Let $p>3$ be prime and let $E$ be an elliptic curve; then each vector $𝐚$ defines a finite sequence in the subgroup $⟨G⟩$ as$$F_a(x)=(a_1^{x_1}{a}_2^{x_2}\dots a_n^{x_n})G,$$where $x=x_1\cdots x_n$ is the bit representation of integer $x,0\le x\le 2^{n-1}$. The Naor–Reingold elliptic curve sequence is defined as$$u_k=X(f_a(k)),$$where $X(P)$ is the abscissa of $P\in E({𝔽}_p)$.

If the decisional Diffie–Hellman assumption holds, then index $k$ is not enough to compute $u_k$ in polynomial time, even if an attacker performs polynomially-many queries to a random oracle.

See also

• Decisional Diffie–Hellman assumption
• Finite field
• Inversive congruential generator
• Generalized inversive congruential pseudorandom numbers

References

• Template:Citation.
• Template:Citation
• Template:Citation