World Library  
Flag as Inappropriate
Email this Article

Semantic security

Article Id: WHEBN0000960585
Reproduction Date:

Title: Semantic security  
Author: World Heritage Encyclopedia
Language: English
Subject: Strong secrecy, Blum–Goldwasser cryptosystem, Initialization vector, Block cipher, Integrated Encryption Scheme
Publisher: World Heritage Encyclopedia

Semantic security

In cryptography, a cryptosystem is semantically secure if any probabilistic, polynomial-time algorithm (PPTA) that is given the ciphertext of a certain message m (taken from any distribution of messages), and the message's length, cannot determine any partial information on the message with probability non-negligibly higher than all other PPTA's that only have access to the message length (and not the ciphertext).[1] In other words, knowledge of the ciphertext (and length) of some unknown message does not reveal any additional information on the message that can be feasibly extracted. This concept is the computational complexity analogue to Shannon's concept of perfect secrecy. Perfect secrecy means that the ciphertext reveals no information at all about the plaintext, whereas semantic security implies that any information revealed cannot be feasibly extracted.[2][3]:378–381


  • History 1
  • Symmetric-key cryptography 2
  • Public-key cryptography 3
  • References 4


The notion of semantic security was first put forward by Goldwasser and Micali in 1982.[1] However, the definition they initially proposed offered no straightforward means to prove the security of practical cryptosystems. Goldwasser/Micali subsequently demonstrated that semantic security is equivalent to another definition of security called ciphertext indistinguishability under chosen-plaintext attack.[4] This latter definition is more common than the original definition of semantic security because it better facilitates proving the security of practical cryptosystems.

Symmetric-key cryptography

In the case of symmetric-key algorithm cryptosystems, an adversary must not be able to compute any information about a plaintext from its ciphertext. This may be posited as an adversary, given two plaintexts of equal length and their two respective ciphertexts, cannot determine which ciphertext belongs to which plaintext.

Public-key cryptography

For an asymmetric key encryption algorithm cryptosystem to be semantically secure, it must be infeasible for a computationally bounded adversary to derive significant information about a message (plaintext) when given only its ciphertext and the corresponding public encryption key. Semantic security considers only the case of a "passive" attacker, i.e., one who generates and observes ciphertexts using the public key and plaintexts of her choice. Unlike other security definitions, semantic security does not consider the case of chosen ciphertext attack (CCA), where an attacker is able to request the decryption of chosen ciphertexts, and many semantically secure encryption schemes are demonstrably insecure against chosen ciphertext attack. Consequently, semantic security is now considered an insufficient condition for securing a general-purpose encryption scheme. (This is generally an inaccurate description of reality.)

Indistinguishability under Chosen Plaintext Attack (IND-CPA) is commonly defined by the following experiment:[5]

  1. A random pair (pk,sk) is generated by running Gen(1^n).
  2. A probabilistic polynomial time-bounded adversary is given the public key pk , which it may use to generate any number of ciphertexts (within polynomial bounds).
  3. The adversary generates two equal-length messages m_0 and m_1, and transmits them to a challenge oracle along with the public key.
  4. The challenge oracle selects one of the messages by flipping a fair coin (selecting a random bit b \in {0,1}), encrypts the message m_b under the public key, and returns the resulting challeging ciphertext c to the adversary.

The underlying cryptosystem is IND-CPA (and thus semantically secure under chosen plaintext attack) if the adversary cannot determine which of the two messages was chosen by the oracle, with probability significantly greater than 1/2 (the success rate of random guessing). Variants of this definition define indistinguishability under chosen ciphertext attack and adaptive chosen ciphertext attack (IND-CCA, IND-CCA2).

Because the adversary possesses the public encryption key in the above game, a semantically secure encryption scheme must by definition be probabilistic, possessing a component of randomness; if this were not the case, the adversary could simply compute the deterministic encryption of m_0 and m_1 and compare these encryptions with the returned ciphertext c to successfully guess the oracle's choice.

Semantically secure encryption algorithms include Goldwasser-Micali, El Gamal and Paillier. These schemes are considered provably secure, as their semantic security can be reduced to solving some hard mathematical problem (e.g., Decisional Diffie-Hellman or the Quadratic Residuosity Problem). Other, semantically insecure algorithms such as RSA, can be made semantically secure (under stronger assumptions) through the use of random encryption padding schemes such as Optimal Asymmetric Encryption Padding (OAEP).


  1. ^ a b S. Goldwasser and S. Micali, Probabilistic encryption & how to play mental poker keeping secret all partial information, Annual ACM Symposium on Theory of Computing, 1982.
  2. ^ Shannon, Claude (1949). "Communication Theory of Secrecy Systems". Bell System Technical Journal 28 (4): 656–715.  
  3. ^ Goldreich, Oded. Foundations of Cryptography: Volume 2, Basic Applications. Vol. 2. Cambridge university press, 2004.
  4. ^ S. Goldwasser and S. Micali, Probabilistic encryption. Journal of Computer and System Sciences, 28:270-299, 1984.
  5. ^ Katz, Jonathan; Lindell, Yehuda (2007). Introduction to Modern Cryptography: Principles and Protocols. Chapman and Hall/CRC. 
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.