Cryptography Reference

In-Depth Information

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).

5.1

Definitions

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).