Cryptography Reference
In-Depth Information
A
adversary
is any algorithm (which does not require any input to output two equal-
length messages, so the security parameter does not appear here). Show that
E
is
PrivK
ind-eav
A,E
perfectly secret if and only if Pr
(
=
1
)
=
1
/
2.
We have given an informal argument that the fixed-length pseudo-random one-
time pad presented in Definition 3.5 is computationally secure in the intuitive sense
mentioned in Remark 3.3. The formal version of this security concept is IND-EAV
security as defined in Definition 3.22. Thus we can now give a more precise formu-
lation of this result:
Theorem 3.11
The pseudo-random one-time pad of Definition 3.5 is a fixed-length
private-key encryption scheme that has indistinguishable encryptions in the presence
of an eavesdropper.
Sketch of proof.
Observe that if
POTP
denotes the fixed-length pseudo-random
one-time pad then, as the output of the PRG used in
POTP
is, to a PPT algorithm
A
, indistinguishable from a truly random string, from the point of view of such an
A
,
POTP
behaves exactly as the one-time pad. By Exercise 3.19, the one-time pad
has indistinguishable encryptions in the presence of an eavesdropper. Therefore such
an
should be unable to succeed with non-negligible probability in the experiment
PrivK
ind-eav
A
A
,
POTP
(
n
)
. We refer to [109, Theorem 3.16] for a detailed proof.
Corollary 3.1
The BBS-based pseudo-random one-time pad is IND-EAV secure
under the factoring assumption.
Proof
It is a consequence of the preceding theorem and Theorem 3.10.
The preceding discussion of security refers to the situation in which the eaves-
dropper is given a unique ciphertext and tries to guess to which of two messages
it corresponds. But in practice, an encryption scheme will often be used for multi-
ple encryptions (with the same key). This situation is completely different regarding
security for, as we have seen, both the one-time pad and the pseudo-random one-time
pad are secure only when the key is not reused. More generally, if an eavesdropper
observes a repeated ciphertext, it can guess that a message has been resent and this in
itself is a significant leak of information that may be—and there are historical exam-
ples of this—useful to an attacker. In some cases this could lead to a more important
information leakage. A very simple scenario in which this situation occurs is the
following. Suppose that a ciphertext is sent. It is not infrequent that the eavesdropper
may learn a posteriori—by whatever means—information about the plaintext. Then,
if the same message is later resent encrypted by means of a deterministic algorithm,
the eavesdropper gains information about the new message.
We may now define the concept of security for multiple encryptions. We keep the
same notation as in Definition 3.21.
Definition 3.23
The
private-key eavesdropping multiple-encryption indistinguisha-
bility
PrivK
mult-ind-eav
A,E
experiment
(
n
)
,
for a private-key encryption scheme
