Security of Allmost ALL Discrete Log Bits
Claus-Peter Schnorr · Electronic colloquium on computational complexity · 1998
Let G be a finite cyclic group with generator fi and with an encoding so that multiplication is computable in polynomial time. We study the security of bits of the discrete log x when given exp fi (x), assuming that the exponentiation function exp fi (x) = fi x is oneway. We reduce he general problem to the case that G has odd order q. If G has odd order q the security of the least-significant bits of x and of the most significant bits of the rational number x 2 [0,1) follows from the work of Peralta [P85] and Long and Wigderson [LW88]. We generalize these bits and study the security of consecutive shift bits lsb(2 ii x mod q) for i = k + 1,...,k + j. When we restrict exp fi to arguments x such that some sequence of j consecutive shift bits of x is constant (i.e., not depending on x) we call it a 2 ij -fraction of exp fi . For groups of odd group order q we show that every two 2 ij -fractions of exp fi are equally one-way by a polynomial time transformation: Either they are all one-way or none of them. Our key theorem shows that arbitrary j consecutive shift bits of x are simultaneously secure when given expfi(x) i the 2 ij -fractions of expfi are one-way. In particular this applies to the j least-significant bits of x and to the j most-significant bits of x 2 [0,1).