Assumptions Related to Discrete Logarithms:
Why Subtleties Make a Real Di¬erence

Ahmad-Reza Sadeghi and Michael Steiner

Fachrichtung Informatik, Universit¨t des Saarlandes, D-66123 Saarbr¨cken, Germany,
a u
{sadeghi,steiner}@cs.uni-sb.de



Abstract. The security of many cryptographic constructions relies on
assumptions related to Discrete Logarithms (DL), e.g., the Di¬e-Hellman,
Square Exponent, Inverse Exponent or Representation Problem assump-
tions. In the concrete formalizations of these assumptions one has some
degrees of freedom o¬ered by parameters such as computational model,
the problem type (computational, decisional) or success probability of
adversary. However, these parameters and their impact are often not
properly considered or are simply overlooked in the existing literature.
In this paper we identify parameters relevant to cryptographic applica-
tions and describe a formal framework for de¬ning DL-related assump-
tions. This enables us to precisely and systematically classify these as-
sumptions.
In particular, we identify a parameter, termed granularity, which de-
scribes the underlying probability space in an assumption. Varying gran-
ularity we discover the following surprising result: We prove that two DL-
related assumptions can be reduced to each other for medium granularity
but we also show that they are provably not reducible with generic algo-
rithms for high granularity. Further we show that reductions for medium
granularity can achieve much better concrete security than equivalent
high-granularity reductions.


Keywords: Complexity Theory, Cryptographic Assumptions, Generic Algorithms,
Discrete Logarithms, Di¬e-Hellman, Square Exponent, Inverse Exponent.


1 Introduction

Most modern cryptographic algorithms rely on assumptions on the computa-
tional di¬culty of some particular number-theoretic problem. One well-known
class of assumptions is related to the di¬culty of computing discrete loga-
rithms in cyclic groups [1]. In this class a number of variants exists. The most
prominent ones besides Discrete Logarithm (DL) itself are the computational
and decisional Di¬e-Hellman (DH) assumptions [2, 3, 4] and their generaliza-
tion [5, 6]. Less known assumptions are Matching Di¬e-Hellman [7, 8], Square
Exponent1 (SE) [10, 11], and the Inverse Exponent (IE) [12], an assumption also
1
This problem is called Squaring Di¬e-Hellman in [9]

B. P¬tzmann (Ed.): EUROCRYPT 2001, LNCS 2045, pp. 243“260, 2001.
c Springer-Verlag Berlin Heidelberg 2001
244 Ahmad-Reza Sadeghi and Michael Steiner

implicitly required for the security of [13, 14]. Several papers have studied rela-
tions among these assumptions, e.g., [15, 16, 17, 18, 9].
In the concrete formalizations of these assumptions one has various degrees
of freedom o¬ered by parameters such as computational model, problem type
(computational, decisional or matching) or success probability of adversary. How-
ever, such aspects are often not precisely considered in the literature and related
consequences are simply overlooked. In this paper, we address these aspects
by identifying the parameters relevant to cryptographic assumptions. Based on
this, we present an understandable formal framework and a notation for de¬ning
DL-related assumptions. This enables us to precisely and systematically classify
these assumptions.
Among the speci¬ed parameters, we focus on a parameter we call granularity
of the probability space which underlies an assumption. Granularity de¬nes what
part of the underlying algebraic structure (i.e., algebraic group and generator) is
part of the probability space and what is ¬xed in advance: For high granularity
an assumption has to hold for all groups and generators; for medium granular-
ity the choice of the generator is included in the probability space and for low
granularity the probability is taken over both the choice of the group and the
generator. Assumptions with lower granularity are weaker than those with higher
granularity. Yet not all cryptographic settings can rely on the weaker variants:
Only when the choice of the system parameters is guaranteed to be random one
can rely on a low-granularity assumption. Consider an anonymous payment sys-
tem where the bank chooses the system parameters. To base the security of such
a system a-priori on a low-granularity assumption would not be appropriate. A
cheating bank might try to choose a weak group with trapdoors (easy problem
instances) [19] to violate the anonymity of the customer. An average-case low-
granular assumption would not rule out that in¬nitely many weak groups exist
even though the number of easy problem instances is asymptotically negligible.
However, if we choose the system parameters of the payment system through a
random yet veri¬able process we can resort to a weaker assumption with lower
granularity. Note that to our knowledge no paper on anonymous payment sys-
tems does address this issue properly. Granularity was also overlooked in di¬er-
ent contexts, e.g., [3] ignores that low-granular assumptions are not known to
be random self-reducible which leads to a wrong conclusion.
In this paper we show that varying granularity can lead to surprising results.
We extend the results of [9] to the problem class IE, i.e., we prove statements
on relations between IE, DH and SE for both computational and decisional
variants in the setting of [9] which corresponds to the high-granular case. We then
consider medium granularity (with other parameters unchanged) and show the
impact: We prove that the decisional IE and SE assumptions are equivalent for
medium granularity whereas this is provably not possible for their high-granular
variants, at least not in the generic model [15]. We also show that reductions
between computational IE, SE and DH can o¬er much better concrete security
for medium granularity than their high-granular analogues.
Assumptions Related to Discrete Logarithms 245

2 Terminology

2.1 Algebraic Structures

The following terms are related to the algebraic structures underlying an as-
sumption.

Group G: All considered assumptions are based on cyclic ¬nite groups. For
brevity, however, we will omit the “cyclic ¬nite” in the sequel and refer to them
simply as “groups”. The order of a group is associated with a security parameter
k which classi¬es the group according to the di¬culty of certain problems (e.g.,
DL).
Group family G: A set of groups with the “same” structure/nature. An example
is the family of the groups used in DSS [20], i.e., unique subgroups of — of order
 




p
q with p and q prime, |q| ≈ 2k and p = rq + 1 for an integer r su¬ciently
large to make DL hard to compute in security parameter k. Other examples are
non-singular elliptic curves or composite groups — with n a product of two safe
 




n
primes.
Generator g: In the DL settings, we also need a generator g which generates
the group G, i.e., ∀y ∈ G ∃x ∈ |G| : y = g x .
 




Structure instance SI : The structure underlying the particular problem. In
our case this means a group G together with a non-empty tuple of generators
gi . As a convention we abbreviate g1 to g if there is only a single generator
associated with a given structure instance.


2.2 Problem Families

