Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
About Open Problems Kapitel lesen Erstes Kapitel lesen

2014 | OriginalPaper | Buchkapitel

The Past, Evolving Present, and Future of the Discrete Logarithm

verfasst von : Antoine Joux, Andrew Odlyzko, Cécile Pierrot

Erschienen in: Open Problems in Mathematics and Computational Science

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The first practical public key cryptosystem ever published, the Diffie–Hellman key exchange algorithm, relies for its security on the assumption that discrete logarithms are hard to compute. This intractability hypothesis is also the foundation for the security of a large variety of other public key systems and protocols.
Since the introduction of the Diffie–Hellman key exchange more than three decades ago, there have been substantial algorithmic advances in the computation of discrete logarithms. However, in general the discrete logarithm problem is still considered to be hard. In particular, this is the case for the multiplicative groups of finite fields with medium to large characteristic and for the additive group of a general elliptic curve.
This chapter presents a survey of the state of the art concerning discrete logarithms and their computation.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel About Open Problems
Nächstes Kapitel Isogenies in Theory and Praxis
Fußnoten
1
Assuming that it is irreducible, which is usually the case.
 
2
The group G and generator g can be the same for many users and can be part of a public standard. However, that can lead to a reduction in security of the system.
 
3
In general, asymmetric pairings are also considered. For simplicity of presentation, we only describe the symmetric case.
 
4
If | G | is a product of many small primes, possibly with multiplicity, this claim does not hold. However, this is not an interesting case for cryptographic purposes.
 
5
In other words, the number of oracle calls is a polynomial in the bitsize of the answer.
 
6
Since there are many distinct generators of G, in fact \(\varphi (G)\), g 0 is easy to find by testing random candidates.
 
7
Typically, an error probability of 1∕3 can be used in the formal definition of BQP.
 
8
As usual, the \(\tilde{O}\) notation \(\tilde{O}(n)\) is a shorthand for \(O(n\log ^{\alpha }n)\) for an arbitrary value of α.
 
9
Up to logarithmic factors.
 
10
Or at least, a large fraction of these logarithms. Indeed, depending on the exact properties of the relation collection phase, a few elements of the smoothness basis might possibly be missing.
 
11
See Sect. 3.3 to understand the origin of this L notation. For the moment, just read L q (α, c) as a shorthand for \(\exp \left ((c + o(1))(\log q)^{\alpha }(\log \log q)^{1-\alpha }\right ).\)
 
12
Note that those subsets are sometimes called the smoothness bases by some authors too.
 
13
Note that since logq is the number of bits necessary to encode elements of the group we are considering, it is the natural parameter to consider when expressing the complexity of algorithms.
 
14
More precisely, this is the goal of Wiedemann algorithm. The block version computes something somewhat different but quite similar.
 
