Cryptography Reference
In-Depth Information
and the all-ones message). The latter definition is technical in nature and is referred to
as
indistinguishability of encryptions
.
We stress that the definitions presented here go way beyond saying that it is infeasible
to recover the plaintext from the ciphertext. The latter statement is indeed a minimal
requirement for a secure encryption scheme, but we claim that it is far too weak a
requirement: An encryption scheme typically is used in applications where obtaining
specific partial information on the plaintext endangers 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. Furthermore, even if
one wants to design an encryption scheme tailored to one's own specific applications,
it is rare (to say the least) that one has a precise characterization of all possible partial
information that can endanger these applications. Thus, we require that it be
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 also be preserved in such a case. That is, even in the presence of a
priori information on the plaintext, it is
infeasible
to obtain any (new) information
about the plaintext from the ciphertext (beyond what it 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 indistinguishability of encryptions is useful in
demonstrating the security of candidate constructions, as well as for arguing about
their usage as parts of larger protocols.
The Actual Definitions.
In both definitions, we consider (feasible) adversaries that
obtain, in addition to the ciphertext, auxiliary information that may depend on the po-
tential plaintext (but not on the key). By
E
(
x
) we denote the distribution of encryptions
of
x
, when the key is selected at random. To simplify the exposition, let us assume
that on security parameter
n
, the key-generation algorithm produces a key of length
n
,
whereas the scheme is used to encrypt messages of length
n
2
.
Definition B.1.1 (Semantic Security (Following [123])):
An encryption scheme
is
semantically secure
if for every feasible algorithm, A, there exists a feasible
algorithm B such that for every two functions f
,
h
:
{
0
,
1
}
∗
→{
0
,
1
}
∗
and all
sequences of pairs
(
X
n
,
z
n
)
n
∈
N
, where X
n
is a random variable ranging over
{
0
,
1
}
n
2
and
|
z
n
|
is of feasible
(in
n
)
length,
Pr
[
A
(
E
(
X
n
)
h
(
X
n
)
,
z
n
)
=
f
(
X
n
)]
<
Pr
[
B
(
h
(
X
n
)
,
z
n
)
=
f
(
X
n
)]
+
µ
(
n
)
where
is a negligible function. Furthermore, the complexity of B should be
related to that of A.
µ
What Definition B.1.1 says is that a feasible adversary does not gain anything by
looking at the ciphertext. That is, whatever information (captured by the function
f
)
it tries to compute about the ciphertext when given a priori information (captured by
the function
h
) can essentially be computed as efficiently from the available a priori
339
