On the complexity of the discrete logarithm and Diffie-Hellman problems

DOI10.1016/j.jco.2004.01.002zbMath1052.94014MaRDI QIDQ1827563

Ian F. Blake, Theo Garefalakis

Publication date: 6 August 2004

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jco.2004.01.002

zbMATH Keywords

cryptography; discrete logarithm problem; Diffie-Hellman problems

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

11T71: Algebraic coding theory; cryptography (number-theoretic aspects)

94A60: Cryptography

68P25: Data encryption (aspects in computer science)

11Y16: Number-theoretic algorithms; complexity

Related Items

The Diffie-Hellman key exchange protocol and non-Abelian nilpotent groups, On the bit security of the Diffie-Hellman key

Uses Software

• Oracle

Cites Work

• A key-exchange system based on imaginary quadratic fields
• Breaking generalized Diffie-Hellman modulo a composite is no easier than factoring
• On the distribution of the Diffie-Hellman pairs
• Security of most significant bits of \(g^{x^{2}}\).
• Linear complexity of the discrete logarithm
• Separating decision Diffie-Hellman from computational Diffie-Hellman in cryptographic groups
• Complexity of a determinate algorithm for the discrete logarithm
• Counting points on elliptic curves over finite fields
• The Diffie-Hellman protocol
• On the Distribution of Diffie--Hellman Triples with Sparse Exponents
• Polynomial representations of the Diffie-Hellman mapping
• A general framework for subexponential discrete logarithm algorithms
• On the connection between the discrete logarithms and the Diffie-Hellman problem
• Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes
• Diffie-Hellman Oracles
• Algorithms for Black-Box Fields and their Application to Cryptography
• A simple and fast probabilistic algorithm for computing square roots modulo a prime number (Corresp.)
• New directions in cryptography
• Monte Carlo Methods for Index Computation (mod p)
• Real and imaginary quadratic representations of hyperelliptic function fields
• The Relationship Between Breaking the Diffie--Hellman Protocol and Computing Discrete Logarithms
• A Remark Concerning m-Divisibility and the Discrete Logarithm in the Divisor Class Group of Curves
• Reducing elliptic curve logarithms to logarithms in a finite field
• On Certain Exponential Sums and the Distribution of Diffie-Hellman Triples
• The Tate pairing and the discrete logarithm applied to elliptic curve cryptosystems
• A sieve algorithm for the shortest lattice vector problem
• Algebraic aspects of cryptography. With an appendix on hyperelliptic curves by Alfred J. Menezes, Yi-Hong Wu, and Robert J. Zuccherato
• Cryptography in quadratic function fields
• On the statistical properties of Diffie-Hellman distributions
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item