# Lower Bounds for Discrete Logarithms and Related Problems

@inproceedings{Shoup1997LowerBF, title={Lower Bounds for Discrete Logarithms and Related Problems}, author={Victor Shoup}, booktitle={EUROCRYPT}, year={1997} }

This paper considers the computational complexity of the discrete logarithm and related problems in the context of "generic algorithms"--that is, algorithms which do not exploit any special properties of the encodings of group elements, other than the property that each group element is encoded as a unique binary string. Lower bounds on the complexity of these problems are proved that match the known upper bounds: any generic algorithm must perform Ω(p1/2) group operations, where p is the… Expand

#### Topics from this paper

#### 1,176 Citations

A Note on Security Proofs in the Generic Model

- Computer Science
- ASIACRYPT
- 2000

Practical pitfalls when applying the generic model to other schemes than the discrete-log problem and when interpreting such lower bounds as security proofs for these schemes are discussed. Expand

Generic Hardness of the Multiple Discrete Logarithm Problem

- Mathematics, Computer Science
- EUROCRYPT
- 2015

The tight generic lower bound of the multiple discrete logarithm problem is proved, showing that the previously known algorithms are asymptotically optimal. Expand

Lower Bounds on Generic Algorithms in Groups

- Mathematics, Computer Science
- EUROCRYPT
- 1998

It is shown that the two problems are not computationally equivalent in a generic sense for groups whose orders contain a multiple large prime factor, which complements earlier results which stated this equivalence for all other groups. Expand

Hard Instances of the Constrained Discrete Logarithm Problem

- Mathematics, Computer Science
- ANTS
- 2006

This work draws on earlier results due to Erdos et al. and Schnorr, develops geometric tools such as generalized Menelaus’ theorem for proving lower bounds on the complexity of the constrained DLP, and constructs explicit sets with provable non-trivial lower bounds. Expand

Finding discrete logarithms with a set orbit distinguisher

- Mathematics, Computer Science
- J. Math. Cryptol.
- 2012

This work considers finding discrete logarithms in a group of prime order p when the help of an algorithm D that distinguishes certain subsets of from each other is available, and proves that for some of these classes no algorithm for distinguishing can be efficient. Expand

Bounds in Various Generalized Settings of the Discrete Logarithm Problem

- Mathematics, Computer Science
- ACNS
- 2017

This work can be regarded as a generalization and extension on the hardness of the multiple discrete logarithm problem analyzed by Yun (EUROCRYPT ’15). Expand

On Polynomial Approximation of the Discrete Logarithm and the Diffie—Hellman Mapping

- Mathematics, Computer Science
- Journal of Cryptology
- 2015

Improved lower bounds are obtained on the degree and sensitivity of Boolean functions on bits of x deciding whether x is a quadratic residue and for the Diffie—Hellman mapping gx→ gx2, where g is a primitive root of a finite field of q elements Fq . Expand

The Discrete-Logarithm Problem with Preprocessing

- Computer Science
- IACR Cryptol. ePrint Arch.
- 2017

Motivated by surprising recent preprocessing attacks on the discrete-log problem, this paper study the power and limits of such algorithms that use preprocessing. Expand

Comparison of the complexity of Diffie–Hellman and discrete logarithm problems

- Computer Science
- Journal of Computer Virology and Hacking Techniques
- 2020

The article presents an algorithm for solving the discrete logarithm problem with an oracle, solving the Diffie–Hellman problem, and the degree of logarathm in the estimation of the complexity of the algorithm presented is reduced to one. Expand

UNEXPOSED EXPONENTS The Ornery Case of the Discrete Log Problem in Cryptography

- Mathematics
- 2010

The discrete log problem is the name given to the fact that, while computing exponentiation in nite cyclic groups is easy, the reverse operation - the discrete analogue of the classical logarithm -… Expand

#### References

SHOWING 1-10 OF 15 REFERENCES

An improved algorithm for computing logarithms over GF(p) and its cryptographic significance (Corresp.)

- Mathematics, Computer Science
- IEEE Trans. Inf. Theory
- 1978

An improved algorithm is derived which requires O =(\log^{2} p) complexity if p - 1 has only small prime factors and such values of p must be avoided in the cryptosystem. Expand

An Improved Algorithm for Computing Logarithms over GP(p) and Its Cryptographic Significance

- Computer Science
- 1973

An improved algorithm is derived which requires O(log2 p) complexity if p 1 has only small prime factors and such values of p must be avoided in the cryptosystem. Expand

Diie-hellman Oracles

- 1996

This paper consists of three parts. First, various types of Diie-Hellman oracles for a cyclic group G and subgroups of G are de-ned and their equivalence is proved. In particular, the security of… Expand

Towards the Equivalence of Breaking the Diffie-Hellman Protocol and Computing Discrete Logarithms

- Mathematics, Computer Science
- CRYPTO
- 1994

It is proved that breaking the Diffie-Hellman protocol for G and base g is equivalent to computing discrete logarithms in G to the base g when a certain side information string S is given. Expand

Diffie-Hellman Oracles

- Mathematics, Computer Science
- CRYPTO
- 1996

Several new conditions for the polynomial-time equivalence of breaking the Diffie-Hellman protocol and computing discrete logarithms in G are derived which extend former results by den Boer and Maurer. Expand

Algorithms for Black-Box Fields and their Application to Cryptography (Extended Abstract)

- Computer Science
- CRYPTO
- 1996

The results show that any algebraically homomorphic cryptosystem can be broken in sub-exponential time and it is proved that manipulating black box fields over the rationals is as hard as factoring integers. Expand

On the Complexity of Matrix Group Problems I

- Mathematics, Computer Science
- FOCS
- 1984

A theory of black box groups is built, and it is proved that for such subgroups, membership and divisor of the order are in NPB, and under a plausible mathematical hypothesis on short presentations of finite simple groups, nom membership and exaact order will also be inNPB. Expand

Monte Carlo methods for index computation ()

- Mathematics
- 1978

We describe some novel methods to compute the index of any integer relative to a given primitive root of a prime p. Our flrst method avoids the use of stored tables and apparently requires O(p 1/2)… Expand

A hard-core predicate for all one-way functions

- Mathematics, Computer Science
- STOC '89
- 1989

This paper proves a conjecture of [Levin 87, sec. 5.6.2] that the scalar product of Boolean vectors p, g, x is a hard-core of every one-way function ƒ, and extends to multiple (up to the logarithm of security) such bits and to any distribution on the <italic>x</italic>. Expand

Fast Probabilistic Algorithms for Verification of Polynomial Identities

- Computer Science
- J. ACM
- 1980

Vanous fast probabdlsttc algonthms, with probability of correctness guaranteed a prion, are presented for testing polynomial ldentmes and propemes of systems of polynomials and ancdlary fast algorithms for calculating resultants and Sturm sequences are given. Expand