Naor-Reingold Pseudorandom Function

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 l |p-1. Select an element g {\mathbb F_p}^* of multiplicative order l. Then for each n-dimensional vector a = (a1, ..., an)∈  (\mathbb F_{l})^{n} they define the function

f_{a}(x) = g^{a_{1}^{x_{1}} a_{2}^{x_{2}}...a_{n}^{x_{n}}} \in \mathbb F_p

where x = x1 ... xn is the bit representation of integer x, 0 ≤ x ≤ 2n-1, with some extra leading zeros if necessary.[1]

Example[edit]

Let p = 7, p – 1 = 6, and l = 3, l |p-1. Select g = 4 ∈  {\mathbb F_7}^* of multiplicative order 3 (since 43 = 64 ≡ 1 mod 7). For n = 3, a = (1, 2, 1) and x = 5 (the bit representation of 5 is 101), we can compute  f_{a}\;(5) as follows:

f_{a}(x) = g^{a_{1}^{x_{1}} a_{2}^{x_{2}}...a_{n}^{x_{n}}}
f_{a}(5) = 4^{1^{1} 2^{0} 1^{1}} = 4^{1} = 4 \in \mathbb F_7

Efficiency[edit]

The evaluation of function  f_{a}\;(x) in the Naor-Reingold construction can be done very efficiently. Computing the value of the function  f_{a}\;(x) 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.

Security of the Function[edit]

Assume that an attacker sees several outputs of the function, e.g.  f_{a}(1) = g^{a_{1}}, f_{a}(2) = g^{a_{2}}, f_{a}(3) = g^{a_{1}a_{2}}, ... f_{a}(k) = g^{a_{1}^{x_{1}} a_{2}^{x_{2}}...a_{n}^{x_{n}}} and wants to compute  f_{a}\;(k + 1). Assume for simplicity that x1 = 0, then the attacker needs to solve the Computational Diffie-Hellman (CDH) between  f_a (1)= g^{a_{1}} and f_{a}(k) = g^{a_{2}^{x_{2}} ...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'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. 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).


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. Let  \mathcal{A}^f denote the algorithm  \mathcal{A} with access to an oracle for evaluating the function  f_{a}\;(x) . Suppose the Decisional Diffie-Hellman assumption holds for  \mathbb F_p , Naor and Reingold show that for every probabilistic polynomial time algorithm  \mathcal{A} and sufficiently large n

 \text{Pr }[\mathcal{A}^{f_{a}(x)}(p,g) \to 1] - \text{Pr }[\mathcal{A}^{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  \mathcal{I}\mathcal{G} (n) , instance generator, and the random choice of the function  R_{a}\;(x) among the set of all  \{0,1\}^{n} \to \mathbb F_p functions.[2]

Linear Complexity[edit]

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  \mathcal{R} 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,…, nl –1 with A0, …, Al-1 \mathcal{R}, which is satisfied by this sequence.

For some \gamma > 0,n ≥ (1+ \gamma) \log l, for any \delta > 0 , sufficiently large l, the linear complexity of the sequence  f_{a}\;(x),0 ≤ x ≤ 2n-1, denoted by L_a satisfies

L_{a} \geqslant \begin{cases}
l^{1-\ \delta\,\!} &\text{, if } \gamma\,\! \geqslant 2\\
l^{\left (\tfrac{\ \gamma\,\!}{2-\ \delta\,\!}\right )} &\text{, if }  \gamma\,\! < 2
\end{cases}

for all except possibly at most 3(l - 1)^{n - \delta} vectors a ∈  (\mathbb F_{l})^{n} .[3] 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[edit]

The statistical distribution of  f_{a}\;(x) is exponentially close to uniform distribution for almost all vectors a ∈  (\mathbb F_{l})^{n} .

Let {\mathbf D}_a be the discrepancy of the set \{f_a (x)| 0 \leq x \leq 2^{n-1}\}. Thus, if n = \log  p is the bit length of p then for all vectors a ∈  (\mathbb F_{l})^{n} the bound {\mathbf D}_a\leq \Delta (l,p) holds, where

\Delta (l,p) = \begin{cases}
p^{\left (\tfrac{1-\ \gamma\,\!}{2}\right )}l^{\left (\tfrac{-1}{2}\right )}\log^{2}p &\text{, if } l \geqslant p^{\gamma\,\!}\\
p^{\left (\tfrac{1}{2}\right )}l^{-1}\log^{2}p &\text{, if } p^{\gamma\,\!} > l \geqslant p^{\left (\tfrac{2}{3}\right )}  \\
p^{\left (\tfrac{1}{4}\right )}l^{\left (\tfrac{-5}{8}\right )}\log^{2}p &\text{, if } p^{\left (\tfrac{2}{3}\right )} > l \geqslant p^{\left (\tfrac{1}{2}\right )}  \\
p^{\left (\tfrac{1}{8}\right )}l^{\left (\tfrac{-3}{8}\right )}\log^{2}p &\text{, if } p^{\left (\tfrac{1}{2}\right )} > l \geqslant p^{\left (\tfrac{1}{3}\right )}  \\
\end{cases}

and \gamma = 2.5 - \log 3 = 0.9150....

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]

Sequences in Elliptic Curve[edit]

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. Let p > 3 be prime and let E be an elliptic curve over  \mathbb F_p , then each vector a defines a finite sequence in the subgroup \langle G\rangle as:

F_{a}(x) = (a_{1}^{x_{1}} a_{2}^{x_{2}}\dots a_{n}^{x_{n}})G

where x = x_1 \dots  x_n is the bit representation of integer x, 0 \leq x \leq 2^{n-1}. The Naor-Reingold elliptic curve sequence is defined as

 u_{k} = X (f_{a}(k))\; \mbox{where } X (P) \mbox{ is the abscissa of}\; P \in E. [5]

If the Decisional Diffie-Hellman assumption holds, the 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[edit]

Notes[edit]

  1. ^ Naor, M., Reingold, O. "Number-theoretic constructions of efficient pseudo-random functions," Proc 38th IEEE Symp. on Foundations of Comp. Sci, (1997), 458-467.
  2. ^ Boneh, Dan. "The Decision Diffie–Hellman Problem,"ANTS-III: Proceedings of the Third International Symposium on Algorithmic Number Theory,1998,48–63.
  3. ^ Shparlinski, Igor E. "Linear Complexity of the Naor-Reingold pseudo-random function," Inform. Process Lett, 76 (2000), 95-99.
  4. ^ Shparlinski, Igor E. "On the uniformity of distribution of the Naor-Reingold pseudo-random function," Finite Fields and Their Applications, 7 (2001), 318-326
  5. ^ Cruz, M., Gomez, D., Sadornil, D. "On the linear complexity of the Naor-Reingold sequence with elliptic curves," Finite Fields and Their Applications, 16 (2010), 329-333

References[edit]

  • Shparlinski, Igor (2003), Cryptographic Applications of Analytic Number Theory: Complexity Lower Bounds and Pseudorandomness (first ed.), Birkhäuser Basel, ISBN 978-3-7643-6654-4 
  • Goldreich, Oded (1998), Modern Cryptography, Probabilistic Proofs and Pseudorandomness (first ed.), Springer, ISBN 978-3-540-64766-9