# Discrete Logarithms

#### 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 $G = \langle g \rangle$ 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 $h \in G$ to compute x such that h = gx.

Reductions: CDHP DLP, DLPP CDH when auxiliary information is given (Maurer reduction), FACTORINGP DLP in $Z_N^*$.

Algorithms: The best known algorithm for DLP in general is the parallel Pollard rho method, which has complexity $O(\sqrt{ r} )$ group operations. For particular groups, such as finite fields, tori, divisor class groups of curves of genus $g \ge 3$ 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 $g_0, g_0^x \in G$ 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 $g^a, g^b \in G$ to compute gab.

Reductions:

• CDHP DLP
• DLPsubexp CDH in groups of squarefree order.

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 $g_0, g_0^a, g_0^b \in G$ to compute $g_0^{ab}$. 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 $g, g^a \in G$. Given $h \in G$to compute ha.

Reductions: SDHP CDH.

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 $g^a, g^b \in G$ to compute gab where the algorithm has access to an oracle which solves the DDH problem.

Reductions: gap-CDHP 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 $g^a, g^b, h \in G$ to determine whether or not h = gab.

Reductions: DDHP CDH.

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 $g_0, g_0^a, g_0^b, h \in G$ to determine whether or not $h = g_0^{ab}$. 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 $g, g^a, g^b, g^{b^{-1}}, h \in G$ to determine whether or not h = gab.

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 Zr. Given f(a) and $g^b, h \in G$ to determine whether or not h = gab.

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 $g^{x_1},..., g^{x_n}, h_1,...,h_n\in G$ to determine whether or not $h_1 = g^{x_{1}x_{2}},..., h_{n-1}=g^{x_{n-1}x_n}, h_n=g^{x_{n}x_{1}}$.

Reductions: PDDHP DDH.

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 $g^a \in G$ to compute $g^{a^{2}}$.

Reductions: Square-DHP 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 $g^a, g^{a^2}, \ldots, g^{a^l} \in G$ to compute g1 / a.

Reductions: l-DHIP CDH.

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 $g^a, g^{a^2}, \ldots, g^{a^l}, v \in G$ to determine whether v = g1 / a.

Reductions: l-DDHIP 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 $g_1, \dots, g_k, h \in G$ to compute $a_1,\dots,a_k$ such that $h = g_1^{a_1} \dots g_k^{a_k}$.

Reductions: REPRESENTATIONP 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,gx,gy and an oracle O which on input s chooses a random a = gz and answers (a,asy,ax + sxy), to compute (t,b,bty,bx + txy) where $b \ne 1$ and t is not one of the s on which O was queried.

Reductions: LRSWP DLP.

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 $g^a, g^b, g^{ac}, g^{bd} \in G$ to compute gc + d.

Reductions: LinearP DLP.

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 $g^a, g^b, g^{ac}, g^{bd}, v \in G$ to decide if v = gc + d.

Reductions: D-Linear1P 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 $g^a, g^{a^2}, \ldots, g^{a^l} \in G$ to find $w \in F_q$ and g1 / (a + w)

Reductions: l-SDHP DLP.

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 $G=Z_p^*$ such that p − 1 = 2q for p,q primes and let c be an integer. Given $g^x \mod p$ for $0\leq x \leq 2^c$ to find x.

Reductions: c-DLSEP DLP.

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 $g, g^a, g^{ab} \in G$ to compute gb.

Reductions: CONFP CDH

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 $A,B,C \in G$ to compute s such that A = sa,B = sb,C = sab if such an s exists.

Reductions: 3PASSP CONF

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 $p, z \in \langle V_t(m) \rangle$ to compute x such that Vx(m) = z where Vt(m) is defined as V0(m) = 2,V1(m) = m,Vt(m) = mVt − 1(m) − Vt − 2(m)

Reductions: LUCASP CDLP

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 $E(\mathbb{F}_q)$, we write $x(P)=\overline{x}$ where $\overline{x}\in \mathbb{Z}$ is obtaining by taking the bit representation of the x-coordinate of $P\in \mathbb{F}_q^2$, and considering this as the bit representation of an integer.

The x-Logarithm Problem is to distinguish between gd and gx where x = x(ga) and ga is an arbitrary element in the group.

Reductions: XLPP DDH

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 $a_0, b_0, a_1, b_1 \in_R \Z_q$ and $r \in_R \{0,1\}$. Given $(g^{a_0}, g^{a_0b_0},g^{a_1}, g^{a_1b_1})$ and $(g^{b_r},g^{b_{1-r}})$, find r.

