encryption algorithm denoted E ,anda decryption algorithm denoted
D . For every pair of encryption and decryption keys ( e, d ) generated
by G , and for every plaintext x , it holds that D d ( E e ( x )) = x ,where
E e ( x ) de = E ( e, x )and D d ( y ) de = D ( d, y ). The difference between the two
types of encryption schemes is reflected in the definition of security: the
security of a public-key encryption scheme should hold also when the
adversary is given the encryption-key, whereas this is not required for a
private-key encryption scheme. Below we focus on the public-key case
(and the private-key case can be obtained by omitting the encryption-
key from the sequence of inputs given to the adversary).
A good disguise should not reveal the person's height.
Shafi Goldwasser and Silvio Micali, 1982
For simplicity, we first consider the encryption of a single message
(which, for further simplicity, is assumed to be of length n ). 1 As implied
by the above discussion, a public-key encryption scheme is said to be
secure if it is infeasible to gain any information about the plaintext by
looking at the ciphertext (and the encryption-key). That is, whatever
information about the plaintext one may compute from the cipher-
text and some a-priori information, can be essentially computed as
eciently from the a-priori information alone. This fundamental defi-
nition of security (called semantic security) turns out to be equivalent
to saying that, for any two messages, it is infeasible to distinguish
the encryption of the first message from the encryption of the second
message, even when given the encryption-key. Both definitions were
introduced by Goldwasser and Micali (80).
Definition 5.1. (semantic security (following (80), revisited (64))):
A public-key encryption scheme ( G, E, D )is semantically secure if for
1 In the case of public-key schemes no generality is lost by these simplifying assumptions,
but in the case of private-key schemes one should consider the encryption of polynomially-
many messages (as we do below).