Paper 2010/370

Finding discrete logarithms with a set orbit distinguisher

Robert P. Gallant

Abstract

We consider finding discrete logarithms in a group $\GG$ when the help of an algorithm $D$ that distinguishes certain subsets of $\GG$ from each other is available. For a group $\GG$ of prime order $p$, if algorithm $D$ is polynomial-time with complexity c(\log(p))$, we can find discrete logarithms faster than square-root algorithms. We consider two variations on this idea and give algorithms solving the discrete logarithm problem in $\GG$ with complexity ${\cal O}(p^{\frac{1}{3}}\log(p)^3 + p^{\frac{1}{3}}c(\log(p) )$ and ${\cal O}(p^{\frac{1}{4}}\log(p)^3 + p^{\frac{1}{4}}c( \log(p) )$ in the best cases. When multiple distinguishers are available logarithms can be found in polynomial time. We discuss natural classes of algorithms $D$ that distinguish the required subsets, and prove that for {\em some} of these classes no algorithm for distinguishing can be efficient. The subsets distinguished are also relevant in the study of error correcting codes, and we give an application of our work to bounds for error-correcting codes.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
Discrete logarithm problemcomplexitysparse polynomialquadratic residue codes
Contact author(s)
rpgallant @ swgc mun ca
History
2010-06-28: received
Short URL
https://ia.cr/2010/370
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/370,
      author = {Robert P.  Gallant},
      title = {Finding discrete logarithms with a set orbit distinguisher},
      howpublished = {Cryptology ePrint Archive, Paper 2010/370},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/370}},
      url = {https://eprint.iacr.org/2010/370}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.