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