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