Cryptography Reference

In-Depth Information

Private-key and public-key encryption schemes secure against cho-

sen ciphertext attacks can be constructed under (almost) the same

assumptions that suce for the construction of the corresponding pas-

sive schemes. Specifically:

Theorem 5.3.
(folklore, see (67, Sec. 5.4.4.3)):
Assuming the exis-

tence of
one-way functions
,thereexist
private-key
encryption schemes

that are secure against chosen ciphertext attack.

Theorem 5.4.
((104; 50), using (29; 56), see (67, Sec. 5.4.4.4)):

Assuming the existence of
enhanced
5
trapdoor permutations
,thereexist

public-key
encryption schemes that are secure against chosen ciphertext

attack.

Both theorems are proved by constructing encryption schemes in which

the adversary's gain from a chosen ciphertext attack is eliminated by

making it infeasible (for the adversary) to obtain any useful knowl-

edge via such an attack. In the case of private-key schemes (i.e.,

Theorem 5.3), this is achieved by making it infeasible (for the adver-

sary) to produce legitimate ciphertext s (other than those explic-

itly given to it, in response to its request to encrypt plaintext s of

its choice). This, in turn, is achieved by augmenting the ciphertext

with an “authentication tag” that is hard to generate without knowl-

edge of the encryption-key; that is, we use a message-authentication

scheme (as defined in Section 6). In the case of public-key schemes

(i.e., Theorem 5.4), the adversary can certainly generate ciphertext s

by itself, and the aim is to to make it infeasible (for the adversary) to

produce legitimate ciphertext s without “knowing” the corresponding

plaintext . This, in turn, will be achieved by augmenting the plain-

text with a non-interactive zero-knowledge “proof of knowledge” of the

corresponding plaintext .

5
Loosely speaking, the enhancement refers to the hardness condition of Definition 2.2, and

requires that it be hard to recover
f
−
i
(
y
) also when given the coins used to sample
y

(rather than merely
y
itself). See (67, Apdx. C.1).