Cryptography Reference
In-Depth Information
n
instead of the forward cipher function
F
k
and to prove that this scheme is CPA secure. The scheme obtained this way
is not efficient because there is no efficient way to describe the random function.
The function might be represented by a table storing the
n
-bit value of
f
n
:{
,
}
→{
,
}
truly random function
f
0
1
0
1
(
x
)
for
2
n
bits of storage and this description has
exponential length in
n
. However, this is irrelevant for our purpose and the analysis
of the idealized scheme lets us isolate the possible weaknesses of CTR mode itself,
since we are assuming an ideal block cipher. Thus, proving that this idealized scheme
is CPA secure shows that CTR mode is good from a security point of view and it
only remains to show, by exploiting the pseudo-randomness of
F
, that CPA security
is preserved when we replace
f
by
F
. This is a consequence of the fact that if an
adversary
n
, requiring a total of
n
each
x
∈{
0
,
1
}
·
attacking the CTR scheme (with underlying block cipher
F
) has non-
negligible advantage then it can be used as a subroutine by a distinguisher that will
be able to distinguish
F
from a random
f
also with non-negligible advantage. The
distinguisher
D
runs
A
A
using its own queries to the oracle to answer
A
's queries—
acts exactly as in experiment
PrivK
ind
−
cpa
so that
A
A,
CTR
(
n
)
—and observes whether
A
succeeds or not. In the first case,
D
guesses that its oracle is a pseudo-random
function and, otherwise, that it is a random function.
So let us prove that the idealized scheme iCTR is CPA secure. The key generation
algorithm for this scheme takes as input a security parameter 1
n
and outputs a key,
which is now just a random function
f
n
n
)
{
0
,
1
}
, while the encryption
algorithm uses
f
instead of
F
k
.Let
ctr
0
be the initial random value of the counter
used to encrypt the challenge ciphertext in the
PrivK
ind-cpa
←
(
{
0
,
1
}
experiment and let
ctr
i
be the initial value used when the encryption oracle answers the
i
th query of
A,
iCTR
(
n
)
A
.
A
We assume that
makes a polynomial number of queries to the oracle and also that
the messages
m
0
,
m
1
, that
outputs at the start of the experiment have a polynomial
number of blocks (or, equivalently, polynomial length), where the term polynomial
is relative to the security parameter 1
n
used by the key generation algorithm (here
n
is the block length of
F
and, for simplicity, we may also assume that
n
is the key
length of
F
). Thus we may consider a polynomial upper bound
q
A
on the
number of oracle queries and also on the number of blocks in each encryption, and
hence we may suppose that the random function
f
is applied to
=
q
(
n
)
ctr
i
+
1
,
ctr
i
+
2
,...,
ctr
i
+
l
i
,
where
i
0 corresponds to the counter sequence used to obtain the challenge
ciphertext and the remaining values of
i
for which 1
=
≤
i
(and that are also
≤
q
)to
the counter sequence used in the successive queries of
A
to the oracle. If, for each
1
l
0
,the
j
th block of the challenge ciphertext was obtained by using a value
of the counter equal to
ctr
0
+
≤
j
≤
j
, for any
i
in
j
, which is different from
ctr
i
+
j
the query sequence and any 1
≤
≤
l
i
, then the values
r
t
=
f
(
ctr
0
+
t
)
,for
n
t
=
1
,...,
l
0
are, in the view of
A
, randomly and uniformly distributed in
{
0
,
1
}
since
f
was not applied to any of these values during
's oracle queries. Thus these
values yield a one-time pad when they are Xor-ed with the message blocks and hence
A