The following two de¬nitions characterize a particular problem underlying an
assumption.

Problem family P: A family of abstract and supposedly di¬cult relations. Ex-
amples are Discrete Logarithm (DL), Di¬e-Hellman (DH), or the Representation
Problem (RP). Note that the problem family ignores underlying algebraic groups
and how parameters are chosen. Further, note that in the de¬nition of problem
families we don™t distinguish between decisional or computational variants of a
problem.
Problem instance PI : A list of concrete parameters fully describing a par-
ticular instance of a problem family, i.e., a structure instance SI and a tuple
(priv , publ , sol ) where priv is the tuple of secret values used to instantiate that
problem, publ is the tuple of information publicly known on that problem and
sol is the solution of that problem instance. This presentation achieves a certain
uniformity of description and allows a generic de¬nition of problem types. For
convenience, we de¬ne PI SI , PI P , PI publ , PI priv and PI sol to be the projection
of a problem instance PI to its structure instance, problem family and public,
private and solution part, respectively. When not explicitly stated, we can as-
sume that priv consists always of elements from |G| and publ and sol consists
 
246 Ahmad-Reza Sadeghi and Michael Steiner

of elements from G. Furthermore, the structure instance SI is assumed to be
publicly known.
If we take the DH problem for integers modulo a prime p as an example, PI DH is
de¬ned by the tuple ((( —, p), (g)), ((x, y), (g x , g y ), (g xy ))) with PI DH P := DH,
 




p
PI DH :=(( p, p), (g)), PI DH priv :=(x, y), PI DH publ :=(g x , g y ), PI DH sol :=g xy ,
SI —
 




respectively.


3 Parameters of DL-based Assumptions

In formulating intractability assumptions for problems related to DL we identi-
¬ed the following orthogonal parameters which su¬ce to describe assumptions
relevant to cryptographic applications.2
Note that the labels of the following sublists (e.g., “u” and “n” for the ¬rst
parameter) are used later in Section 4 to identify values corresponding to a given
parameter (e.g., “Computational capability of adversary” for above example).

1. Computational capability of adversary: Potential algorithms solving a
problem have to be computationally limited for number-theoretic assump-
tions to be meaningful (otherwise we could never assume their nonexistence).
Here, we only consider algorithms (called adversary in the following) with
running times bounded by a polynomial. The adversary can be of
u (Uniform complexity): There is a single probabilistic Turing machine (TM)
A which for any given problem instance from the proper domain returns
a (not necessarily correct) answer in expected polynomial time in the
security parameter k.
n (Non-uniform complexity): There is an (in¬nite) family of TMs {Ai } with
description size and running time of Ai bounded by a polynomial in the
security parameter k.
To make the de¬nition of the probability spaces more explicit we model
probabilistic TMs always as deterministic machines with the random coins
given as explicit input C chosen from the uniform distribution U.
Finally, a note on notation: In the case a machine A has access to some
oracles O1 , . . . , On we denote that as AO1 ,... ,On .
2. “Algebraic knowledge”: A second parameter describing the adversary™s
computational capabilities relates to the adversary™s knowledge on the group
family. It can be one of the following:
σ (Generic): This means that the adversary doesn™t know anything about
the structure (representation) of the underlying algebraic group. More
precisely this means that all group elements are represented using a
random bijective encoding function σ(·) : |G| ’ G and group operations
 




can only be performed via the addition and inversion oracles σ(x + y) ←
σ+ (σ(x), σ(y)) and σ(’x) ← σ’ (x) respectively, which the adversary
receives as a black box [15, 22, 23].
2
For this paper we slightly simpli¬ed the classi¬cation. Further parameters and values
and more details can be found in the full paper [21].
Assumptions Related to Discrete Logarithms 247

If we use σ in the following we always mean the (not further speci¬ed)
random encoding used for generic algorithms with a group G and gen-
erator g implicitly implied in the context. In particular, by Aσ we refer
to a generic algorithm.
(marked by absence of σ) (Speci¬c): In this case the adversary can also
exploit special properties (e.g., the encoding) of the underlying group.
3. Success probability: The adversary™s success probability in solving prob-
lem instances (for a given security parameter k and probability distribution
D) can either be
1 (Perfect): The algorithm A must solve all problem instances from D.
1’1/poly(k) (Strong): The algorithm A must be successful with over-
whelming probability, i.e., at most a negligible (in k) amount of instances
in D can remain unsolved.
(Invariant): The algorithm A must answer at least a constant fraction
of the queries from D successfully.
1/poly(k) (Weak): The algorithm A must be successful with at least a non-
negligible amount of queries from D.
An assumption requiring the inexistence of perfect adversaries corresponds
to worst-case complexity, i.e., if the assumption holds then there are at least
a few hard instances. However, what is a-priori required in most cases in
cryptography is an assumption requiring even the inexistence of weak adver-
saries, i.e., if the assumption holds then most instances are hard.
4. “Granularity of probability space”: Depending on what part of the
structure instance is a-priori ¬xed (i.e., the assumption has to hold for all
such parameters) or not (i.e., the parameters are part of the probability
space underlying an assumption) we distinguish among following situations:
l (Low-granular): The group family (e.g., prime order subgroups of —) is
 




p
¬xed but not the speci¬c structure instance (e.g., parameters p, q and
generators gi for the example group family given above).
m (Medium-granular): The group (e.g., p and q) but not the generators gi
are ¬xed.
h (High-granular): The group as well as the generators gi are ¬xed.
5. Problem family: Following problem families are useful (and often used)
for cryptographic applications. As mentioned in Section 2.2 we describe the
problem family (or more precisely their problem instances) by an (abstract)
structure instance SI (G, g1 , g2 , . . . ) and an (explicit) tuple (priv , publ , sol ):
DL (Discrete Logarithm): PI DL := (SI , ((x), (g x ), (x))).
DH (Di¬e-Hellman): PI DH := (SI , ((x, y), (g x , g y ), (g xy ))).
GDH (Generalized Di¬e-Hellman): PI GDH := (SI , ((xi |1 ¤ i ¤ n § n ≥ 2),
n
 

 




(g i∈I xi |∀ I ‚ {1, . . . , n}), (g i=1 xi ))).
2
SE (Square-Exponent): PI SE := (SI , ((x), (g x ), (g x ))).
’1
IE (Inverse-Exponent): PI IE := (SI , ((x), (g x ), (g x ))).
Note that priv (x) has to be an element of — here, contrary to the
 




