Probabilistic encryption

Probabilistic encryption

Probabilistic encryption is the use of randomness in an encryption algorithm, so that when encrypting the same message several times it will, in general, yield different ciphertexts. The term "probabilistic encryption" is typically used in reference to public key encryption algorithms, however various symmetric key encryption algorithms achieve a similar property (e.g., block ciphers when used in a chaining mode such as CBC). To be semantically secure, that is, to hide even partial information about the plaintext, an encryption algorithm must be probabilistic.

Probabilistic encryption is particularly important when using public key cryptography. Suppose that the adversary 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 deterministic encryption algorithm is used, the adversary can simply try encrypting each of his 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.

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 deterministic algorithm. 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 OAEP integrate random padding in a manner that is secure using any trapdoor permutation.

The first provably-secure probabilistic public-key encryption scheme was proposed by Shafi Goldwasser and Silvio Micali, based on the hardness of the quadratic residuosity problem and had a message expansion factor equal to the public key size. More efficient probabilistic encryption algorithms include Elgamal, Paillier, MCC and various constructions under the random oracle model, including Optimal Asymmetric Encryption Padding (OAEP).

Example of probabilistic encryption using any trapdoor permutation:

* "x" - "single bit" plaintext
* "f" - trapdoor permutation (deterministic encryption algorithm)
* "b" - hard core predicate of "f"
* "r" - random string

{ m Enc}(x) = (f(r), x oplus b(r))

{ m Dec}(y, z) = b(f^{-1}(y)) oplus z

This is inefficient because only a single bit is encrypted. In other words, the message expansion factor is equal to the public key size.

Example of probabilistic encryption in the random oracle model:

* "x" - plaintext
* "f" - trapdoor permutation (deterministic encryption algorithm)
* "h" - random oracle (typically implemented using a publicly specified hash function)
* "r" - random string

{ m Enc}(x) = (f(r), x oplus h(r))

{ m Dec}(y, z) = h(f^{-1}(y)) oplus z

ee also

* Efficient Probabilistic Public-Key Encryption Scheme

External links

* Shafi Goldwasser and Silvio Micali, [http://theory.lcs.mit.edu/~cis/pubs/shafi/1984-jcss.pdf Probabilistic Encryption] , Special issue of Journal of Computer and Systems Sciences, Vol. 28, No. 2, pages 270-299, April 1984


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Deterministic encryption — A deterministic encryption scheme (as opposed to a probabilistic encryption scheme) is a cryptosystem which always produces the same ciphertext for a given plaintext and key, even over separate executions of the encryption algorithm. Examples of… …   Wikipedia

  • Efficient Probabilistic Public-Key Encryption Scheme — EPOC (Efficient Probabilistic Public Key Encryption) is a probabilistic public key encryption scheme.EPOC was developed in 1999 by T. Okamoto, S. Uchiyama and E. Fujisaki of NTT Labs in Japan. It is based on the random oracle model, in which a… …   Wikipedia

  • ElGamal encryption — In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public key cryptography which is based on the Diffie Hellman key agreement. It was described by Taher Elgamal in 1984 [Taher ElGamal, A Public Key… …   Wikipedia

  • Optimal asymmetric encryption padding — This article is about the padding scheme used in public key cryptography. For the division of the Thailand Ministry of Science Technology and Environment entitled Office of Atomic Energy for Peace, see [1]. In cryptography, Optimal Asymmetric… …   Wikipedia

  • Optimal Asymmetric Encryption Padding — This article is about the padding scheme used in public key cryptography. For the division of the Thailand Ministry of Science Technology and Environment entitled Office of Atomic Energy for Peace, see [http://www.oaep.go.th/english/index.html] …   Wikipedia

  • Blum-Goldwasser cryptosystem — The Blum Goldwasser (BG) cryptosystem is an asymmetric key encryption algorithm proposed by Manuel Blum and Shafi Goldwasser in 1984. Blum Goldwasser is a probabilistic, semantically secure cryptosystem with a constant size ciphertext expansion.… …   Wikipedia

  • Goldwasser-Micali cryptosystem — The Goldwasser Micali cryptosystem (GM) is an asymmetric key encryption algorithm developed by Shafi Goldwasser and Silvio Micali in 1982. GM has the distinction of being the first probabilistic public key encryption scheme which is provably… …   Wikipedia

  • Semantic security — is a widely used definition for security in an asymmetric key encryption algorithm. For a cryptosystem to be semantically secure, it must be infeasible for a computationally bounded adversary to derive significant information about a message… …   Wikipedia

  • McEliece cryptosystem — In cryptography, the McEliece cryptosystem is an asymmetric encryption algorithm developed in 1978 by Robert McEliece.[1] It was the first such scheme to use randomization in the encryption process. The algorithm has never gained much acceptance… …   Wikipedia

  • List of mathematics articles (P) — NOTOC P P = NP problem P adic analysis P adic number P adic order P compact group P group P² irreducible P Laplacian P matrix P rep P value P vector P y method Pacific Journal of Mathematics Package merge algorithm Packed storage matrix Packing… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”