# Discrete Logarithms

### From Wiki

#### Discrete logarithms general

The following notation applies to all problems on this page.
Let *g* be a known element of prime order *r* in a group
(with group operation written multiplicatively). Let be the group generated by *g*.

Popular choices for group are subgroups of: Multiplicative group of a finite field, algebraic torus over a finite field, elliptic curve over a finite field, divisor class group of a curve over a finite field.

##### DLP: discrete logarithm problem

Definition: Let notation be as above. Given to compute *x* such that
*h* = *g*^{x}.

Reductions: CDH ≤_{P} DLP,
DLP ≤_{P} CDH
when auxiliary information is given (Maurer reduction),
FACTORING ≤_{P} DLP
in .

Algorithms: The best known algorithm for DLP in general is the parallel Pollard rho method, which has complexity group operations. For particular groups, such as finite fields, tori, divisor class groups of curves of genus there are index calculus algorithms.

Use in cryptography: Schnorr signatures, DSA signatures.

History: DLP is a classical problem in number theory.

Remark: A variant of DLP is: Given to compute *x*.
This is ≡_{P} DLP.

References:

- D. Knuth, The Art of computer programming, Vol. 2, 3rd ed., 1997.

##### CDH: computational Diffie-Hellman problem

Definition: Given to compute *g*^{ab}.

Reductions:

Algorithms: The best known algorithm for CDH is to actually solve the DLP.

Use in cryptography: Diffie-Hellman key exchange and variants, Elgamal encryption and variants, BLS signatures and variants.

History: Discovered by W. Diffie and M. Hellman.

Remark: A variant of CDH is: Given to compute .
This is ≡_{P} CDH.

References:

- W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Transactions on Information Theory, vol. IT-22, No. 6, Nov. 1976, p. 644-654.
- U.M. Maurer and S. Wolf, Diffie-Hellman Oracles, Proceedings of CRYPTO '96, p. 268-282.
- D. Boneh and R.J. Lipton Algorithms for Black-Box Fields and Applications to Cryptography, Proceedings of CRYPTO '96, p. 283-297.

##### SDH: static Diffie-Hellman problem

Definition: Fix . Given to compute *h*^{a}.

Algorithms: The best known algorithm for SDH is to actually solve the DLP.

Use in cryptography:

History: Discussed by Brown-Gallant and Cheon.

References:

- D. R. L. Brown and R. P. Gallant, The Static Diffie–Hellman Problem, IACR ePrint 2004/306.

##### gap-CDH: Gap Diffie-Hellman problem

Definition: Given to compute *g*^{ab} where the algorithm
has access to an oracle which solves the DDH problem.

Reductions: gap-CDH ≤_{P} CDH.

Algorithms: The best known algorithm for gap-CDH is to actually solve the CDH.

Use in cryptography: ECIES proof in the Random Oracle Model, Chaum undeniable signature.

History: Introduced by Okamoto and Pointcheval in their analysis of undeniable signatures. A closely related problem is strong-Diffie-Hellman (proposed by Abdulla, Bellare and Rogaway at CT-RSA 2001) which is to solve CDH given a restricted DDH oracle.

References:

- T. Okamoto and D. Pointcheval, The Gap-Problems: A New Class of Problems for the Security of Cryptographic Schemes. Public Key Cryptography 2001, Springer LNCS 1992, 104-118.

##### DDH: decision Diffie-Hellman problem

Definition: Given to determine whether or not *h* = *g*^{ab}.

Algorithms: The best known algorithm for DDH in general is to solve DLP. Note that DDH can be easy for some pairing groups.

Use in cryptography: Diffie-Hellman key exchange and variants, Elgamal encryption and variants.

History:

Remark: A variant of DDH is: Given to determine
whether or not .
This variant is not known to be ≡_{P} DDH.

References:

- D. Boneh, The decision-Diffie-Hellman problem, ANTS-III, Springer LNCS 1423 (1998) 48--63.

##### Strong-DDH: strong decision Diffie-Hellman problem

Definition: Given to determine whether or not *h* = *g*^{ab}.

Reductions:

Algorithms:

Use in cryptography:

History:

Remark: References:

- B. Pfitzmann and A. Sadeghi, Anonymous Fingerprinting with Direct Non-repudiation, Advances in Cryptology - AsiaCrypt 2000.

##### sDDH: skewed decision Diffie-Hellman problem

Definition: Let *f* be any uninvertible function with domain *Z*_{r}.
Given *f*(*a*) and to determine whether or not *h* = *g*^{ab}.

Reductions:

Algorithms:

History:

References:

- Ran Canetti: Towards Realizing Random Oracles: Hash Functions That Hide All Partial Information. Proceedings of Crypto'97, pages 455-469.

##### PDDH: parallel decision Diffie-Hellman problem

Definition: Given to determine whether or not .

Algorithms: Same as for DDH.

Use in cryptography:

History:

References:

- M. Abdalla, E. Bresson, O. Chevassut, D. Pointcheval, 'Password-Based Group Key Exchange in a Constant Number of Rounds,' PKC 2006, Springer LNCS (2006) 427--442

##### Square-DH: Square Diffie-Hellman problem

Definition: Given to compute .

Reductions: Square-DH ≡_{P} CDH.

Algorithms: The best known algorithm for Square-DH is to actually solve the DLP.

Use in cryptography:

History:

References:

##### l-DHI: *l*-Diffie-Hellman inversion problem

Definition: Given to compute *g*^{1 / a}.

Algorithms: The best known algorithm for l-DHI is to actually solve the DHP.

Use in cryptography:

History:

References:

##### l-DDHI: *l*-Decisional Diffie-Hellman inversion problem

Definition: Given to determine whether
*v* = *g*^{1 / a}.

Reductions: l-DDHI ≤_{P} l-DHI.

Algorithms: The best known algorithm for l-DDHI is to actually solve the l-DHI.

Use in cryptography:

History:

References:

##### REPRESENTATION: Representation problem

Definition: Given to compute such that .

Reductions: REPRESENTATION ≡_{P} DLP.

Algorithms: The best known algorithm for REPRESENTATION is to solve the DLP.

Use in cryptography:

History: Proposed by S. Brands.

References:

- S. Brands, An efficient off-line electronic cash system based on the representation problem, CWI Technical Report CS--R9323, 1993.

##### LRSW: LRSW Problem

Definition: Given *g*,*g*^{x},*g*^{y} and an oracle O which on input *s* chooses a random *a* = *g*^{z} and answers (*a*,*a*^{sy},*a*^{x + sxy}), to compute (*t*,*b*,*b*^{ty},*b*^{x + txy}) where and *t* is not one of the *s* on which O was queried.

Algorithms: The best known algorithm for LRSW is to solve the DLP.

Use in cryptography: Anonymous credentials.

References:

- A. Lysyanskaya, R.L. Rivest, A. Sahai and S. Wolf, Pseudonym Systems, SAC 1999, Springer LNCS 1758, 184-199.
- A. Lysyanskaya and J. Camenisch, Signature schemes and anonymous credentials from bilinear maps, CRYPTO 2004, Springer LNCS 3152, 56-72.

##### Linear: Linear problem

Definition: Given to compute *g*^{c + d}.

Algorithms: The best known algorithm for Linear is to solve the DLP.

Use in cryptography:

History: Never actually used in cryptography yet it seems.

References:

##### D-Linear1: Decision Linear problem (version 1)

Definition: Given to decide if *v* = *g*^{c + d}.

Reductions: D-Linear1 ≤_{P} Linear.

Algorithms: The best known algorithm for D-Linear1 is to solve the DLP.

Use in cryptography:

History: This problem was generalised to D-Linear2

References:

- D. Boneh, X. Boyen and H. Shacham, Short Group Signatures, CRYPTO 2004, Springer LNCS 3152, 41-55.

##### l-SDH: *l*-Strong Diffie-Hellman problem

Definition: Given to find and
*g*^{1 / (a + w)}

Algorithms: The best known algorithm for the l-SDH is to solve the DLP.

Use in cryptography: Boneh-Boyen short signatures

History:

References:

- Dan Boneh, Xavier Boyen: Short Signatures Without Random Oracles and the SDH Assumption in Bilinear Groups. J. Cryptology 21(2): 149-177 (2008)