|G|
other problem families mentioned where priv contains elements of |G|.
 




RP (Representation Problem): PI RP := (SI , ((xi | 1 ¤ i ¤ n § n ≥ 2),
( n gi i ), (xi | 1 ¤ i ¤ n))).
x
i=1
248 Ahmad-Reza Sadeghi and Michael Steiner

6. Problem type: Each problem can be formulated in three variants.
C (Computational): For a given problem instance PI the algorithm A suc-
ceeds if and only if it can solve PI , i.e., A(PI publ , . . . ) = PI sol .
D (Decisional): For a given problem instance PI , a random problem in-
stance PI R and a random bit b the algorithm A succeeds if and only
if it can decide whether a given solution matches the given problem
instance, i.e., A(PI publ , b — PI sol + ¯ — PI R sol ), . . . ) = b.
b
M (Matching): For two given problem instances PI 0 and PI 1 , and a ran-
dom bit b the algorithm A succeeds if and only if it can correctly
associate the solutions to their corresponding problem instances, i.e.,
A(PI 0 publ , PI 1 publ , PI b sol , PI ¯sol , . . . ) = b.
b
7. Group family: We distinguish between group families with the following
generic properties. The factorization of the group order contains
lprim large prime factors (at least one)
nsprim no small prime factor
prim only a single and large prime factor

4 De¬ning Assumptions
Using the parameters and corresponding values de¬ned in the previous section
we can de¬ne intractability assumptions in a compact and precise way. The used
notation is composed out of the labels corresponding to the parameter values of
a given assumption. This is best illustrated in following example:3 The term
1/poly(k)-DDHσ (c:u; g:h; f:prim)
denotes the decisional (D) Di¬e-Hellman (DH) assumption in prime-order groups
(f:prim) with weak success probability (1/poly(k)), limited to generic algorithms
(σ) of uniform complexity (c:u), and with high granularity (g:h).
The formal assumption statement automatically follows from the parameter
values implied by an assumption term. For space reasons we restrict ourselves
again to an example as explanation: To assume that above-mentioned assump-
tion 1/poly(k)-DDHσ (c:u; g:h; f:prim) holds informally means that there are no
generic algorithms of uniform complexity which are asymptotically able to dis-
tinguish a non-negligible amount of DH tuples from random ones in prime-order
subgroups where the probability space is de¬ned according to high granularity.
Formally this assumption is given below. To give the reader a better feel for
the newly introduced parameter granularity we specify also the corresponding
assumptions with medium and low granularity.
A few explanations to the statements: SG , Sg and SPI are the probabilis-
tic algorithms selecting groups, generators and problem instances, respectively;
ExpectRunTime gives a bound on the expected run time of the algorithm and
Prob[S :: PS] gives the probability of statement S with the probability taken
over a probability space de¬ned by PS. Furthermore, remember that PI DH is
(SI , ((x, y), (g x , g y ), (g xy ))), PI DH publ is (g x , g y ) and PI DH sol is (g xy ).
3
A more thorough treatment is omitted here due to space reasons and will appear
in [21].
Assumptions Related to Discrete Logarithms 249

1. Assumption 1/poly(k)-DDHσ (c:u; g:h; f:prim), i.e., with high granularity:
∀p1 , p2 > 0; ∀Aσ ∈ TM; ∃k0 ; ∀k > k0 ;
∀G ← SG (“prime-order groups”, 1k ); ∀g ← Sg (G); SI ← (G, g);
ExpectRunTime(Aσ (C, G, g, PI DH )) < k p2 ;
(| Prob[Aσ (C, G, g, PI DH publ , b — PI DH sol + ¯ — PI R sol ) = b ::
b
R R
b ← {0, 1}; C ← U;
PI DH ← SPI (DH, SI ); PI R ← SPI (PI DH P , PI DH SI );
]- 1/2 | · 2) < 1/k p1
2. As above except now with medium granularity
(1/poly(k)-DDHσ (c:u; g:m; f:prim)):
∀p1 , p2 > 0; ∀Aσ ∈ TM; ∃k0 ; ∀k > k0 ;
∀G ← SG (“prime-order groups”, 1k );
ExpectRunTime(Aσ (C, G, g, PI DH )) < k p2 ;
(| Prob[Aσ (C, G, g, PI DH publ , b — PI DH sol + ¯ — PI R sol ) = b ::
b
R R
b ← {0, 1}; C ← U;
g ← Sg (G); SI ← (G, g);
PI DH ← SPI (DH, SI ); PI R ← SPI (PI DH P , PI DH SI );
]- 1/2 | · 2) < 1/k p1
3. As above except now with low granularity
(1/poly(k)-DDHσ (c:u; g:l; f:prim)):
∀p1 , p2 > 0; ∀Aσ ∈ TM; ∃k0 ; ∀k > k0 ;
ExpectRunTime(Aσ (C, G, g, PI DH )) < k p2 ;
(| Prob[Aσ (C, G, g, PI DH publ , b — PI DH sol + ¯ — PI R sol ) = b ::
b
R R
b ← {0, 1}; C ← U;
G ← SG (“prime-order groups”, 1k ); g ← Sg (G); SI ← (G, g);
PI DH ← SPI (DH, SI ); PI R ← SPI (PI DH P , PI DH SI );
]- 1/2 | · 2) < 1/k p1

To express relations among assumptions we will use following notation:
A =’ B means that if assumption A holds, so does assumption B, i.e., A
(B) is a weaker (stronger) assumption than B (A). Vice-versa, it also means
that if there is a (polynomially-bounded) algorithm AB breaking assumption
B then we can build another (polynomially-bounded) algorithm AAB with
A
(oracle) access to AB which breaks assumption A.
A ⇐’ B means that A =’ B and B =’ A, i.e., A and B are assumptions
of the same (polynomial) complexity.
Furthermore, if we are referring to oracle-assumption, i.e., assumptions where
we give adversaries access to auxiliary oracles, we indicate it by listing the
oracles at the end of the list in the assumption term. For example, the as-
sumption 1/poly(k)-DDHσ (c:u; g:h; f:prim; O1-DSE(c:u; g:h; f:prim) ) corresponds to
the ¬rst assumption statement given above except that now the adversary also
gets access to an oracle breaking the assumption 1-DSE(c:u; g:h; f:prim). Finally,
if we use — for a particular parameter in an assumption term we mean the class
of assumptions where this parameter is varied over all possible values.
250 Ahmad-Reza Sadeghi and Michael Steiner

