Cryptography Reference
In-Depth Information
are uniformly random from Z
q
and the random variable
D
that equals to
hG,q,g,g
a
,g
b
,g
ab
i where a,b are uniformly random from Z
q
. A polynomial
time algorithm solves the DDH problem with advantage α if it can distinguish
D
from
R
with probability at least 1/2 + α.
The DDH-Assumption with ε-insecurity with respect to Gen suggests that
any algorithm that solves the DDH problem with advantage α satisfies α ≤ ε.
Having defined the necessary computational assumption we prove the se-
curity of the Boneh-Franklin scheme.
Theorem 3.11. The Boneh-Franklin scheme BF
`
is a public-key scheme
that is CPA ε-insecure in the sense of Definition
3.2
assuming the DDH-
Assumption with ε-insecurity holds with respect to Gen.
ition
3.2
. we rewrite the original game Exp
0
= Exp
BF
`
(1
n
) explicitly in
A
Experiment Exp
BF
A
(1
n
)
(tk,ek,sk
1
,...,sk
n
) ←KeyDist(1
n
)
aux ←A(ek)
m
0
,m
1
←M
b ←{0,1}; c ← Transmit(ek,m
1
)
b
0
←A(aux,ek,m
b
,c)
return 1 if and only if b = b
0
Fig. 3.3. The CPA security game for the Boneh-Franklin scheme.
Experiment Exp
1
. This experiment is identical to Exp
0
, with a slight modi-
fication in its encryption on line 4. Let the experiment Exp
1
, be the one where
the transmission is computed as an encryption of a random message that is
neither m
0
nor m
1
. More specifically, the 4th line is replaced with:
c ← Transmit(ek,m
R
)
where m
R
is a random string of the same length as the message m
0
and
m
1
.
Let p
1
be the probability that the experiment Exp
1
returns 1 and similarly
let p
0
be the probability that the experiment Exp
0
returns 1. Observe that in
Exp
1
, the encryption is no longer associated to m
0
,m
1
. Given that m
0
,m
1
are identically distributed it follows that the adversary's view is independent
of b and therefore p
1
=
2
.
On the other hand, let us assume that the adversary A has advantage of
at least ε
0
in being successful on the original experiment Exp
0
, i.e. we obtain
p
0
≥
2
+ ε
0
.