##### c-DLSE: Discrete Logarithm with Short Exponents

Definition: Let such that *p* − 1 = 2*q* for *p*,*q* primes and let *c* be an integer. Given for to find *x*.

Algorithms: The best known algorithm for the c-DLSE is to use the baby-step-giant-step or Pollard kangaroo algorithms for solving the DLP in a short interval.

Use in cryptography: Gennaro pseudorandom generator

History:

References:

- S. Patel and G. Sundaram, An Efficient Discrete Log Pseuo Random Generator, CRYPTO '98, Springer LNCS 1462, 304-317.
- R. Gennaro, An Improved Pseudo-random Generator Based on Discrete Log, CRYPTO 2000, Springer LNCS 1880, 469-481.

##### CONF: (conference-key sharing scheme)

Definition: Given to compute *g*^{b}.

Algorithms:

Use in cryptography: Okamoto's conference-key sharing scheme

History:

References:

- K. Sakurai and H. Shizuya, Relationships among the Computational Powers of Breaking Discrete Log Cryptosystems, EUROCRYPT 1995, Springer LNCS 921, 341-355
- T. Okamoto, Encryption and authentication schemes based on public-key systems, Ph.D. Thesis, The university of Tokyo, 1988

##### 3PASS: 3-Pass Message Transmission Scheme

Definition: Given to compute *s* such that *A* = *s*^{a},*B* = *s*^{b},*C* = *s*^{ab} if such an *s* exists.

Algorithms:

Use in cryptography: Shamir's 3-pass message transmission scheme.

History:

References:

- K. Sakurai and H. Shizuya, Relationschips among the Computational Powers of Breaking Discrete Log Cryptosystems, EUROCRYPT 1995, Springer LNCS 921, 341-355
- A. Shamir, R.L. Rivest and L. Adleman, Mental poker, MIT/LCS, TM-125, Feb 1979

##### LUCAS: Lucas Problem

Definition: Given to compute *x* such that *V*_{x}(*m*) = *z* where *V*_{t}(*m*) is defined as *V*_{0}(*m*) = 2,*V*_{1}(*m*) = *m*,*V*_{t}(*m*) = *m**V*_{t − 1}(*m*) − *V*_{t − 2}(*m*)

Algorithms:

Use in cryptography:

History:

References:

- C. Laih, F. Tu and W. Tai, On the security of the Lucas function, Information Processing Letters, Vol 53, No 5, 243-247, March 1995
- P. Smith and C. Skinner, A public-key cryptosystem and a digital signature system based on the Lucas function analogue to discrete logarithms, ASIACRYPT 1994, Springer LNCS 917, 357-364

##### XLP: x-Logarithm Problem

Definition: For any point *P* = (*x*,*y*) in an Elliptic curve
, we write
where is obtaining by taking the
bit representation of the x-coordinate of , and considering this as the bit representation of an integer.

The x-Logarithm Problem is to distinguish between *g*^{d} and *g*^{x} where *x* = *x*(*g*^{a}) and *g*^{a} is an arbitrary element in the group.

Algorithms:

Use in cryptography:

History:

References:

- Daniel R.L. Brown and Kristian Gjøsteen, A Security Analysis of the NIST SP 800-90 Elliptic Curve Random Number Generator, CRYPTO 2007, LNCS 4622, pp. 466-481, 2007.

##### MDHP: Matching Diffie-Hellman Problem

Definition: Let *g* be a generator of group *G* having order *q*. Let and . Given and , find *r*.

Reductions: MDHP ≡_{P} DDH
Handschuh et al. (see below for the reference) showed that the MDHP problem is equivalent to DDH.

Algorithms:

Use in cryptography: E-Cash

History:

References:

- Y. Frankel, Y. Tsiounis, M. Yung, "Indirect Discourse Proofs": Achieving Efficient Fair Off-Line E-Cash, Proceedings of Asiacrypt '96, p. 287-300.
- H. Handschuh, Y. Tsiounis and M. Yung, Decision Oracles are equivalent to Matching Oracles, PKC 1999, LNCS 1560, pp. 276-289.

##### DDLP: Double Discrete Logarithm Problem

