Cryptography Reference
In-Depth Information
information alone. In particular, the ciphertext does not help in (feasibly) computing
the least significant bit of the plaintext or any other information regarding the plaintext.
This holds for any distribution of plaintexts (captured by the random variable
X
n
). We
now turn to an equivalent definition.
Definition B.1.2 (Indistinguishability of Encryptions (Following [123])):
An
encryption scheme has
indistinguishable encryptions
if for every feasible algo-
rithm A and all sequences of triples
(
x
n
,
y
n
,
z
n
)
n
∈N
, where
|
x
n
|=|
y
n
|=
n
2
and
|
z
n
|
is of feasible
(in
n
)
length,
|
Pr
[
A
(
E
(
x
n
)
,
z
n
)
=
1]
−
Pr
[
A
(
E
(
y
n
)
,
z
n
)
=
1]
|
<µ
(
n
)
where
µ
is a negligible function.
In particular,
z
n
may equal (
x
n
,
y
n
). Thus, it is infeasible to distinguish the encryptions
of any two fixed messages such as the all-zeros message and the all-ones message.
Theorem B.1.3:
An encryption scheme is semantically secure if and only if it has
indistinguishable encryptions.
Probabilistic Encryption.
It is easy to see that a secure public-key encryption scheme
must employ a probabilistic (i.e., randomized)
encryption
algorithm. Otherwise, given
the encryption key as (additional) input, it is easy to distinguish the encryption of the
all-zeros message from the encryption of the all-ones message. The same holds for
private-key encryption schemes when considering the security of encrypting several
messages (rather than a single message as done before).
1
This explains the linkage
between the foregoing robust security definitions and the
randomization paradigm
(discussed later).
B.1.2. Constructions
Private-key encryption schemes can be constructed based on the existence of one-way
functions. In contrast, the known constructions of public-key encryption schemes seem
to require stronger assumptions (such as the existence of trapdoor permutations).
B.1.2.1. Private-Key Schemes
It is common practice to use “pseudorandom generators” as a basis for private-key
stream ciphers. We stress that this is a very dangerous practice when the “pseudoran-
dom generator” is easy to predict (such as the linear congruential generator or some
modifications of it that output a constant fraction of the bits of each resulting num-
ber [38, 84]). However, this common practice can become sound provided one uses
pseudorandom generators as defined in Section 3.3. Thus, we obtain a
private-key
stream cipher
that allows us to encrypt a stream of plaintext bits. Note that such a
1
Here, for example, using a deterministic encryption algorithm allows the adversary to distinguish two encryp-
tions of the same message from the encryptions of a pair of different messages.
