Cryptography Reference
In-Depth Information
tuples
(i.e., the uniform distribution on tuples of the form (
g,g
a
,g
b
,g
ab
)
G
4
) and the
∈
uniform distribution on
G
4
.
Definition 20.2.4
Let (
G
n
,r
n
) be a family of cyclic groups
G
n
of order
r
n
,for
n
.A
DDH algorithm
for the family
G
n
is an algorithm
A
that takes as input a quadruple in
G
n
and outputs “yes” or “no”. The
advantage
of the DDH algorithm
A
is
∈ N
=
Pr
A
g,g
a
,g
b
,g
ab
=
Z
Adv(
A
)
“
yes
":
g
←
G
n
,a,b
← Z
/r
Pr
A
g,g
a
,g
b
,g
c
=
Z
.
−
“
yes
":
g
←
G
n
, a,b,c
← Z
/r
A DDH algorithm is called
successful
if the advantage is noticeable. The
DDH assumption
for the family of groups is that all polynomial-time (i.e., running time
O
(log(
r
n
)
c
)forsome
constant
c
) DDH algorithms have negligible advantage.
Lemma 20.2.5
DDH
≤
R
CDH
≤
R
DLP.
Exercise 20.2.6
Prove Lemma
20.2.5
.
Exercise 20.2.7
Definition
20.2.3
states that
r
is prime. Show that if (
g,g
a
,g
b
,g
c
)is
a quadruple of elements such that the order of
g
is
n
for some integer
n
where
n
has
some small factors (e.g., factors
l
|
n
such that
l
≤
log
2
(
n
)) then one can eliminate some
quadruples (
g,g
a
,g
b
,g
c
)
G
4
that are not valid DDH tuples by reducing to DDH instances
in subgroups of prime order. Show that this is enough to obtain a successful DDH algorithm
according to Definition
20.2.4
.
∈
20.2.2 Burmester-Desmedt key exchange
In the case of
n>
2 participants there is a generalisation of Diffie-Hellman key exchange
due to Burmester and Desmedt [
107
] that requires two rounds of broadcast. Let the partic-
ipants in the protocol be numbered as player 0 to player
n
−
1. In the first round, player
i
g
a
i
to the other players (or, at
(for 0
≤
i<n
) chooses a random 1
≤
a
i
<r
and sends
c
i
=
least, to player
i
−
1(mod
n
) and
i
1(mod
n
)). In the second round, player
i
computes
t
i
=
c
i
+
1(mod
n
)
c
−
1
+
1(mod
n
)
a
i
i
−
and sends it to all other players. Finally, player
i
computes
c
na
i
i
+
1(mod
n
)
t
n
−
1
1(mod
n
)
t
n
−
2
K
=
···
t
i
+
n
−
1(mod
n
)
.
i
+
i
+
2(mod
n
)
Lemma 20.2.8
Each participant in the Burmester-Desmedt protocol computes
g
a
0
a
1
+
a
1
a
2
+···
a
n
−
2
a
n
−
1
+
a
n
−
1
a
0
.
K
=
Exercise 20.2.9
Prove Lemma
20.2.8
.
