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 = g x$ .

Reductions: CDH ≤_P DLP, DLP ≤_P CDH when auxiliary information is given (Maurer reduction), FACTORING ≤_P 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 $g a b$ .

Reductions:

CDH ≤_P DLP
DLP ≤_subexp 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 $h a$ .

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

Reductions: DDH ≤_P 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 = g a b$ .

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

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: PDDH ≡_P 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-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 $g^a, g^{a^2}, \ldots, g^{a^l} \in G$ to compute $g 1 / a$ .

Reductions: l-DHI ≤_P 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 = 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 $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: 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 s y, a x + s x y)$ , to compute $(t, b, b t y, b x + t x y)$ where $b \ne 1$ and $t$ is not one of the $s$ on which O was queried.

Reductions: LRSW ≤_P 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 $g c + d$ .

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

Reductions: l-SDH ≤_P 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 = 2 q$ 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-DLSE ≤_P 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 $g b$ .

Reductions: CONF ≤_P 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 = s a, B = s b, C = s a b$ if such an $s$ exists.

Reductions: 3PASS ≤_P 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 $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)$

Reductions: LUCAS ≡_P 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 $g d$ and $g x$ where $x = x (g a)$ and $g a$ is an arbitrary element in the group.

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

Reductions: DDLP ≤_P (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 $D r a n d o m$ .

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

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 x y$ . 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 $2 d h (X 1, X 2, Y)$ , given random $X_1,X_2,Y\in G$ . The strong twin DH assumption states that it is hard to compute $2 d h (X 1, X 2, 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 $T r (g)$ be an XTR representation of an element of the XTR subgroup of $F_{p^6}^*$ . Given $t$ to compute $x$ such that $t = T r (g x)$ .

Reductions: DLP ≡_P 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 $T r (g)$ be an XTR representation of an element of the XTR subgroup of $F_{p^6}^*$ . 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 x y)$ .

Reductions: CDH ≡_P 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 $T r (g)$ be an XTR representation of an element of the XTR subgroup of $F_{p^6}^*$ . Given $t 1, t 2, t 3$ to determine whether $t 3 = T r (g x y)$ 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 $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 = 2 q + 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-DDH ≡_P 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 $g n + 1$ .

Use in cryptography: Broadcast encryption, accumulators.

Retrieved from "http://www.ecrypt.eu.org/wiki/index.php/Discrete_Logarithms"

Views

Personal tools

Log in / create account

Search

Toolbox