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, and select an element g ∈ F p ∗ {\displaystyle g\in \mathbb {F} _{p}^{*}} of multiplicative order l. Then for each (n+1)-dimensional vector a = ( a 0 , a 1 , … , a n ) ∈ F l n + 1 , {\displaystyle a=(a_{0},a_{1},\ldots ,a_{n})\in \mathbb {F} _{l}^{n+1},} they define the function f a ( x ) = g a 0 ⋅ a 1 x 1 a 2 x 2 ⋯ a n x n ∈ F p , {\displaystyle f_{a}(x)=g^{a_{0}\cdot a_{1}^{x_{1}}a_{2}^{x_{2}}\cdots a_{n}^{x_{n}}}\in \mathbb {F} _{p},} where x = x1…xn is the bit representation of the integer x, 0 ≤ x ≤ 2n−1, with some extra leading zeros if necessary.
Example Let p = 7 and l = 3; then l | p − 1. Select g = 4 ∈ F 7 ∗ {\displaystyle g=4\in \mathbb {F} _{7}^{*}} of multiplicative order 3 (since 43 = 64 ≡ 1 (mod 7)). For n = 3, a = (1,1,2,1) and x = 5 (the bit representation of 5 is 101), we can compute fa(5) as follows: f a ( ) 5 ) = 4 1 ⋅ 1 1 2 0 1 1 = 4 1 = 4 ∈ F 7 . {\displaystyle f_{a}()5)=4^{1\cdot 1^{1}2^{0}1^{1}}=4^{1}=4\in \mathbb {F} _{7}.}
Efficiency The evaluation of function fa(5) 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.
… excerpt ends here. Continue reading the full article.
