Cryptography Reference
In-Depth Information
the distinguisher advantage
Adv
prf
D
F
(
n
)
as a function of the advantages of
A
in the
,
IND-CPA experiments for iCTR and CTR.
D
runs as follows:
n
n
•
Abit
b
1
is chosen and
D
is given oracle access to a function
f
:{
0
,
1
}
→{
0
,
1
}
n
which is either
f
:=
F
k
for
k
←{
0
,
1
}
if
b
1
=
1 or a random function otherwise.
on input 1
n
and when
n
,
D
chooses
•
D
runs
A
A
outputs messages
m
0
,
m
1
∈{
0
,
1
}
n
and returns to
a random bit
b
←{
0
,
1
}
A
the challenge ciphertext
c
computed
as follows:
n
.
- If the blocks of
m
b
are
m
b
1
,...,
-
ctr
0
←{
0
,
1
}
m
bl
,
D
queries the oracle and obtains the values
:=
(
ctr
0
+
)
=
,...,
l
.
-
c
is the ciphertext whose blocks are
c
i
r
i
f
i
,for
i
1
:=
r
i
⊕
m
bi
.
•
A
's oracle queries are answered by
D
by returning a ciphertext computed as in
the preceding item.
outputs a bit
b
,
D
outputs a bit
b
1
defined as
b
1
=
1if
b
=
b
and
b
1
=
•
When
A
0
otherwise.
Let us now analyze
D
's advantage in the distinguishing experiment. If
D
is given
oracle access to a random function from
n
, then the view of
{
0
,
1
}
A
when run as
in the experiment
PrivK
ind-cpa
indicated above is identical to the view of
)
since a random function is used to 'encrypt' the messages. On the other hand, if
D
is given oracle access to some
F
k
, for a randomly chosen
k
, then the view of
A
A,
iCTR
(
n
A
is the
same as in experiment
PrivK
ind-cpa
's oracle queries,
D
computes the answer in the same way as when encrypting the message with CTR
and key
k
.
Now let
A
,
CTR
(
n
)
because when answering
A
PrivK
ind-cpa
PrivK
ind-cpa
1
ε(
n
)
=
Pr
(
A,
CTR
(
n
)
=
1
)
−
2
and
ν(
n
)
=
Pr
(
A,
iCTR
(
n
)
=
1
1
in the IND-CPA experiments
corresponding to CTR and iCTR, respectively, and we have just seen that
)
−
2
. Then
ε(
n
)
and
ν(
n
)
are the advantages of
A
ν(
n
)
≤
2
2
n
−
1
. Since the latter function is negligible, we have that
q
(
n
)
ν(
n
)
is negligible too and
is also negligible. Since
b
1
our goal is to show that
ε(
n
)
=
1 precisely when
A
PrivK
ind-cpa
1
b
1
=
succeeds, we have that Pr
(
1
|
b
1
=
1
)
=
Pr
(
A,
CTR
(
n
)
=
1
)
=
2
+
ε(
n
)
PrivK
ind-cpa
1
b
1
=
and Pr
. The advantage of
D
in the distinguishing experiment (see Definition 4.2) is equal to the absolute value
of the difference between these two values, namely:
(
1
|
b
1
=
0
)
=
Pr
(
A,
iCTR
(
n
)
=
1
)
=
2
+
ν(
n
)
Adv
prf
D
b
1
=
b
1
=
F
(
n
)
=|
Pr
(
1
|
b
1
=
1
)
−
Pr
(
1
|
b
1
=
0
)
|=|
ε(
n
)
−
ν(
n
)
|
,
This advantage is negligible because we are assuming that
F
is a pseudo-random
function and, since
ν(
)
ε(
)
n
is also negligible, we see that so is
n
. Therefore, CTR is
CPA secure.