5 The Impact of Granularity
It would go beyond the scope (and space) of this paper to discuss all previously
identi¬ed parameters and we will focus only on granularity. Before stating the
actual results, let us ¬rst brie¬‚y repeat the practical relevance of granularity as
alluded in the introduction. Assumptions with lower granularity are weaker and
are so more desirable in principle. However, which of the granularity variants
is appropriate in cryptographic protocols depends on how and by whom the
parameters are chosen. A priori we have to use a high-granular assumption.
Yet in following situations we can resort to a weaker less granular assumption:
The security requirements of the cryptographic system guarantee that it™s in
the best (and only) interest of the chooser of the system parameters to choose
them properly; the system parameters are chosen by a mutually trusted third
party; or the system parameters are chosen in a veri¬able random process.4
Furthermore, care has to be taken for DL-related high and medium granular
assumptions in — and its subgroups. Unless we further constrain the set of valid
 




p
groups with (expensive) tests as outlined by [19], we require, for a given security
parameter, considerably larger groups than for the low granular counterpart of
the assumptions.


6 Computational DH, SE and IE
Maurer and Wolf [10] prove the equivalence between the computational SE and
DH assumption in their uniform and high-granular variant for both perfect and
invariant success probabilities.
We brie¬‚y review their results, extend their results to medium granularity
and prove similar relations between IE and DH.

6.1 CSE versus CDH
Theorem 1 ([10]).
-CSE(c:u; g:h; f:—) ⇐’ -CDH(c:u; g:h; f:—) 2

More concretely, they show the following: Let 0 < ±1 < 1, 0 < ±2 < 1 be
arbitrary constants and let G be a cyclic group with known order |G|. Then
(a) given an oracle OCDH which breaks -CDH(c:u; g:h; f:—) in G with success
probability at least = ±1 , there exists an algorithm AOCDH that breaks
-CSE(c:u; g:h; f:—) in G with success probability at least = ±1 .
(b) given an oracle OCSE which breaks -CSE(c:u; g:h; f:—) in G with success
probability at least = ±2 , there exists an algorithm AOCSE that breaks
-CDH(c:u; g:h; f:—) in G with success probability at least = ±2 3 .
From these reductions the theorem immediately follows.
4
This can be done either through a joint generation using random coins [24] or using
heuristics such as the one used for DSS key generation [20].
Assumptions Related to Discrete Logarithms 251

Remark 1. Maurer and Wolf showed the reduction for invariant success prob-
ability. However, the results easily extend also to all other variants related to
success probability, i.e., weak, strong and perfect. —¦
Above relation also holds for medium granularity as we show next.
Theorem 2.
1/poly(k)-CSE(c:u; g:m; f:—) ⇐’ 1/poly(k)-CDH(c:u; g:m; f:—). 2
Proof (sketch). The proof idea of Theorem 1 can also be applied in this case. The
only thing we have to show is that the necessary randomization in the reduction
steps can be extended to the medium granularity variants of CDH and CSE.
This can be done using standard techniques and is shown in the full version of
this paper [21]. The rest of the proof remains then the same as the proof of
Theorem 1.

Remark 2. Reduction proofs of a certain granularity can in general be easily
applied to the lower granularity variant of the involved assumptions. The nec-
essary condition is only that all involved randomizations extend to the wider
probability space associated with the lower granularity parameter.
Remark 3. In all the mentioned problem families the necessary random self-
reducibility exists for medium granularity and above remark always holds, i.e., we
can transform proofs from a high-granular variant to the corresponding medium-
granular variant. However, it does not seem to extend to low-granular variants.
This would require to randomize not only over the public part of the problem
instance PI and the generator g but also over the groups G with the same
associated security parameter k; this seems impossible to do in the general case
and is easily overlooked and can lead to wrong conclusions, e.g., the random
self-reducibility as stated in [3] doesn™t hold as the assumptions are (implicitly)
given in their low-granular form. —¦

6.2 CDH versus CIE
In the following we prove that similar relations as above also exist for CIE. In the
high-granular case following theorem holds. Here as well as in following results
related to IE we will restrict ourselves to groups of prime order. The results
also extend to more general groups but the general case is more involved5 and
omitted in this version of the paper for space reasons.

Theorem 3.
1/poly(k)-CDH(c:u; g:h; f:prim) ⇐’ 1/poly(k)-CIE(c:u; g:h; f:prim) 2

More concretely, we show the following: Let G be a cyclic group with known
prime order. Then
5
Due to the di¬erence in input domains between IE and other assumptions we have
to deal with the distribution of — over |G|. This results, e.g., in the success
   




|G|
probability being reduced by a factor of •(|G|)/|G|.
252 Ahmad-Reza Sadeghi and Michael Steiner

(a) given an oracle OCDH which breaks —-CDH(c:u; g:h; f:prim) in G with success
probability at least — = ±1 (k), there exists an algorithm AOCDH that solves
CIE(c:u; g:h; f:prim) in G with success probability at least ±1 (k)O(log |G|) .6
(b) given an oracle OCIE which breaks —-CIE(c:u; g:h; f:prim) in G with success
probability at least — = ±2 (k), there exists an algorithm AOCIE that solves
3
CSE(c:u; g:h; f:prim) in G with success probability at least ±2 (k) .
(c) following (b), there exists also an algorithm AOCIE that, with success prob-
9
ability at least ±2 (k) , breaks 1/poly(k)-CDH(c:u; g:h; f:prim) in G.
From these reductions and Remark 4 the theorem immediately follows. The
complete proof can be found in [21].
Remark 4. For strong and perfect success probabilities, i.e., ±1 (k) is either 1 or
1’1/poly(k), the resulting success probability in case (a) can always be polynomi-
ally bounded because O(log |G|) = O(poly(k)) and there always exist constants
c and c such that for large enough k it holds that (1 ’ 1/k c )O(poly(k)) ≥ 1/k c .
However, for the weak and invariant success probability, i.e., ±1 (k) is either
or 1/poly(k), the resulting error cannot be bounded polynomially. This implies
that above reduction in (a) does not work directly in the case where the oracle
OCDH is only of the weak or invariant success probability ¬‚avor! The success
probability of OCDH has ¬rst to be improved by self-correction [15] to strong
success probability, a task expensive both in terms of oracle calls and group
operations. —¦
Next, we prove above equivalence also for medium granularity. Similar to
Theorem 2 we could argue that due to the existence of a randomization the result
immediately follows also for the medium granularity case. However, we will show
below that the reduction can be performed much more e¬ciently in the medium
granular case than in the case above; thereby we improve the concrete security
considerably.
Theorem 4.
1/poly(k)-CSE(c:u; g:m; f:prim) ⇐’ 1/poly(k)-CIE(c:u; g:m; f:prim). 2
OCIE
Proof. “’”: We construct A as follows: Assume we are given a CSE in-
stance g with respect to generator g. We set h := g x and t := x’1 , pass g x (= h)
x

