Cryptography Reference
In-Depth Information
Lemma 21.1.15 Fixed-Square-DH
R Fixed-Inverse-DH.
g a be the input Fixed-Square-DH instance and let A be a perfect oracle for
the Fixed-Inverse-DH problem. Call A ( gh ) to get g (1 + a ) 1
Proof Let h
=
and call A ( gh 1 ) to get g (1 a ) 1 .
Multiplying these outputs gives
g (1 + a ) 1 g (1 a ) 1
g 2(1 a 2 ) 1 .
w
=
=
Calling A ( w 2 1
(mod r ) )gives g 1 a 2
from which we compute g a 2
as required.
We can now solve a non-fixed problem using an oracle for a fixed problem.
Lemma 21.1.16 Square-DH
R Fixed-CDH.
Proof Let g
G be fixed of prime order r and let A be a perfect Fixed-CDH oracle.
Let g 1 ,g 1
g a . We are required to compute
be the input Square-DH problem. Write g 1 =
g b 2
1
g ab 2 .
Call A ( g 1 ,g 1 ) to compute g a 2 b 2 . Use the perfect Fixed-CDH oracle as in Lemma 21.1.14
to compute g a 1 . Then compute A ( g a 2 b 2 ,g a 1 ) to get g ab 2 .
=
Since CDH
R Square-DH we finally obtain the main result of this section.
Corollary 21.1.17 Fixed-CDH and CDH are equivalent.
Proof We already showed Fixed-CDH
R CDH. Now, let A be a perfect Fixed-CDH oracle.
Lemma 21.1.16 together with Lemma 21.1.9 gives CDH
R Square-DH
R Fixed-CDH
as required.
Now suppose A only succeeds with noticeable probability > 1 / log( r ) c for some fixed
c . The reductions CDH
R Fixed-CDH require O (log( r )) oracle queries.
We perform self-correction (see Section 21.3 ) to obtain an oracle A for Fixed-CDH that
is correct with probability 1
R Square-DH
1 / (log( r ) c ) for some constant c ; by Theorem 21.3.8 this
requires O (log( r ) c log log( r )) oracle queries.
Exercise 21.1.18 It was assumed throughout this section that G has prime order r . Suppose
instead that G has order r 1 r 2 where r 1 and r 2 are odd primes and that g is a generator for
G . Which of the results in this section no longer necessarily hold? Is Fixed-CDH in
g
g r 1
equivalent to Fixed-CDH in
?
We end with a variant of the DDH problem.
Exercise 21.1.19 Let g have prime order r and let
{
x 1 ,...,x n }⊂Z
/r
Z
. For a subset
A
⊂{
1 ,...,n
}
define
g i A x i .
g A
=
The group decision Diffie-Hellman problem (GDDH) is: given g , g A for all proper
subsets A
g c (where c
{
1 ,...,n
}
, and h , to distinguish h
=
∈ Z
/r
Z
is chosen uniformly
at random) from g x 1 x 2 ··· x n . Show that GDDH
DDH.
Search WWH ::




Custom Search