Probabilistic encryption

<h2 id="history">History</h2>
<p>The first provably-secure probabilistic public-key encryption scheme was proposed by <a href="/facts/Shafi_Goldwasser/aTJJq4mB">Shafi Goldwasser</a> and <a href="/facts/Silvio_Micali/IxgCplaX">Silvio Micali</a>, based on the hardness of the <a href="/facts/Quadratic_residuosity_problem/b8B2ptVQ">quadratic residuosity problem</a> and had a message expansion factor equal to the public key size.  More efficient probabilistic encryption algorithms include <a href="/facts/ElGamal_encryption/sKDVyMyR">Elgamal</a>, <a href="/facts/Paillier/oLl6TR8H">Paillier</a>, and various constructions under the <a href="/facts/Random_oracle_model/wK7MhxDq">random oracle model</a>, including OAEP.
</p>
<h2 id="security">Security</h2>
<p>Probabilistic encryption is particularly important when using <a href="/facts/Public_key_cryptography/gowoFTxS">public key cryptography</a>.  Suppose that the <a href="/facts/Adversary_(cryptography)/X211CFfE">adversary</a> observes a ciphertext, and suspects that the plaintext is either "YES" or "NO", or has a hunch that the plaintext might be "ATTACK AT CALAIS". When a <a href="/facts/Deterministic_encryption/UDDXRtQ2">deterministic encryption</a> algorithm is used, the adversary can simply try encrypting each of their guesses under the recipient's public key, and compare each result to the target ciphertext. To combat this attack, public key encryption schemes must incorporate an element of randomness, ensuring that each plaintext maps into one of a large number of possible ciphertexts.
</p><p>An intuitive approach to converting a deterministic encryption scheme into a probabilistic one is to simply pad the plaintext with a random string before encrypting with the <a href="/facts/Deterministic_algorithm/v8x4wz35">deterministic algorithm</a>.  Conversely, decryption involves applying a deterministic algorithm and ignoring the random padding.  However, early schemes which applied this naive approach were broken due to limitations in some deterministic encryption schemes.  Techniques such as <a href="/facts/Optimal_Asymmetric_Encryption_Padding/j5doK6YB">Optimal Asymmetric Encryption Padding</a> (OAEP) integrate random padding in a manner that is secure using any <a href="/facts/Trapdoor_permutation/xMTTRrhY">trapdoor permutation</a>.
</p>
<h2 id="examples">Examples</h2>
<p>Example of probabilistic encryption using any trapdoor permutation:
</p>
<ul><li><i>x</i> - <i>single bit</i> plaintext</li>
<li><i>f</i> - <a href="/facts/Trapdoor_permutation/xMTTRrhY">trapdoor permutation</a> (deterministic encryption algorithm)</li>
<li><i>b</i> - <a href="/facts/Hard_core_predicate/jhThVcFC">hard core predicate</a> of <i>f</i></li>
<li><i>r</i> - random string</li></ul>
<p>
  
    
      
        
          
            E
            n
            c
          
        
        (
        x
        )
        =
        (
        f
        (
        r
        )
        ,
        x
        ⊕
        b
        (
        r
        )
        )
      
    
    {\displaystyle {\rm {Enc}}(x)=(f(r),x\oplus b(r))}

</p><p>
  
    
      
        
          
            D
            e
            c
          
        
        (
        y
        ,
        z
        )
        =
        b
        (
        
          f
          
            −
            1
          
        
        (
        y
        )
        )
        ⊕
        z
      
    
    {\displaystyle {\rm {Dec}}(y,z)=b(f^{-1}(y))\oplus z}

</p><p>This is inefficient because only a single bit is encrypted. In other words, the message expansion factor is equal to the public key size.
</p><p>Example of probabilistic encryption in the random oracle model:
</p>
<ul><li><i>x</i> - plaintext</li>
<li><i>f</i> - <a href="/facts/Trapdoor_permutation/xMTTRrhY">trapdoor permutation</a> (deterministic encryption algorithm)</li>
<li><i>h</i> - <a href="/facts/Random_oracle/wK7MhxDq">random oracle</a> (typically implemented using a publicly specified <a href="/facts/Cryptographic_hash_function/cuxkgbST">hash function</a>)</li>
<li><i>r</i> - random string</li></ul>
<p>
  
    
      
        
          
            E
            n
            c
          
        
        (
        x
        )
        =
        (
        f
        (
        r
        )
        ,
        x
        ⊕
        h
        (
        r
        )
        )
      
    
    {\displaystyle {\rm {Enc}}(x)=(f(r),x\oplus h(r))}

</p><p>
  
    
      
        
          
            D
            e
            c
          
        
        (
        y
        ,
        z
        )
        =
        h
        (
        
          f
          
            −
            1
          
        
        (
        y
        )
        )
        ⊕
        z
      
    
    {\displaystyle {\rm {Dec}}(y,z)=h(f^{-1}(y))\oplus z}

</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Deterministic_encryption/UDDXRtQ2">Deterministic encryption</a></li>
<li><a href="/facts/Efficient_Probabilistic_Public-Key_Encryption_Scheme/bIFl93J4">Efficient Probabilistic Public-Key Encryption Scheme</a></li>
<li><a href="/facts/Strong_secrecy/Tm1IkGoC">Strong secrecy</a></li></ul>

<h2 id="external-links">External links</h2>
<ul><li>Shafi Goldwasser and Silvio Micali, <a href="https://web.archive.org/web/20090319000035/http://groups.csail.mit.edu/cis/pubs/shafi/1984-jcss.pdf">Probabilistic Encryption</a>, Special issue of Journal of Computer and Systems Sciences, Vol. 28, No. 2, pages 270-299, April 1984</li>
<li>Freestyle, a randomized version of ChaCha for resisting offline brute-force and dictionary attacks <a href="https://github.com/arun-babu/freestyle">[1]</a>.</li></ul>

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

<ol>
<li id="fn:1"><p>Puthuparambil, Arun Babu; Thomas, Jithin Jose (2019-12-01). "Freestyle, a randomized version of ChaCha for resisting offline brute-force and dictionary attacks". Journal of Information Security and Applications. 49: 102396. arXiv:1802.03201. doi:10.1016/j.jisa.2019.102396. ISSN 2214-2126. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
</ol>

Probabilistic encryption open-in-new

Probabilistic encryption