Definition: Let *p* and *q* be primes such that *q* = (*p* − 1) / 2. Let *G* be a group of order *p* with generator *g* and be an element of order *q*. Given *g*, *h*, and , compute *x*.

Reductions: DDLP ≤_{P} (DLP in *G* + DLP in )

Algorithms:

Use in cryptography: Public verifiable secret sharing.

History:

References:

- M. Stadler, Publicly Verifiable Secret Sharing, Proceedings of EUROCRYPT '96, p. 190-199.

##### rootDLP: Root of Discrete Logarithm Problem

Definition: Given group generator *g*, positive integer *e*, and , compute integer *x* such that

.

Reductions:

Algorithms:

Use in cryptography: Camenisch and Stadler group signature scheme

History:

References:

- Jan Camenisch and Markus Stadler, Efficient Group Signature Schemes for Large Groups, Proceedings of CRYPTO'97, p. 410-424.

##### n-M-DDH: Multiple Decision Diffie-Hellman Problem

Definition: Let and for random , and a random tuple in *G*. It is hard to tell apart *D* from *D*_{random}.

Algorithms:

Use in cryptography: Group key exchange

References:

- Emmanuel Bresson, Olivier Chevassut, and David Pointcheval, Dynamic Group Diffie-Hellman Key Exchange under Standard Assumptions, EUROCRYPT 2002, LNCS 2332, pp. 321–336.

##### l-HENSEL-DLP: l-Hensel Discrete Logarithm Problem

Definition: Let *G* a subgroup of prime order *r* in , where *p* is a prime with polynomial binary length. Let 1 < *g* < *p* be an integer such that but for some integer . Given for a random *x* such that , compute .

Reductions: l-HENSEL-DLP ≥_{P} DLP

Algorithms:

Use in cryptography:

References:

- Dario Catalano, Phong Q. Nguyen, and Jacques Stern, The Hardness of Hensel Lifting: The Case of RSA and Discrete Logarithm, ASIACRYPT 2002, LNCS 2501, pp. 299–310.

##### DLP(Inn(G)): Discrete Logarithm Problem over Inner Automorphism Group

Definition: Given for some , find

Reductions: DLP(Inn(G)) ≡_{P} *l**o**g*(*G*) DLP

Algorithms:

Use in cryptography: MOR Public Key Cryptosystem

References:

- In-Sok Lee, Woo-Hwan Kim, Daesung Kwon, Sangil Nahm, Nam-Seok Kwak, and Yoo-Jin Baek, On the Security of MOR Public Key Cryptosystem, ASIACRYPT 2004, LNCS 3329 pp. 387-400.

##### IE: Inverse Exponent

Definition: I (Galbraith) think this is just the special case l=1 of l-DHI (l-Diffie-Hellman inversion problem) defined above.

Reductions:

Algorithms:

Use in cryptography:

References:

- Birgit Pfitzmann and Ahmad-Reza Sadeghi, Anonymous fingerprinting with direct non-repudiation, ASIACRYPT 2000, LNCS 1976, pp. 401-414.

##### SE: Square Exponent

Definition: I (Galbraith) think this is Square-DH (already defined above)

Reductions:

Algorithms:

Use in cryptography:

References:

- Ueli M. Maurer and Stefan Wolf, Diffie-Hellman oracles, CRYPTO 96, LNCS 1109, pp. 268-282
- Mike Burmester, Yvo Desmedt, and Jennifer Seberry, Equitable key escrow with limited time span (or, how to enforce time expiration cryptographically), ASIACRYPT 98, LNCS 1514, pp. 380-391

##### TDH: The Twin Diffie-Hellman Assumption

Definition: Let *G* be a cyclic group with genearator *g*, and of prime order *q*.
Define *d**h*(*X*,*Y*) = *Z*, where *X* = *g*^{x},*Y* = *g*^{y},*Z* = *g*^{xy}.
Furthermore define the function
We call this the twin DH function.
One can also define a corresponding twin DH predicate:

iff .

The twin DH assumption states it is hard to compute 2*d**h*(*X*_{1},*X*_{2},*Y*), given random .
The strong twin DH assumption states that it is hard to compute 2*d**h*(*X*_{1},*X*_{2},*Y*), given along with access to a decision oracle for
the predicate which on input , returns .

