Cryptography Reference
In-Depth Information
succeeds in the
PrivK
ind-cpa
the probability that
A
A
,
iCTR
(
n
)
experiment is exactly 1
/
2in
this case.
Suppose now that, on the contrary, there exist indices
i
,
j
l
0
and
j
≤
≤
l
i
such
j
. Then the preceding argument does not apply because
the adversary might deduce the value
f
that
ctr
0
+
j
=
ctr
i
+
from its
i
th oracle query and Xor
it with the corresponding block of the challenge ciphertext to determine which of the
two messages
m
0
,
m
1
was encrypted. We do not need to know the exact probability
of success of
(
ctr
0
+
j
)
in case this happens, and we may assume that it is very high (even
equal to 1). We can show that this case happens with negligible probability and hence
the advantage of
A
in experiment
PrivK
ind-cpa
will be negligible. Let us give an
upper bound on the probability that a repeated value of the counter occurs. For this
we may assume that
i
varies from 1 to
q
and that
l
i
A
A,
iCTR
(
n
)
=
q
for all
i
=
0
,...,
q
. Then
we want to compute the probability that, for some
i
,
j
∈{
1
,...
q
}
,
ctr
0
+
j
∈
[
ctr
i
+
1
,
ctr
i
+
q
]
. This is equivalent to
ctr
0
∈[
ctr
i
−
q
+
1
,
ctr
i
+
q
−
1
]
for some
i
1 and there are
q
of
them so, assuming that these intervals are disjoint—which maximizes the probability
of a repeated counter value—we have that the total number of values of
ctr
0
that
produce a repeated counter value is
∈{
1
,...
q
}
. Each of these intervals has length 2
q
−
2
q
2
. Since all the
ctr
i
are randomly chosen,
the probability that
ctr
0
is equal to one of these values is
≤
2
q
2
2
n
q
2
2
n
−
1
.
≤
/
=
/
Therefore, the probability that a repeated counter occurs is bounded by
q
2
2
n
−
1
.If
we denote by
Rep
the event that a repeated counter value occurs and by
NoRep
its
complement, then by Proposition 2.1 we have that:
/
Pr
(
PrivK
ind-cpa
A,
iCTR
(
n
)
=
1
)
=
Pr
(
PrivK
ind-cpa
iCTR
(
n
)
=
1
|
Rep
)
·
Pr
(
Rep
)
+
Pr
(
PrivK
ind-cpa
A,
A,
iCTR
(
n
)
=
1
|
NoRep
)
·
Pr
(
NoRep
).
PrivK
ind-cpa
We have just proved that Pr
(
A
,
iCTR
(
n
)
=
1
|
NoRep
)
=
1
/
2 and Pr
(
Rep
)
≤
PrivK
ind-cpa
q
2
2
n
−
1
. Combining these bounds with the obvious bounds Pr
/
(
A,
iCTR
(
n
)
=
1
|
Rep
)
≤
1 and Pr
(
NoRep
)
≤
1 and substituting these values in the previous
equality, we obtain the bound:
2
2
n
−
1
.
1
2
+
q
(
n
)
PrivK
ind-cpa
Pr
(
A
,
iCTR
(
n
)
=
1
)
≤
2
n
−
1
is a negligible function and hence the
idealized scheme iCTR is CPA secure according to Definition 3.24.
Next we turn to the counter scheme CTR and we use the fact that iCTR is CPA
secure to prove that CTR is CPA secure too. Let
is polynomial in
n
,
q
2
Since
q
(
n
)
/
be an adversary attacking the CPA
security of CTR. We construct a distinguisher
D
that, using
A
as a subroutine, tries
to determine whether a given function
f
is equal to some
F
k
for a randomly chosen
key or is randomly chosen in
A
n
n
)
{
0
,
1
}
(
{
0
,
1
}
(see Definition 4.2) and we compute
