| Semantic Security |
Article Index for Semantic |
Website Links For Semantic |
Information AboutSemantic Security |
| CATEGORIES ABOUT SEMANTIC SECURITY | |
| theory of cryptography | |
|
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 the property of Ciphertext Indistinguishability [2]. This equivalence allowed for security proofs of practical cryptosystems, and consequently the indistinguishability definition is used more commonly than the original definition of semantic security. Indistinguishability under Chosen Plaintext Attack ( IND-CPA ) is commonly defined by the following Game : # A probabilistic polynomial time-bounded adversary is given a public key, which it may use to generate any number of ciphertexts (within polynomial bounds). # The adversary generates two equal-length messages and , and transmits them to a challenge oracle along with the public key. # The challenge oracle selects one of the messages by flipping a uniformly-weighted coin, encrypts the message under the public key, and returns the resulting ciphertext 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 (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 and and compare these encryptions with the returned ciphertext 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, non-semantically-secure 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). REFERENCES
|
|
|