Cryptography Reference
In-Depth Information
E
=
(
,
,
)
Gen
Enc
Dec
is the following:
is given input 1
n
and outputs, for a positive integer
t
,two
t
-tuples
1. The adversary
A
of messages
(
m
01
,...,
m
0
t
), (
m
11
,...,
m
1
t
), where len
(
m
0
i
)
=
len
(
m
1
i
)
for all
t
.
2. A key
k
is generated by running
Gen
i
=
1
...
1
n
(
)
and a random bit
b
is chosen. For each
i
=
1
...
t
the
challenge ciphertexts c
i
←
Enc
(
k
,
m
bi
)
are computed and given
to
A
.
outputs a bit
b
.
4. The output of the experiment is defined to be 1 if
b
3.
A
=
b
and 0 otherwise. If
PrivK
mult-ind-eav
A
,
E
(
n
)
=
1 then we say that
A
succeeded
.
Then the encryption scheme
is said to have
indistinguishable multiple encryptions
in the presence of an eavesdropper
if, for every PPT adversary
E
A
, there exists a
negligible function
negl
such that
PrivK
mult-ind-eav
(
(
)
=
)
≤
/
+
negl
(
),
Pr
n
1
1
2
n
A
,
E
where the probability is taken over the random bits used by
A
, as well as the random
bits used elsewhere in the experiment.
Remarks 3.8
1. By the preceding remarks,
POTP
has indistinguishable encryptions but not indis-
tinguishable multiple encryptions in the presence of an eavesdropper. But the
fact that indistinguishable multiple encryption is a much stronger concept that
indistinguishable single encryption may be better appreciated by noting that no
encryption scheme in which
Enc
is a
deterministic function of the key and the
message alone
can have indistinguishable multiple encryptions. Indeed, it suf-
fices to consider an adversary
A
who outputs the two following ordered pairs
0
n
0
n
0
n
1
n
of messages:
(or any other such
ordered pairs, in which the messages of the first pair are equal and the messages
of the second pair are different). Then if
(
m
01
=
,
m
02
=
), (
m
11
=
,
m
12
=
)
A
receives the ciphertexts
(
c
1
,
c
2
)
cor-
responding to the encryption of the messages of one of these pairs,
A
just checks
whether
c
1
=
c
2
. If the answer is affirmative
A
outputs 0, otherwise
A
outputs 1.
succeeds with probability 1.
2. Observe that if
Enc
is a probabilistic algorithm then the argument above breaks
down and
Then, because
Enc
is deterministic,
A
m
02
,
the corresponding ciphertexts can be (and, with high probability, should be)
different.
3. Note also that the first of these remarks allows the possibility that an encryption
scheme with a deterministic encryption algorithm might have multiple indistin-
guishable encryptions. For this it is necessary that the encryption algorithm be
stateful
, meaning that, apart from the key and the message, there is an additional
input called the
state
which is initialized in some specified way and updated
after each encryption operation, so that both parties using the scheme maintain
the same value of the state (usually a
counter
that increases by one unit after
A
does not succeed with probability 1 because even if
m
01
=