Literatur
[Adl79]
L.M. Adleman, A subexponential algorithm for the discrete logarithm problem with applications to cryptography (abstract), in FOCS (1979), pp. 55–60
[AFK89]
[AH99]
L.M. Adleman, M.-D.A. Huang, Function field sieve method for discrete logarithms over finite fields. Inf. Comput. 151(1–2), 5–16 (1999)CrossRefMATHMathSciNet
[BBG05]
D. Boneh, X. Boyen, E.-J. Goh, Hierarchical identity based encryption with constant size ciphertext, in EUROCRYPT (2005), pp. 440–456
[BD94]
M. Burmester, Y. Desmedt, A secure and efficient conference key distribution system (extended abstract), in EUROCRYPT (1994), pp. 275–286
[BF03]
[BGJT13]
R. Barbulescu, P. Gaudry, A. Joux, E. Thomé, A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic. CoRR (2013). abs/1306.4244
[BLS04]
D. Boneh, B. Lynn, H. Shacham, Short signatures from the Weil pairing. J. Cryptol. 17(4), 297–319 (2004)MATHMathSciNet
[BLS11]
D.J. Bernstein, T. Lange, P. Schwabe, On the correct use of the negation map in the Pollard Rho method, in Public Key Cryptography (2011), pp. 128–146
[BP14]
R. Barbulescu, C. Pierrot, The multiple number field sieve for medium and high characteristic finite fields. IACR Cryptol. ePrint Arch. 2014, 147 (2014)
[CEP83]
E.R. Canfield, P. Erdös, C. Pomerance, On a problem of Oppenheim concerning factorisatio numerorum. J. Number Theory 17, 1–28 (1983)CrossRefMATHMathSciNet
[CGH00]
R. Canetti, O. Goldreich, S. Halevi, The random oracle methodology, revisited. CoRR (2000). cs.CR/0010019
[CHK12]
[Cop84]
D. Coppersmith, Fast evaluation of logarithms in fields of characteristic two. IEEE Trans. Inf. Theory 30(4), 587–593 (1984)CrossRefMATHMathSciNet
[COS86]
[Den82]
D.E. Denning, Cryptography and Data Security (Addison-Wesley, Reading, 1982)MATH
[Den02]
A.W. Dent, Adapting the weaknesses of the random oracle model to the generic group model, in ASIACRYPT (2002), pp. 100–109
[DH76]
[DK13]
C. Diem, S. Kochinke, Computing discrete logarithms with special linear systems. Preprint (2013)
[DOW92]
W. Diffie, P.C. Oorschot, M.J. Wiener, Authentication and authenticated key exchanges. Des. Codes Cryptogr. 2(2), 107–125 (1992)CrossRefMathSciNet
[EGT11]
A. Enge, P. Gaudry, E. Thomé, An L(1∕3) discrete logarithm algorithm for low degree curves. J. Cryptol. 24(1), 24–41 (2011)CrossRefMATH
[FJM13]
P.-A. Fouque, A. Joux, C. Mavromati, Multi-user collisions: applications to discrete logs, Even-Mansour and prince. IACR Cryptol. ePrint Arch. 2013, 761 (2013)
[FPPR12]
J.-C. Faugère, L. Perret, C. Petit, G. Renault, Improving the complexity of index calculus algorithms in elliptic curves over binary fields, in EUROCRYPT (2012), pp. 27–44
[FR94]
G. Frey, H. Georg Rück, A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves. Math. Comput. 62, 865–874 (1994)MATH
[FS86]
A. Fiat, A. Shamir, How to prove yourself: practical solutions to identification and signature problems, in CRYPTO (1986), pp. 186–194
[Gam85]
T. El Gamal, A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory 31(4), 469–472 (1985)CrossRefMATH
[GGMZ13]
F. Göloglu, R. Granger, G. McGuire, J. Zumbrägel, On the function field sieve and the impact of higher splitting probabilities—application to discrete logarithms in and, in CRYPTO (2) (2013), pp. 109–128
[GHS02]
P. Gaudry, F. Hess, N.P. Smart, Constructive and destructive facets of Weil descent on elliptic curves. J. Cryptol. 15(1), 19–46 (2002)CrossRefMathSciNet
[GKZ14]
R. Granger, T. Kleinjung, J. Zumbrägel, On the powers of 2. Cryptology ePrint Archive, Report 2014/300 (2014)
[Gor93]
[GTTD07]
P. Gaudry, E. Thomé, N. Thériault, C. Diem, A double large prime variation for small genus hyperelliptic index calculus. Math. Comput. 76(257), 475–492 (2007)CrossRefMATH
[HR82]
M.E. Hellman, J.M. Reyneri, Fast computation of discrete logarithms in GF(q), in CRYPTO (1982), pp. 3–13
[JL02]
A. Joux, R. Lercier, The function field sieve is quite special, in ANTS (2002), pp. 431–445
[JL03]
A. Joux, R. Lercier, Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the gaussian integer method. Math. Comput. 72(242), 953–967 (2003)MATHMathSciNet
[JL06]
A. Joux, R. Lercier, The function field sieve in the medium prime case, in EUROCRYPT (2006), pp. 254–270
[JLSV06]
A. Joux, R. Lercier, N.P. Smart, F. Vercauteren, The number field sieve in the medium prime case, in CRYPTO (2006), pp. 326–344
[JN03]
A. Joux, K. Nguyen, Separating decision Diffie-Hellman from computational Diffie-Hellman in cryptographic groups. J. Cryptol. 16(4), 239–247 (2003)CrossRefMATHMathSciNet
[Jou04]
A. Joux, A one round protocol for tripartite Diffie-Hellman. J. Cryptol. 17(4), 263–276 (2004)MATHMathSciNet
[Jou13a]
A. Joux, Faster index calculus for the medium prime case application to 1175-bit and 1425-bit finite fields, in EUROCRYPT (2013), pp. 177–193
[Jou13b]
A. Joux, A new index calculus algorithm with complexity \(L(1/4 + o(1))\) in very small characteristic. IACR Cryptol. ePrint Arch. 2013, 95 (2013)
[JP13]
A. Joux, C. Pierrot, The special number field sieve in finite fields - application to pairing-friendly constructions, in Pairing (2013), pp. 45–61
[JV12]
A. Joux, V. Vitse, Cover and decomposition index calculus on elliptic curves made practical—application to a previously unreachable curve over \(\mathbb{F}_{p^{6}}\), in EUROCRYPT (2012), pp. 9–26
[Kra22]
M. Kraïtchik, Théorie des nombres (Gauthier-Villars, Paris, 1922)MATH
[KS01]
F. Kuhn, R. Struik, Random walks revisited: extensions of Pollard’s Rho algorithm for computing multiple discrete logarithms, in Selected Areas in Cryptography (2001), pp. 212–229
[LO90]
B.A. LaMacchia, A.M. Odlyzko, Solving large sparse linear systems over finite fields, in CRYPTO (1990), pp. 109–133
[MOV93]
A. Menezes, T. Okamoto, S.A. Vanstone, Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Trans. Inf. Theory 39(5), 1639–1646 (1993)CrossRefMATHMathSciNet
[MW96]
U.M. Maurer, S. Wolf, Diffie-Hellman oracles, in CRYPTO (1996), pp. 268–282
[Odl85]
A.M. Odlyzko, Discrete logarithms in finite fields and their cryptographic significance. Adv. Cryptol. 209, 224–314 (1985)CrossRefMathSciNet
[Pai99]
P. Paillier, Public-key cryptosystems based on composite degree residuosity classes, in EUROCRYPT (1999), pp. 223–238
[PGF98]
D. Panario, X. Gourdon, P. Flajolet, An analytic approach to smooth polynomials over finite fields, in ANTS (1998), pp. 226–236
[PH78]
S.C. Pohlig, M.E. Hellman, An improved algorithm for computing logarithms over gf(p) and its cryptographic significance (corresp.). IEEE Trans. Inf. Theory 24(1), 106–110 (1978)
[Pol75]
[Pol78]
J. Pollard, Monte Carlo methods for index computations mod p. Math. Comput., 32(143), 918–924 (1978)
[Pom87]
C. Pomerance, Discrete Algorithms and Complexity: Proceedings of the Japan-US Joint Seminar, June 4-6, 1986, Kyoto, Japan, D. S. Johnson, T. Nishizeki, A. Nozaki and H. S. Wilf (Editors), Academic Press, New York, (1987)
[PQ12]
C. Petit, J.-J. Quisquater, On polynomial systems arising from a Weil descent, in ASIACRYPT (2012), pp. 451–466
[QD89]
J.-J. Quisquater, J.-P. Delescaille, How easy is collision search. New results and applications to DES, in CRYPTO (1989), pp. 408–413
[Sch89]
C.-P. Schnorr, Efficient identification and signatures for smart cards, in CRYPTO (1989), pp. 239–252
[Sch00]
[Sem04]
I. Semaev, Summation polynomials and the discrete logarithm problem on elliptic curves. IACR Cryptol. ePrint Arch. 2004, 31 (2004)
[Sha71]
D. Shanks, Class number, a theory of factorization and genera, in Proceedings of the Symposium on Pure Mathematics (1971), pp. 415–440
[Sho97a]
P.W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)CrossRefMATHMathSciNet
[Sho97b]
V. Shoup, Lower bounds for discrete logarithms and related problems, in EUROCRYPT (1997), pp. 256–266
[SWD96]
O. Schirokauer, D. Weber, T.F. Denny, Discrete logarithms: the effectiveness of the index calculus method, in ANTS (1996), pp. 337–361
[Tes00]
[vOW99]
P.C. van Oorschot, M.J. Wiener, Parallel collision search with cryptanalytic applications. J. Cryptol. 12(1), 1–28 (1999)CrossRefMATH
[Wie86]
Metadaten
Titel
The Past, Evolving Present, and Future of the Discrete Logarithm
verfasst von
Antoine Joux
Andrew Odlyzko
Cécile Pierrot
Copyright-Jahr
2014
Buch
Open Problems in Mathematics and Computational Science

Print ISBN: 978-3-319-10682-3

Electronic ISBN: 978-3-319-10683-0

Copyright-Jahr: 2014

DOI
https://doi.org/10.1007/978-3-319-10683-0_2