Reductions: MDHPP 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 $h \in Z_p^*$ be an element of order q. Given g, h, and $a = g^{(h^x)}$, compute x.

Reductions: DDLPP (DLP in G + DLP in $Z_p^*$ )

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 $a\in G$, compute integer x such that

$a = g^{(x^e)}$.

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 $n\geq 2$ and $D=(g^{x_1},\ldots,g^{x_n},\{g^{x_i x_j}\}_{1\leq i < j \leq n})$ for random $x_1,\ldots,x_n\in Z_r$, and $D_{random}=(g_1,\ldots,g_n,\{g_{ij}\}_{1\leq i < j \leq n})$ a random tuple in G. It is hard to tell apart D from Drandom.

Reductions: DDHP n-M-DDH

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 $Z_p^*$, where p is a prime with polynomial binary length. Let 1 < g < p be an integer such that $g^r \equiv 1 \pmod{p^{\ell-1}}$ but $g^r \not\equiv 1 \pmod{p^\ell}$ for some integer $\ell > 1$. Given $g^x \mod p$ for a random x such that $1\leq x\leq r-1$, compute $g^x \mod p^\ell$.

Reductions: l-HENSEL-DLPP 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 $\phi,\phi^s \in Inn(G)$ for some $s \in \Z$, find $s(mod \mid\phi\mid)$

Reductions: DLP(Inn(G))P log(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 dh(X,Y) = Z, where X = gx,Y = gy,Z = gxy. Furthermore define the function $2dh:{G}^3\mapsto {G}^2$ $(X_1,X_2,Y) \mapsto (dh(X_1,Y),dh(X_2,Y)).$ We call this the twin DH function. One can also define a corresponding twin DH predicate:

$2dhp(X_1,X_2,\hat Y,\hat Z_1,\hat Z_2)=1$ iff $2dh(X_1,X_2,\hat Y)=(\hat Z_1,\hat Z_2)$.

The twin DH assumption states it is hard to compute 2dh(X1,X2,Y), given random $X_1,X_2,Y\in G$. The strong twin DH assumption states that it is hard to compute 2dh(X1,X2,Y), given $X_1,X_2,Y\in G$ along with access to a decision oracle for the predicate $2dhp(X_1,X_2,\cdot,\cdot,\cdot)$ which on input $(\hat Y,\hat Z_1,\hat Z_2)$, returns $2dhp(X_1,X_2,\hat Y,\hat Z_1,\hat Z_2)$.

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 Tr(g) be an XTR representation of an element of the XTR subgroup of $F_{p^6}^*$. Given t to compute x such that t = Tr(gx).

Reductions: DLPP XTR-DL.

Algorithms: Best algorithm is to solve DLP in $F_{p^6}^*$.

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 Tr(g) be an XTR representation of an element of the XTR subgroup of $F_{p^6}^*$. Given t1,t2 to compute t3 such that t1 = Tr(gx),t2 = Tr(gy),t3 = Tr(gxy).

Reductions: CDHP XTR-DH.

Algorithms: Best algorithm is to solve DLP in $F_{p^6}^*$.

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 Tr(g) be an XTR representation of an element of the XTR subgroup of $F_{p^6}^*$. Given t1,t2,t3 to determine whether t3 = Tr(gxy) for integers x,y such that t1 = Tr(gx),t2 = Tr(gy).

Reductions: DDHP XTR-DHD.

Algorithms: Best algorithm is to solve DLP in $F_{p^6}^*$.

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 = 2q + 1 be primes and let $G \subseteq \mathbb{F}_p^*$ be the subgroup of order q. Represent $h \in G$ as an integer between 1 and p − 1 and interpret $h \mod{q}$ as the corresponding integer between 0 and q − 1. The computational problem is: Given $g_1, g_2 \in G$ and $0 \le u_1, u_2 < q$ to determine whether or not $u_1 = g_1^a \mod{q}, u_2 = g_2^a \mod{q}$ for some integer a.

Reductions: TV-DDHP DDH.

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 $g_i = g^{\lambda^i} , \lambda \gets Z_q$. On input $\{g, g_1 , g_2 , \ldots , g_n , g_{n+2} , \ldots , g_{2n} \} \in G^{2n}$ , output gn + 1.

Use in cryptography: Broadcast encryption, accumulators.