Strict Standards: Declaration of APCBagOStuff::delete() should be compatible with BagOStuff::delete($key, $time = 0) in /usr/share/mediawiki1.7/includes/BagOStuff.php on line 499
Discrete Logarithms - Wiki

Discrete Logarithms

From Wiki

Jump to: navigation, search


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 Gto 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.


Personal tools