Cryptography Reference

In-Depth Information

Further discussion:
We stress that (the equivalent) Definitions 5.1

and 5.2 go way beyond saying that it is infeasible to recover the plain-

text from the ciphertext . The latter statement is indeed a minimal

requirement from a secure encryption scheme, but is far from being

a sucient requirement. Typically, encryption schemes are used in

applications where even obtaining partial information on the plain-

text may endanger the security of the application. When designing

an application-independent encryption scheme, we do not know which

partial information endangers the application and which does not. Fur-

thermore, even if one wants to design an encryption scheme tailored to

a specific application, it is rare (to say the least) that one has a precise

characterization of all possible partial information that endanger this

application. Thus, we need to require that it is infeasible to obtain any

information about the plaintext from the ciphertext . Furthermore, in

most applications the plaintext may not be uniformly distributed and

some a-priori information regarding it is available to the adversary. We

require that the secrecy of all partial information is preserved also in

such a case. That is, even in presence of a-priori information on the

plaintext , it is infeasible to obtain any (new) information about the

plaintext from the ciphertext (beyond what is feasible to obtain from

the a-priori information on the plaintext ). The definition of semantic

security postulates all of this. The equivalent definition of indistin-

guishability of encryptions is useful in demonstrating the security of

candidate constructions as well as for arguing about their effect as part

of larger protocols.

Security of multiple messages:
Definitions 5.1 and 5.2 refer to the

security of an encryption scheme that is used to encrypt a single plain-

text (per generated key). Since the plaintext may be longer than the

key,
3
these definitions are already non-trivial, and an encryption scheme

satisfying them (even in the private-key model) implies the existence

of one-way functions. Still, in many cases, it is desirable to encrypt

3
Recall that for sake of simplicity we have considered only messages of length
n
, but the

general definitions refer to messages of arbitrary (polynomial in
n
) length. We comment

that, in the general form of Definition 5.1, one should provide the length of the message

as an auxiliary input to both algorithms (
A
and
B
).