Reductions: The ordinary DH assumption holds if and only if the strong twin DH assumption holds.

Algorithms: The best known algorithm for it is to solve DLP in *G*.

Use in cryptography:

References: David Cash, Eike Kiltz and Victor Shoup, The Twin Diffie-Hellman Problem and Applications, EUROCRYPT 2008, Springer LNCS 4965, 127-145

##### XTR-DL: XTR discrete logarithm problem

Definition: Let *T**r*(*g*) be an XTR representation of an element of the XTR subgroup of . Given *t* to compute *x* such that
*t* = *T**r*(*g*^{x}).

Algorithms: Best algorithm is to solve DLP in .

Use in cryptography: Most protocols based on DLP can be used with XTR.

History: Introduced by Lenstra and Verheul.

References:

- A. K. Lenstra and E. R. Verheul, The XTR public key system, CRYPTO 2000.

##### XTR-DH: XTR Diffie-Hellman problem

Definition: Let *T**r*(*g*) be an XTR representation of an element of the XTR subgroup of . Given *t*_{1},*t*_{2} to compute *t*_{3} such that
*t*_{1} = *T**r*(*g*^{x}),*t*_{2} = *T**r*(*g*^{y}),*t*_{3} = *T**r*(*g*^{xy}).

Algorithms: Best algorithm is to solve DLP in .

Use in cryptography: Most protocols based on DLP can be used with XTR.

History: Introduced by Lenstra and Verheul.

References:

- A. K. Lenstra and E. R. Verheul, The XTR public key system, CRYPTO 2000.

##### XTR-DHD: XTR decision Diffie-Hellman problem

Definition: Let *T**r*(*g*) be an XTR representation of an element of the XTR subgroup of . Given *t*_{1},*t*_{2},*t*_{3} to determine whether *t*_{3} = *T**r*(*g*^{xy}) for integers *x*,*y* such that
*t*_{1} = *T**r*(*g*^{x}),*t*_{2} = *T**r*(*g*^{y}).

Reductions: DDH ≡_{P} XTR-DHD.

Algorithms: Best algorithm is to solve DLP in .

Use in cryptography: Most protocols based on DLP can be used with XTR.

History: Introduced by Lenstra and Verheul.

References:

- A. K. Lenstra and E. R. Verheul, The XTR public key system, CRYPTO 2000.

##### CL-DLP: discrete logarithms in class groups of imaginary quadratic orders

Definition: Standard discrete logarithm problems in a class group of imaginary quadratic orders.

Reductions: Solving the CL-DLP is at least as hard as solving the integer factorization problem.

Algorithms: Use in cryptography: key-exchange

History: First proposed by Buchmann and Williams in 1988 and 1990. References:

- Buchmann J. and Williams H. C., A key-exchange system based on imaginary quadratic fields, Journal of Cryptology 1, 3 (1988)
- Buchmann J. and Williams H. C., Quadratic fields and cryptography, Number Theory and Cryptography, J. H. Loxton, Ed., vol. 154 of London Mathematical Society Lecture Note Series.
- A. Hamdy and B. Moller, Security of Cryptosystems Based on Class Groups of Imaginary Quadratic Orders, Advances in Cryptology - AsiaCrypt 2000.

##### TV-DDH: Tzeng Variant Decision Diffie-Hellman problem

Definition: Let *q* and *p* = 2*q* + 1 be primes and let be the subgroup of order *q*. Represent as an integer between 1 and *p* − 1 and interpret as the corresponding integer between 0 and *q* − 1.
The computational problem is: Given and to determine whether or not
for some integer *a*.

Algorithms: The best known algorithm for TV-DDH in general is to solve DLP. Note that DDH can be easy for some pairing groups.

Use in cryptography: Conference key agreement.

History:

References:

- W.-G. Tzeng, A practical and secure fault-tolerant conference key agreement protocol, PKC 2000, Springer LNCS 1751, 1-13.

##### n-DHE: n-Diffie-Hellman Exponent problem

The n-DHE problem in a group *G* of prime order *q* is defined as follows: Let . On input , output *g*_{n + 1}.

Use in cryptography: Broadcast encryption, accumulators.