Finding discrete logarithms with a set orbit distinguisher

Robert P.  Gallant

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)) $, w e c a n f i n d d i s c r e t e l o g a r i t h m s f a s t e r t h a n s q u a r e - r o o t a l g o r i t h m s . W e c o n s i d e r t w o v a r i a t i o n s o n t h i s i d e a a n d g i v e a l g o r i t h m s s o l v i n g t h e d i s c r e t e l o g a r i t h m p r o b l e m i n$ \GG $w i t h c o m p l e x i t y$ {\cal O}(p^{\frac{1}{3}}\log(p)^3 + p^{\frac{1}{3}}c(\log(p) ) $a n d$ {\cal O}(p^{\frac{1}{4}}\log(p)^3 + p^{\frac{1}{4}}c( \log(p) ) $i n t h e b e s t c a s e s . W h e n m u l t i p l e d i s t i n g u i s h e r s a r e a v a i l a b l e l o g a r i t h m s c a n b e f o u n d i n p o l y n o m i a l t i m e . W e d i s c u s s n a t u r a l c l a s s e s o f a l g o r i t h m s$ 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 problem complexity sparse polynomial quadratic residue codes
Contact author(s): rpgallant @ swgc mun ca
History: 2010-06-28: received
Short URL: https://ia.cr/2010/370
License: 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},
      url = {https://eprint.iacr.org/2010/370}
}