On the complexity of the discrete logarithm and Diffie-Hellman problems
type: Item
instance of: scholarly article
title: On the complexity of the discrete logarithm and Diffie-Hellman problems
zbMATH Open document ID: 1052.94014
author: Theo Garefalakis
author: Ian Blake
published in: Journal of Complexity
publication date: 2004-08-06T00:00:00Z
review text: The discrete logarithm problem (DLP): given an element \(a\) in a cyclic group \(G=\langle g\rangle\) of order \(n\) find the unique integer \(x\),\,\, \(0\leq x \leq n-1\) such that \(a = g^x\), is widely believed to be a computationally hard problem. It was proposed as a one-way function for use in public-key cryptography in the foundational paper of \textit{W. Diffie} and \textit{M. E. Hellman} [IEEE Trans. Inf. Theory 22, 644--654 (1976; Zbl 0435.94018)]. In that paper Diffie and Hellman also give a key exchange method related to DLP: two users randomly choose integers \(a,b\in (1,n)\)\,\, and they exchange \(g^a,g^b\). Each of them is then able to compute the common value \(g^{ab}\). The computation of \(g^{ab}\)\, given only \(g^a,g^b\) is called the Diffie-Hellman problem (DHP). Of course if one can solve DLP one can also solve DHP. A connected problem is the decision DHP (DDHP): given \(g^a,g^b,g^c\)\, decide if \(ab\equiv c \bmod n\). In general, DDHP is no harder than DHP and this is no harder than DLP. The object of the present paper is the study of some aspects of these relationships. In Section 2 the authors give an overview of the state of the art of these three and other related problems. Section 3 deals with the computational complexity of these problems in generic cyclic groups. An algorithm is called generic if it works for arbitrary groups, in contrast to algorithms that make use of some particular presentation of the group elements, as is the case in the well-known index-calculus method, which provides an algorithm of subexponential complexity for the DLP in multiplicative groups of finite fields and in Jacobians of hyperelliptic curves of large genus. Section 5 is the core of the paper. The authors first remember a previous result of \textit{D. Boneh} and \textit{R. Venkatesan} [Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes, Proc. CRYPTO `96, Lect. Notes Comput. Sci. 1109, 129--142 (1996)] t…
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 11T71
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68P25
zbMATH DE Number: 2083563
zbMATH Keywords: cryptography
zbMATH Keywords: discrete logarithm problem
zbMATH Keywords: Diffie-Hellman problems
reviewed by: Juan Tena Ayuso
describes a project that uses: Oracle
MaRDI profile type: Publication
full work available at URL: j.jco.2004.01.002
OpenAlex ID: W2020427895
cites work: A sieve algorithm for the shortest lattice vector problem
cites work: Breaking generalized Diffie-Hellman modulo a composite is no easier than factoring
cites work: Q4265362
cites work: Q3840150
cites work: Algorithms for Black-Box Fields and their Application to Cryptography
cites work: Q4783727
cites work: Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes
cites work: Q5501847
cites work: A key-exchange system based on imaginary quadratic fields
cites work: Q3495438
cites work: On Certain Exponential Sums and the Distribution of Diffie-Hellman Triples
cites work: On the statistical properties of Diffie-Hellman distributions
cites work: On the connection between the discrete logarithms and the Diffie-Hellman problem
cites work: New directions in cryptography
cites work: A general framework for subexponential discrete logarithm algorithms
cites work: An extension of Satoh's algorithm and its implementation
cites work: The Tate pairing and the discrete logarithm applied to elliptic curve cryptosystems
cites work: A Remark Concerning m-Divisibility and the Discrete Logarithm in the Divisor Class Group of Curves
cites work: On the distribution of Diffie-Hellman triples with sparse exponents
cites work: Q3044320
cites work: Q3374896
cites work: Q4263442
cites work: Q2708626
cites work: Separating decision Diffie-Hellman from computational Diffie-Hellman in cryptographic groups
cites work: Algebraic aspects of cryptography. With an appendix on hyperelliptic curves by Alfred J. Menezes, Yi-Hong Wu, and Robert J. Zuccherato
cites work: Linear complexity of the discrete logarithm
cites work: Polynomial representations of the Diffie-Hellman mapping
cites work: Q4940702
cites work: Diffie-Hellman Oracles
cites work: Q4249629
cites work: The Relationship Between Breaking the Diffie--Hellman Protocol and Computing Discrete Logarithms
cites work: The Diffie-Hellman protocol
cites work: Q3141896
cites work: Reducing elliptic curve logarithms to logarithms in a finite field
cites work: Q4856179
cites work: Complexity of a determinate algorithm for the discrete logarithm
cites work: Q2724585
cites work: Real and imaginary quadratic representations of hyperelliptic function fields
cites work: A simple and fast probabilistic algorithm for computing square roots modulo a prime number (Corresp.)
cites work: Monte Carlo Methods for Index Computation (mod p)
cites work: Q4409128
cites work: The canonical lift of an ordinary elliptic curve over a finite field and its point counting
cites work: Cryptography in quadratic function fields
cites work: Counting points on elliptic curves over finite fields
cites work: On the distribution of the Diffie-Hellman pairs
cites work: Security of most significant bits of \(g^{x^{2}}\).
cites work: Square-root algorithms for the discrete logarithm problem (a survey)
DOI: 10.1016/J.JCO.2004.01.002
description: scientific article; zbMATH DE number 2083563