Cryptography Reference
In-Depth Information
21
The Diffie-Hellman problem
This chapter gives a thorough discussion of the computational Diffie-Hellman problem
(CDH) and related computational problems. We give a number of reductions between
computational problems, most significantly reductions from DLP to CDH. We explain self-
correction of CDH oracles, study the static Diffie-Hellman problem, and study hard bits of
the DLP and CDH. We always use multiplicative notation for groups in this chapter (except
for in the Maurer reduction where some operations are specific to elliptic curves).
21.1 Variants of the Diffie-Hellman problem
We present some computational problems related to CDH, and prove reductions among
them. The main result is to prove that CDH and Fixed-CDH are equivalent. Most of the
results in this section apply to both algebraic groups (AG) and algebraic group quotients
(AGQ) of prime order r (some exceptions are Lemma 21.1.9 , Lemma 21.1.15 and, later,
Lemma 21.3.1 ). For the algebraic group quotients G considered in this topic then one can
obtain all the results by lifting from the quotient to the covering group G and applying the
results there.
A subtle distinction is whether the base element g
G is considered fixed or variable
in a CDH instance. To a cryptographer it is most natural to assume the generator is fixed,
since that corresponds to the usage of cryptosystems in the real world (the group G and
element g
G are fixed for all users). Hence, an adversary against a cryptosystem leads
to an oracle for a fixed generator problem. To a computational number theorist it is most
natural to assume the generator is variable, since algorithms in computational number
theory usually apply to all problem instances. Hence, both problems are studied in the
literature and when an author writes CDH it is sometimes not explicit which of the variants
is meant. Definition 20.2.1 was for the case when g varies. Definition 21.1.1 below is the
case when g is fixed. This issue is discussed in Section 5 of Shoup [ 495 ] and in Sadeghi
and Steiner [ 457 ] (where it is called “granularity”).
Definition 21.1.1 Let G be an algebraic group (AG) or algebraic group quotient (AGQ)
and let g
G .The Fixed-base computational Diffie-Hellman problem (Fixed-CDH)
with respect to g is: given ( g a ,g b ) to compute g ab .
Search WWH ::




Custom Search