Pseudorandom function family

<h2 id="motivations-from-random-functions">Motivations from random functions</h2>
<p>A PRF is an efficient (i.e. computable in polynomial time), deterministic function that maps two distinct sets (domain and range) and looks like a truly random function.
</p><p>Essentially, a truly random function would just be composed of a lookup table filled with uniformly distributed random entries. However, in practice, a PRF is given an input string in the domain and a hidden random seed and runs multiple times with the same input string and seed, always returning the same value. Nonetheless, given an arbitrary input string, the output looks random if the seed is taken from a uniform distribution.
</p><p>A PRF is considered to be good if its behavior is indistinguishable from a truly random function. Therefore, given an output from either the truly random function or a PRF, there should be no efficient method to correctly determine whether the output was produced by the truly random function or the PRF.
</p>
<h2 id="formal-definition">Formal definition</h2>
<p>Pseudorandom functions take inputs 
  
    
      
        x
        ∈
        {
        0
        ,
        1
        
          }
          
            ∗
          
        
      
    
    {\displaystyle x\in \{0,1\}^{*}}
  
, where

∗
          
        
      
    
    {\displaystyle {}^{*}}
  
 is the <a href="/facts/Kleene_star/I6SX0f2Y">Kleene star</a>. Both the input size 
  
    
      
        I
        =
        
          |
        
        x
        
          |
        
      
    
    {\displaystyle I=|x|}
  
 and output size 
  
    
      
        λ
      
    
    {\displaystyle \lambda }
  
 depend only on the index size 
  
    
      
        n
        :=
        
          |
        
        s
        
          |
        
      
    
    {\displaystyle n:=|s|}
  
.
</p><p>
A family of functions,</p><blockquote><p>
  
    
      
        
          f
          
            s
          
        
        :
        
          
            {
            
              0
              ,
              1
            
            }
          
          
            I
            (
            n
            )
          
        
        →
        
          
            {
            
              0
              ,
              1
            
            }
          
          
            λ
            (
            n
            )
          
        
      
    
    {\displaystyle f_{s}:\left\{0,1\right\}^{I(n)}\rightarrow \left\{0,1\right\}^{\lambda (n)}}
  
</p></blockquote><p>is pseudorandom if the following conditions are satisfied:
</p><ul><li>There exists a polynomial-time algorithm that computes 
  
    
      
        
          f
          
            s
          
        
        (
        x
        )
      
    
    {\displaystyle f_{s}(x)}
  
 given any 
  
    
      
        s
      
    
    {\displaystyle s}
  
 and 
  
    
      
        x
      
    
    {\displaystyle x}
  
.</li>
<li>Let 
  
    
      
        
          F
          
            n
          
        
      
    
    {\displaystyle F_{n}}
  
 be the distribution of functions 
  
    
      
        
          f
          
            s
          
        
      
    
    {\displaystyle f_{s}}
  
 where 
  
    
      
        s
      
    
    {\displaystyle s}
  
 is uniformly distributed over 
  
    
      
        {
        0
        ,
        1
        
          }
          
            n
          
        
      
    
    {\displaystyle \{0,1\}^{n}}
  
, and let 
  
    
      
        R
        
          F
          
            n
          
        
      
    
    {\displaystyle RF_{n}}
  
 denote the uniform distribution over the set of all functions from 
  
    
      
        {
        0
        ,
        1
        
          }
          
            I
            (
            n
            )
          
        
      
    
    {\displaystyle \{0,1\}^{I(n)}}
  
 to 
  
    
      
        {
        0
        ,
        1
        
          }
          
            λ
            (
            n
            )
          
        
      
    
    {\displaystyle \{0,1\}^{\lambda (n)}}
  
. Then we require 
  
    
      
        
          F
          
            n
          
        
      
    
    {\displaystyle F_{n}}
  
 and <i>
  
    
      
        R
        
          F
          
            n
          
        
      
    
    {\displaystyle RF_{n}}
  
</i> are computationally indistinguishable, where <i>n</i> is the security parameter. That is, for any adversary that can query the oracle of a function sampled from either 
  
    
      
        
          F
          
            n
          
        
      
    
    {\displaystyle F_{n}}
  
 or <i>
  
    
      
        R
        
          F
          
            n
          
        
      
    
    {\displaystyle RF_{n}}
  
</i>, the advantage that she can tell apart which kind of oracle is given to her is negligible in 
  
    
      
        n
      
    
    {\displaystyle n}
  
