Computational indistinguishability

<h2 id="formal-definition">Formal definition</h2>
<p>Let 
  
    
      
        
          {
          
            D
            
              n
            
          
          
            }
            
              n
              ∈
              
                N
              
            
          
        
      
    
    {\displaystyle \scriptstyle \{D_{n}\}_{n\in \mathbb {N} }}
  
 and 
  
    
      
        
          {
          
            E
            
              n
            
          
          
            }
            
              n
              ∈
              
                N
              
            
          
        
      
    
    {\displaystyle \scriptstyle \{E_{n}\}_{n\in \mathbb {N} }}
  
 be two <a href="/facts/Distribution_ensemble/6Rn4eTQ0">distribution ensembles</a> indexed by a <a href="/facts/Security_parameter/Xbqeyh60">security parameter</a> <i>n</i> (which usually refers to the length of the input); we say they are computationally indistinguishable if for any <a href="/facts/Uniformity_(complexity)/6EzA9Tty">non-uniform</a> probabilistic <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a> <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> <i>A</i>, the following quantity is a <a href="/facts/Negligible_function_(cryptography)/yHCYQj4J">negligible function</a> in <i>n</i>:
</p>

δ
        (
        n
        )
        =
        
          |
          
            
              Pr
              
                x
                ←
                
                  D
                  
                    n
                  
                
              
            
            [
            A
            (
            x
            )
            =
            1
            ]
            −
            
              Pr
              
                x
                ←
                
                  E
                  
                    n
                  
                
              
            
            [
            A
            (
            x
            )
            =
            1
            ]
          
          |
        
        .
      
    
    {\displaystyle \delta (n)=\left|\Pr _{x\gets D_{n}}[A(x)=1]-\Pr _{x\gets E_{n}}[A(x)=1]\right|.}

<p>denoted 
  
    
      
        
          D
          
            n
          
        
        ≈
        
          E
          
            n
          
        
      
    
    {\displaystyle D_{n}\approx E_{n}}
  
.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> In other words, every efficient algorithm <i>A'</i>s behavior does not significantly change when given samples according to <i>D</i><i>n</i> or <i>E</i><i>n</i> in the limit as 
  
    
      
        n
        →
        ∞
      
    
    {\displaystyle n\to \infty }
  
. Another interpretation of computational indistinguishability, is that polynomial-time algorithms actively trying to distinguish between the two ensembles cannot do so: that any such algorithm will only perform negligibly better than if one were to just guess.
</p>
<h2 id="related-notions">Related notions</h2>
<p>Implicit in the definition is the condition that the algorithm, 
  
    
      
        A
      
    
    {\displaystyle A}
  
, must decide based on a single sample from one of the distributions. One might conceive of a situation in which the algorithm trying to distinguish between two distributions, could access as many samples as it needed. Hence two ensembles that cannot be distinguished by polynomial-time algorithms looking at multiple samples are deemed indistinguishable by polynomial-time sampling.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a>: 107  If the polynomial-time algorithm can generate samples in polynomial time, or has access to a <a href="/facts/Random_oracle/wK7MhxDq">random oracle</a> that generates samples for it, then indistinguishability by polynomial-time sampling is equivalent to computational indistinguishability.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a>: 108 
</p>

<h2 id="external-links">External links</h2>
<ul><li><a href="/facts/Yehuda_Lindell/mlkrM6pV">Yehuda Lindell</a>. <a href="http://u.cs.biu.ac.il/~lindell/89-656/main-89-656.html">Introduction to Cryptography</a></li>
<li>Donald Beaver and <a href="/facts/Silvio_Micali/IxgCplaX">Silvio Micali</a> and <a href="/facts/Phillip_Rogaway/hYhbH8V5">Phillip Rogaway</a>, The Round Complexity of Secure Protocols (Extended Abstract), 1990, pp. 503–513</li>
<li><a href="/facts/Shafi_Goldwasser/aTJJq4mB">Shafi Goldwasser</a> and <a href="/facts/Silvio_Micali/IxgCplaX">Silvio Micali</a>. Probabilistic Encryption. JCSS, 28(2):270–299, 1984</li>
<li><a href="/facts/Oded_Goldreich/Ufn1bqW7">Oded Goldreich</a>. Foundations of Cryptography: Volume 2 – Basic Applications. Cambridge University Press, 2004.</li>
<li><a href="/facts/Jonathan_Katz_(computer_scientist)/NvWxVBYA">Jonathan Katz</a>, <a href="/facts/Yehuda_Lindell/mlkrM6pV">Yehuda Lindell</a>, "Introduction to Modern Cryptography: Principles and Protocols," Chapman & Hall/CRC, 2007</li></ul>
<p>
<i>This article incorporates material from computationally indistinguishable on <a href="/facts/PlanetMath/wphPCtLf">PlanetMath</a>, which is licensed under the Creative Commons Attribution/Share-Alike License.</i>
</p>

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

<ol>
<li id="fn:1"><p>Lecture 4 - Computational Indistinguishability, Pseudorandom Generators <a href="http://www.cs.princeton.edu/courses/archive/spr10/cos433/lec4.pdf" target="_blank">http://www.cs.princeton.edu/courses/archive/spr10/cos433/lec4.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Goldreich, O. (2003). Foundations of cryptography. Cambridge, UK: Cambridge University Press. <a href="/wiki/Oded_Goldreich" target="_blank">/wiki/Oded_Goldreich</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Goldreich, O. (2003). Foundations of cryptography. Cambridge, UK: Cambridge University Press. <a href="/wiki/Oded_Goldreich" target="_blank">/wiki/Oded_Goldreich</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
</ol>

Computational indistinguishability open-in-new

Computational indistinguishability