and g(= ht ) to OCIE . Assuming the oracle answered correctly we get the desired
’1 ’1 ’1 2
solution to the CSE problem: ht = (g x )(x ) = g x .
’1 2 ’2 ’2
“⇐”: Conversely we can exploit the identity ((g x )(x ) = (g x )x = g xx =
’1
g x to construct AOCSE solving CIE with a single call to OCSE .

Remark 5. For each direction we need now only a single oracle call. If we take
also into account that with a single oracle call 1/poly(k)-CSE(c:u; g:m; f:prim)
can be reduced to 1/poly(k)-CDH(c:u; g:m; f:prim) we achieve a reduction from
1/poly(k)-CIE(c:u; g:m; f:prim) to 1/poly(k)-CDH(c:u; g:m; f:prim) while retain-
ing the success probability of the oracle.
6
The exponent O(log |G|) stems from a square and multiply used in the reduction.
Assumptions Related to Discrete Logarithms 253

Remark 6. Above observation also implies that, contrary to the high-granular
(Remark 4) case, this reduction directly applies to the invariant and weak success
probability variant of the assumptions, i.e., no self-correction is required. —¦
In particular the Remark 5 is of high signi¬cance. The reduction we get in the
medium-granular case is much more e¬cient than the corresponding reduction in
the high-granular case: With a single instead of log (|G|) (very expensive) oracle
calls and O(log (|G|)) instead of O(log (|G|)2 ) group operations we achieve a
success probability which is higher by a power of O(log (|G|))!


7 Decisional DH, SE and IE
7.1 Di¬culty in the Generic Model
We state ¬rst a Lemma which plays an important role for later proofs in the
context of generic algorithms:
Lemma 1 ([25, 15]). Let P (X1 , X2 , · · · , Xn ) be a non-zero polynomial in pe [X]
 




of total degree d ≥ 0 (p ∈ ; e ∈ ). Then the probability that P (x1 , x2 , · · · , xn ) ≡
 




¡




0 is at most d/p for a random tuple (x1 , x2 , · · · , xn ) ∈R ne .
 




2
p

Using Lemma 1, Wolf [9] shows that there exists no generic algorithm that
can solve DSE (and consequently also DDH) in polynomial time if the order
of the multiplicative group is not divisible by small primes, as summarized in
following theorem:
Theorem 5 ([9]).
true =’ 1/poly(k)-DSEσ (c:u; g:h; f:nsprim) 2

Remark 7. More precisely, Wolf shows that the probability that any Aσ can cor-
rectly distinguish correct DSE inputs from incorrect ones is at most (T +4)(T +3)
2p
where p is the smallest prime factor of |G| and T is an upper bound on the
algorithm™s runtime.
Remark 8. It might look surprising that 1/poly(k)-DSEσ (c:u; g:h; f:nsprim) al-
ways holds, i.e., it™s a fact, not an assumption. Of course, the crucial aspect is
the rather restricted adversary model (the σ in the assumption statement) which
limits adversaries to generic algorithms. However, note that this fact means that
to break DSE one has to exploit deeper knowledge on the actual structure of the
used algebraic groups. In particular, for appropriately chosen prime-order sub-
groups of — and elliptic or hyper-elliptic curves no such exploitable knowledge
 




p
could yet be found and all of currently known e¬cient and relevant algorithms in
these groups are generic algorithms, e.g., Pohlig-Hellman [26] or Pollard-ρ [27].
Nevertheless, care has to be applied when proving systems secure in the generic
model [28]. —¦

In the following theorem we show that also DIE cannot be solved by generic
algorithms if the order of the multiplicative group is not divisible by small primes.
254 Ahmad-Reza Sadeghi and Michael Steiner

Theorem 6.
true =’ 1/poly(k)-DIEσ (c:u; g:h; f:nsprim) 2

The proof is similar to the proof of Theorem 5 and can be found in [21].


7.2 DSE versus DDH

Wolf [9] shows following two results on the relation of DSE and DDH: DSE can
easily be reduced to DDH but the converse doesn™t hold; in fact, Theorem 8
shows that a DSE oracle, even when perfect, is of no help in breaking DDH
assumptions.

Theorem 7 ([9]).
1/poly(k)-DSE(c:u; g:h; f:—) =’ 1/poly(k)-DDH(c:u; g:h; f:—) 2

Remark 9. Following Remark 2, this result easily extends also to the medium-
granular variant. —¦

Theorem 8 ([9]).
true =’ 1/poly(k)-DDHσ (c:u; g:h; f:nsprim; O1-DSE(c:u; g:h; f:nsprim) ) 2

Remark 10. More precisely, Wolf shows that the probability that any Aσ,ODSE
can correctly distinguish correct DDH inputs from incorrect ones is at most
(T +5)(T +4)
where p is the smallest prime factor of |G| and T is an upper bound
2p
on the algorithm™s runtime. —¦


7.3 DIE versus DDH

In the following we prove that similar relations also hold among DDH and DIE:
We show a reduction from DIE to DDH and prove that a DIE oracle, even when
perfect, is of no help in breaking DDH assumptions.

Theorem 9.
1/poly(k)-DIE(c:u; g:h; f:prim) =’ 1/poly(k)-DDH(c:u; g:h; f:prim) 2

Theorem 10.
true =’ 1/poly(k)-DDHσ (c:u; g:h; f:nsprim; O1-DIE(c:u; g:h; f:nsprim) ) 2

Both proofs follow similar strategies than the proofs of Theorem 7 and 8 and
can be found in [21]. One twist is that the input domains between IE and DH
are di¬erent and the DIE-oracle cannot answer correctly to the queries not from
its domain. However, since this limits the use of a DIE-oracle in solving DDH
even further, this does not a¬ect the desired result.
Assumptions Related to Discrete Logarithms 255

7.4 DSE versus DIE
In the next theorem we prove that an oracle breaking 1-DSE(c:u; g:h; f:—) is of
no help in breaking 1/poly(k)-DIEσ (c:u; g:h; f:—).
Theorem 11.
true =’ 1/poly(k)-DIEσ (c:u; g:h; f:nsprim; O1-DSE(c:u; g:h; f:nsprim) ) 2
Proof. Similar to the proofs of Theorem 6 and 10 we de¬ne a Lemma which
associates the minimal generic complexity of solving DIE directly to the smallest
prime factor of the order of the underlying group G. Theorem 11 immediately
follows from Lemma 2 and Remark 11.

Remark 11. In the classical formulation of decision problems the adversary gets,
depending on the challenge b, either the correct element or a random element
’1
as input, i.e., in the case of DIE the adversary gets g x together with g x if
b = 0 and g c if b = 1. The formulation used in the Lemma considers a slightly
di¬erent variant of the decisional problem type: We consider here an adversary
which receives, in random order, both the correct and a random element and
the adversary has to decide on the order of the elements, i.e., the adversary gets
’1 ’1
g x and (g x , g c ) for b = 0 and (g c , g x ) for b = 1.
This formulation makes the proofs easier to understand. However, note that
both variants can be shown equivalent. —¦
Lemma 2. Let G be a cyclic group and g a corresponding generator, let p be the
smallest prime factor of n = |G|. Let ODSE be a given oracle solving DSE tuples
in G and let Aσ,ODSE be any generic algorithm for groups G with maximum run
time T and oracle access to ODSE . Further let x0 , x1 be random elements of
— R
|G|, b ∈R {0, 1} a randomly and uniformly chosen bit and C ← U. Then it
 




always holds that
(T + 4)(T + 3)
’1 ’1
Prob[Aσ (C, (G, g), g x0 , g xb , g x¯ ) = b] ¤
b
2p 2
Proof. For given σ(1), σ(x), {σ(x’1 ), σ(c)}, assume that the algorithm Aσ,ODSE
computes at most T1 + 4 (images of) distinct linear combinations Pi of the
elements 1, x, x’1 , c with Pi (1, x, x’1 , c) = ai1 + ai2 x + ai3 x’1 + ai4 c such that
σ(Pi (1, x, x’1 , c)) = σ(ai1 + ai2 x + ai3 x’1 + ai4 c),
where aij are constant coe¬cients. Furthermore, it is not a-priori known to
Aσ,ODSE which of the (known) values in {ai3 , ai4 } is the coe¬cient for x’1 and
which one corresponds to c. Assume that Aσ,ODSE makes T2 calls to ODSE .
Aσ,ODSE may be able to distinguish the coe¬cient by obtaining information
from either of the following events:
Ea : Aσ,ODSE ¬nds a collision between two distinct linear equations (Pi , Pj ) with
i = j, i.e.,
σ(Pi (1, x, x’1 , c)) = σ(Pj (1, x, x’1 , c)) ’ Pi (1, x, x’1 , c) = Pj (1, x, x’1 , c)
256 Ahmad-Reza Sadeghi and Michael Steiner

Eb : Aσ,ODSE gets at least one positive answer from ODSE for a non-trivial query
with i = j, i.e.,

σ(Pi (1, x, x’1 , c)) = σ((Pj (1, x, x’1 , c)2 ).

Let E be the union of the events Ea and Eb . Now we compute an upper bound
for the probability that either of these events occurs.

= (T1 +4)(T1 +3)
+4
Case Ea : Consider Pi and Pj as polynomials. There are T12 2
possible distinct pairs. The probability of a collision for two linear combinations
Pi , Pj is the probability of (randomly) ¬nding the root of polynomial x(Pi ’
Pj ) ≡ 0 mod pe for any prime factor p of |G| with pe ||G|. Due to Lemma 1 this
probability is at most 2/pe (¤ 2/p ), because the degree of x(Pi ’ Pj ) is at most
two.7 It follows that Prob[Ea ] ¤ (T1 +4)(T1 +3) p = (T1 +4)(T1 +3) .
2
2 p
Case Eb : For i = j it is not possible to derive a relation Pi = Pj 2 except that
Pi and Pj are both constant polynomials (= 0), meaning that the polynomial
x2 (Pi ’ Pj 2 ) ≡ 0 mod pe for x = 0. The total degree of the polynomial x2 (Pi ’
Pj 2 ) is at most 4 and the probability for Eb is at most p T2 .
4


In total we have
(T1 + 4)(T1 + 3) 4 (T + 4)(T + 3)
Prob[E] ¤ Prob[Ea ] + Prob[Eb ] = + T2 ¤ ,
p p p

with T1 + T2 ¤ T . The success probability of Aσ,ODSE therefore is:
1 ¯
Prob[Aσ,ODSE (..) = b] = Prob[E] + Prob[E] =
2
1 ’ Prob[E] 1 Prob[E] 1 (T + 4)(T + 3)
Prob[E] + =+ ¤+ .
2 2 2 2 2p


In sharp contrast to the above mentioned high granular case, we prove in
the following theorem that these assumptions are equivalent for their medium
granular version (other parameters remain unchanged).

Theorem 12.
1/poly(k)-DSE(c:u; g:m; f:prim) ⇐’ 1/poly(k)-DIE(c:u; g:m; f:prim). 2
Proof. “⇐”: Assume we are given a DIE tuple IDIE = (g, g x , g z ) where g z is
’1
either g x or a random element of group G. Set h:=g z then g = ht and g x = htx
for some (unknown) t ∈ — . After reordering the components we obtain the
 




|G|
t xt
tuple (h, h , h ).
Note that Pi , Pj are also functions of x’1 , x = 0 and thus one can virtually think of
7

the polynomial x(Pi ’ Pj ) by multiplying both sides of the equation Pi = Pj with
x. Furthermore, uniformly distributed random values modn are also randomly and
uniformly distributed modpe .
Assumptions Related to Discrete Logarithms 257

2
If z = x’1 then t = x and the tuple (h, ht , hxt ) will have the form (h, ht , ht )
which represents a DSE tuple and can be solved by the given DSE oracle. The
probability distribution is correct, since h is a group generator and ht is a random
element of G.
If z = x’1 then t = x and hxt is a random group element (x is a random element
of — ) and the elements h, ht , htx are independent.
 




|G|
2
“’”: Assume, we are given a DSE tuple (g, g x , g z ) where g z is either g x or a
random group element. Set h:=g x then g = ht and g z = htz for some (unknown)
t ∈ — . After reordering the components we obtain the tuple (h, ht , htz ).
 




|G|
If z = x2 then we have8 x = t’1 and z = t’2 meaning that the tuple (h, ht , hxt )
’1
has the form (h, ht , ht ) representing a DIE tuple. Its probability distribution
is correct because h is a group generator, ht is a random element of G and the
’1
last element ht has the correct form.
If z = x2 then hzt is a random group element, since t is a random element of
— t tz
|G|, and further the elements h, h and h are independent.
 




8 Conclusions

In this paper, we identify the parameters relevant to cryptographic assumptions.
Based on this we present a framework and notation for de¬ning assumptions re-
lated to Discrete Logarithms. Using this framework these assumptions can be
precisely and systematically classi¬ed. Wider adoption of such a terminology
would ease the study and comparison of results in the literature, e.g., the danger
of ambiguity and mistakes in lengthly stated textual assumptions and theorems
would be minimized. Furthermore, clearly stating and considering these param-
eters opens an avenue to generalize results regarding the relation of di¬erent
assumptions and to get a better understanding of them. This is the focus of
our ongoing research and is covered to a larger extent in the full version of the
paper [21].
A parameter in de¬ning assumptions previously ignored in the literature is
granularity. We show (as summarized in Figure 1) that varying this parameter
leads to surprising results: we prove that some DL-related assumptions are equiv-
alent in one case (medium granular) and provably not equivalent, at least not
in a generic sense, in another case (high granular). Furthermore, we also show
that some reductions for medium granularity are much more e¬cient than their
high-granular version leading to considerably improved concrete security, in par-
ticular as medium granularity results in weaker assumptions than high-granular
ones. However, we note that medium- or low-granular assumption apply in cryp-
tographic settings only when the choice of system parameters is guaranteed to
be truly random.
In this paper we only scratched the topic of granularity and interesting open
questions remain to be answered: While for both CDL and CDH it can be shown
2 2
This is because hx = g x = htz which implies hx = htx , x = tx2 and t = x’1 .
8
258 Ahmad-Reza Sadeghi and Michael Steiner

g:h g:m g:l
1/poly(k)-CSE
1/poly(k)-CSE 1/poly(k)-CSE




1/poly(k)- 1/poly(k)- 1/poly(k)- 1/poly(k)-
1/poly(k)- 1/poly(k)-
CDH CIE CDH CIE
CDH CIE

1/poly(k)-DSE 1/poly(k)-DSE
1/poly(k)-DSE

σ
σ
σ
1/poly(k)- 1/poly(k)- 1/poly(k)- 1/poly(k)- 1/poly(k)- 1/poly(k)-
DDH DIE DDH DIE DDH DIE


Efficient reduction
Inefficient reduction
σ
Reduction impossible in generic model


Fig. 1. Summary of our results


that their high- and medium-granular assumptions are equivalent, this is not yet
known for DDH (also brie¬‚y mentioned as an open problem in [29]). Only few re-
lations can be shown for low-granular assumption as no random self-reducibility
is yet known. However, achieving such “full” random self-reducibility seems very
di¬cult in general (if not impossible) in number-theoretic settings [30] contrary
to, e.g., lattice settings used in [31].

Acknowledgements
We thank Birgit P¬tzmann, Matthias Schunter, and the anonymous reviewers
for their helpful comments.

References
[1] Kevin S. McCurley. The discrete logarithm problem. In Carl Pomerance, ed-
itor, Cryptology and Computational Number Theory, volume 42 of Proceedings
of Symposia in Applied Mathematics, pages 49“74, Providence, 1990. American
Mathematical Society. 243
[2] Whit¬eld Di¬e and Martin Hellman. New directions in cryptography. IEEE
Transactions on Information Theory, IT-22(6):644“654, November 1976. 243
[3] Dan Boneh. The Decision Di¬e-Hellman problem. In Third Algorithmic Number
Theory Symposium, number 1423 in Lecture Notes in Computer Science, pages
48“63. Springer-Verlag, Berlin Germany, 1998. 243, 244, 251
[4] Ronald Cramer and Victor Shoup. A practical public key cryptosystem prov-
ably secure against adaptive chosen ciphertext attack. In Hugo Krawczyk, editor,
Advances in Cryptology “ CRYPTO ™98, number 1462 in Lecture Notes in Com-
puter Science, pages 13“25. International Association for Cryptologic Research,
Springer-Verlag, Berlin Germany, 1998. 243
Assumptions Related to Discrete Logarithms 259

[5] Moni Naor and Omer Reingold. Number-theoretic constructions of e¬cient
pseudo-random functions. In 38th Symposium on Foundations of Computer Sci-
ence (FOCS), pages 458“467. IEEE Computer Society Press, 1997. 243
[6] Michael Steiner, Gene Tsudik, and Michael Waidner. Key agreement in dynamic
peer groups. IEEE Transactions on Parallel and Distributed Systems, 11(8):769“
780, August 2000. 243
[7] Yair Frankel, Yiannis Tsiounis, and Moti Yung. “Indirect discourse proofs”:
Achieving fair o¬-line cash (FOLC). In K. Kim and T. Matsumoto, editors,
Advances in Cryptology “ ASIACRYPT ™96, number 1163 in Lecture Notes in
Computer Science, pages 286“300. Springer-Verlag, Berlin Germany, 1996. 243
[8] Helena Handschuh, Yiannis Tsiounis, and Moti Yung. Decision oracles are equiv-
alent to matching oracles. In International Workshop on Practice and Theory in
Public Key Cryptography ™99 (PKC ™99), number 1560 in Lecture Notes in Com-
puter Science, Kamakura, Japan, March 1999. Springer-Verlag, Berlin Germany.
243
[9] Stefan Wolf. Information-theoretically and Computionally Secure Key Agreement
in Cryptography. PhD thesis, ETH Z¨rich, 1999. 243, 244, 253, 254
u
[10] Ueli M. Maurer and Stefan Wolf. Di¬e-Hellman oracles. In Koblitz [32], pages
268“282. 243, 250
[11] Mike Burmester, Yvo Desmedt, and Jennifer Seberry. Equitable key escrow with
limited time span (or, how to enforce time expiration cryptographically). In
K. Ohta and D. Pei, editors, Advances in Cryptology “ ASIACRYPT ™98, num-
ber 1514 in Lecture Notes in Computer Science, pages 380“391. Springer-Verlag,
Berlin Germany, 1998. 243
[12] Birgit P¬tzmann and Ahmad-Reza Sadeghi. Anonymous ¬ngerprinting with di-
rect non-repudiation. In Okamoto [33], pages 401“414. 243
[13] Jan Camenisch, Ueli Maurer, and Markus Stadler. Digital payment systems with
passive anonymity-revoking trustees. In E. Bertino, H. Kurth, G. Martella, and
E. Montolivo, editors, Proceedings of the Fourth European Symposium on Research
in Computer Security (ESORICS), number 1146 in Lecture Notes in Computer
Science, pages 33“43, Rome, Italy, September 1996. Springer-Verlag, Berlin Ger-
many. 244
[14] George Davida, Yair Frankel, Yiannis Tsiounis, and Moti Yung. Anonymity con-
trol in e-cash systems. In Proceedings of the First Conference on Financial Cryp-
tography (FC ™97), number 1318 in Lecture Notes in Computer Science, pages
1“16, Anguilla, British West Indies, February 1997. International Financial Cryp-
tography Association (IFCA), Springer-Verlag, Berlin Germany. 244
[15] Victor Shoup. Lower bounds for discrete logarithms and related problems. In
Walter Fumy, editor, Advances in Cryptology “ EUROCRYPT ™97, number 1233
in Lecture Notes in Computer Science, pages 256“266. International Association
for Cryptologic Research, Springer-Verlag, Berlin Germany, 1997. 244, 246, 252,
253
[16] Ueli M. Maurer and Stefan Wolf. Di¬e-Hellman, Decision Di¬e-Hellman, and
discrete logarithms. In IEEE Symposium on Information Theory, page 327, Cam-
bridge, USA, August 1998. 244
[17] Ueli M. Maurer and Stefan Wolf. Lower bounds on generic algorithms in groups. In
Kaisa Nyberg, editor, Advances in Cryptology “ EUROCRYPT ™98, number 1403
in Lecture Notes in Computer Science, pages 72“84. International Association for
Cryptologic Research, Springer-Verlag, Berlin Germany, 1998. 244
260 Ahmad-Reza Sadeghi and Michael Steiner

[18] Eli Biham, Dan Boneh, and Omer Reingold. Breaking generalized Di¬e-Hellman
modulo a composite is no easier than factoring. Information Processing Letters,
70:83“87, 1999. Also appeares in Theory of Cryptography Library, Record 97-14,
1997. 244
[19] Daniel M. Gordon. Designing and detecting trapdoors for discrete log cryptosys-
tems. In E.F. Brickell, editor, Advances in Cryptology “ CRYPTO ™92, volume
740 of Lecture Notes in Computer Science, pages 66“75. International Association
for Cryptologic Research, Springer-Verlag, Berlin Germany, 1993. 244, 250
[20] National Institute of Standards and Technology (NIST). The Digital Signature
Standard (DSS). FIPS PUB 186-2, January 2000. 245, 250
[21] Ahmad-Reza Sadeghi and Michael Steiner. Assumptions related to discrete log-
arithms: Why subtleties make a real di¬erence. Full version of paper, available
from http://www.semper.org/sirene/lit/abstrA1.html . 246, 248, 251, 252,
254, 257
[22] Dan Boneh and Richard J. Lipton. Algorithms for black box ¬elds and their
application to cryptography. In Koblitz [32], pages 283“297. 246
[23] V. I. Nechaev. Complexity of a determinate algorithm for the discrete logarithm.
Mathematical Notes, 55(2):165“172, 1994. Translated from Matematicheskie Za-
metki, 55(2):91“101, 1994. 246
[24] Christian Cachin, Klaus Kursawe, and Victor Shoup. Random oracles in Con-
stantinople: Practical asynchronous Byzantine agreement using cryptography. In
Proceedings of the 19th Annual ACM Symposium on Principles of Distributed
Computing, Portland, Oregon, July 2000. ACM. Full version appeared as Cryp-
tology ePrint Archive Report 2000/034 (2000/7/7). 250
[25] J. T. Schwartz. Fast probabilistic algorithms for veri¬cation of polynomial iden-
tities. Journal of the ACM, 27(4):701“717, October 1980. 253
[26] S.C. Pohlig and M. E. Hellman. An improved algorithm for computing logarithms
over GF(p) and its cryptographic signi¬cance. IEEE Transactions on Information
Theory, 24:106“110, 1978. 253
[27] J. M. Pollard. Monte carlo methods for index computation mod p. Mathematics
of Computation, 32:918“924, 1978. 253
[28] Marc Fischlin. A note on security proofs in the generic model. In Okamoto [33],
pages 458“469. 253
[29] Victor Shoup. On formal models for secure key exchange. Research Report RZ
3120 (#93166), IBM Research, April 1999. A revised version 4, dated November
15, 1999, is available from http://www.shoup.net/papers/ . 258
[30] Dan Boneh. Personal Communication, October 2000. 258
[31] Mikl´s Ajtai and Cynthia Dwork. A public-key cryptosystem with worst-
o
case/average-case equivalence. In 29th Annual Symposium on Theory Of Com-
puting (STOC), pages 284“293, El Paso, TX, USA, May 1997. ACM Press. 258
[32] Neal Koblitz, editor. Advances in Cryptology “ CRYPTO ™96, number 1109 in
Lecture Notes in Computer Science. International Association for Cryptologic
Research, Springer-Verlag, Berlin Germany, 1996. 259, 260
[33] T. Okamoto, editor. Advances in Cryptology “ ASIACRYPT ™2000, number 1976
in Lecture Notes in Computer Science, Kyoto, Japan, 2000. International Associ-
ation for Cryptologic Research, Springer-Verlag, Berlin Germany. 259, 260