.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a></li></ul>
<h2 id="oblivious-pseudorandom-functions">Oblivious pseudorandom functions</h2>
<p>In an <a href="/facts/Oblivious_pseudorandom_function/BBG8KoMA">oblivious pseudorandom function</a>, abbreviated OPRF, information is concealed from two parties that are involved in a PRF.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> That is, if Alice cryptographically hashes her secret value, <a href="/facts/Blinding_(cryptography)/oIdt1dCq">cryptographically blinds</a> the hash to produce the message she sends to Bob, and Bob mixes in his secret value and gives the result back to Alice, who unblinds it to get the final output, Bob is not able to see either Alice's secret value or the final output, and Alice is not able to see Bob's secret input, but Alice sees the final output which is a PRF of the two inputs -- a PRF of Alice's secret and Bob's secret.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> This enables transactions of sensitive cryptographic information to be secure even between untrusted parties.
</p><p>An OPRF is used in some implementations of <a href="/facts/Password-authenticated_key_agreement/udf3tV4x">password-authenticated key agreement</a>.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a>
</p><p>An OPRF is used in the Password Monitor functionality in <a href="/facts/Microsoft_Edge/BGoJEFX9">Microsoft Edge</a>.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a>
</p>
<h2 id="application">Application</h2>
<p>PRFs can be used for:<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a>
</p>
<ol><li><a href="/facts/Dynamic_perfect_hashing/AvKXzxrf">dynamic perfect hashing</a>; even if the adversary can change the key-distribution depending on the values the hashing function has assigned to the previous keys, the adversary can not force collisions.</li>
<li>Constructing deterministic, memoryless authentication schemes (<a href="/facts/Message_authentication_code/mXxCP5Yl">message authentication code</a> based) which are provably secure against chosen message attack.</li>
<li>Distributing unforgeable <a href="/facts/ID_number/qwCtYbDW">ID numbers</a>, which can be locally verified by stations that contain only a small amount of storage.</li>
<li>Constructing <a href="/facts/Identification_friend_or_foe/ANQjz9NM">identification friend or foe</a> systems.</li></ol>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Pseudorandom_permutation/5jm7P5hz">Pseudorandom permutation</a></li></ul>
<h2 id="notes">Notes</h2>

<ul><li><a href="/facts/Oded_Goldreich/Ufn1bqW7">Goldreich, Oded</a> (2001). <i>Foundations of Cryptography: Basic Tools</i>. Cambridge: Cambridge University Press. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-511-54689-1.</li>
<li>Pass, Rafael, <a href="https://www.cs.cornell.edu/courses/cs4830/2010fa/lecnotes.pdf"><i>A Course in Cryptography</i></a> (PDF), retrieved 22 December 2015</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Goldreich, Oded; Goldwasser, Shafi; Micali, Silvio (October 1986). "How to Construct Random Functions" (PDF). Journal of the ACM. 33 (4): 792–807. doi:10.1145/6490.6503.  web page and preprint <a href="/wiki/Oded_Goldreich" target="_blank">/wiki/Oded_Goldreich</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Lindell, Yehuda; Katz, Jonathan (2008). Introduction to Modern Cryptography. Chapman & Hall/CRC. p. 88. ISBN 978-1-58488-551-1. <a href="978-1-58488-551-1" target="_blank">978-1-58488-551-1</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Goldreich's FoC, vol. 1, def. 3.6.4. Pass's notes, def. 96.2 <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>M. Bellare; S. Keelveedhi; T. Ristenpart (August 2013). Dupless: server-aided encryption for deduplicated storage (PDF). Proceedings of the 22nd USENIX Security Symposium. Washington, DC, USA: USENIX Association. pp. 1–16. <a href="/wiki/Mihir_Bellare" target="_blank">/wiki/Mihir_Bellare</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Matthew Green. "Let’s talk about PAKE". 2018. <a href="https://blog.cryptographyengineering.com/2018/10/19/lets-talk-about-pake/" target="_blank">https://blog.cryptographyengineering.com/2018/10/19/lets-talk-about-pake/</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>Matthew Green. "Let’s talk about PAKE". 2018. <a href="https://blog.cryptographyengineering.com/2018/10/19/lets-talk-about-pake/" target="_blank">https://blog.cryptographyengineering.com/2018/10/19/lets-talk-about-pake/</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
<li id="fn:7"><p>Lauter, Kristin; Kannepalli, Sreekanth; Laine, Kim; Cruz Moreno, Radames (January 1, 2021). "Password Monitor: Safeguarding passwords in Microsoft Edge". Microsoft Research Blog. Retrieved January 1, 2021. <a href="https://www.microsoft.com/en-us/research/blog/password-monitor-safeguarding-passwords-in-microsoft-edge/" target="_blank">https://www.microsoft.com/en-us/research/blog/password-monitor-safeguarding-passwords-in-microsoft-edge/</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li>
<li id="fn:8"><p>Goldreich, O.; Goldwasser, S.; Micali, S. (1985). "On the Cryptographic Applications of Random Functions (Extended Abstract)". Advances in Cryptology. Lecture Notes in Computer Science. Vol. 196. p. 276. doi:10.1007/3-540-39568-7_22. ISBN 978-3-540-15658-1. <a href="978-3-540-15658-1" target="_blank">978-3-540-15658-1</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li>
</ol>

Pseudorandom function family open-in-new

Pseudorandom function family