Naor–Reingold pseudorandom function

In 1997, <a href="/facts/Moni_Naor/I9UuUSTx">Moni Naor</a> and <a href="/facts/Omer_Reingold/MaaTa9CF">Omer Reingold</a> described efficient constructions for various <a href="/facts/Cryptographic_primitive/fy6vq5YM">cryptographic primitives</a> in private key as well as <a href="/facts/Public-key_cryptography/gowoFTxS">public-key cryptography</a>. Their result is the construction of an efficient <a href="/facts/Pseudorandom_function_family/Y2PpjPeF">pseudorandom function</a>. Let p and l be <a href="/facts/Prime_number/L20FLkgn">prime numbers</a> with l |p−1. Select an element g ∈ 
 
 
 
 
 
 
 
 F
 
 
 p
 
 
 
 
 ∗
 
 
 
 
 {\displaystyle {\mathbb {F} _{p}}^{*}}
 
 of <a href="/facts/Multiplicative_order/mD2IzTo0">multiplicative order</a> l. Then for each (n+1)-dimensional <a href="/facts/Coordinate_vector/TEcLqS40">vector</a> a = (a0,a1, ..., an)∈ 
 
 
 
 (
 
 
 F
 
 
 l
 
 
 
 )
 
 n
 +
 1
 
 
 
 
 {\displaystyle (\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}}...a_{n}^{x_{n}}}\in \mathbb {F} _{p}}

where x = x1 ... xn is the <a href="/facts/Binary_numeral_system/a6JDSRPs">bit representation</a> of integer x, 0 ≤ x ≤ 2n−1, with some extra leading zeros if necessary.

Naor–Reingold pseudorandom function open-in-new

Naor–Reingold pseudorandom function