Cryptology ePrint Archive: Report 1998/020

Almost All Discrete Log Bits Are Simultaneously Secure

Claus P. Schnorr

Abstract: Let G be a finite cyclic group with generator \alpha 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_\alpha(x), assuming that the exponentiation function exp_\alpha(x) = \alpha^x is one-way. We reduce the 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/q \in [0,1) follows from the work of Peralta [P85] and Long and Wigderson [LW88]. We generalize these bits and study the security of consecutive <i> shift bits</i> lsb(2^-ix mod q) for i=k+1,...,k+j. When we restrict exp_\alpha 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^-j-<i>fraction</i> of exp_\alpha.

For groups of odd group order q we show that every two 2^-j-fractions of exp_\alpha are equally one-way by a polynomial time transformation: Either they are all one-way or none of them. Our <i> key theorem</i> shows that arbitrary j consecutive shift bits of x are simultaneously secure when given exp_\alpha(x) iff the 2^-j-fractions of exp_\alpha are one-way. In particular this applies to the j least-significant bits of x and to the j most-significant bits of x/q \in [0,1). For one-way exp_\alpha the individual bits of x are secure when given exp_\alpha(x) by the method of Hastad, Naslund [HN98]. For groups of even order 2^sq we show that the j least-significant bits of \lfloor x/2^s\rfloor, as well as the j most-significant bits of x/q \in [0,1), are simultaneously secure iff the 2^-j-fractions of exp_\alpha' are one-way for \alpha' := \alpha^{2^s}.

We use and extend the models of generic algorithms of Nechaev (1994) and Shoup (1997). We determine the generic complexity of inverting fractions of exp_\alpha for the case that \alpha has prime order q. As a consequence, arbitrary segments of (1-\varepsilon)\lg q consecutive shift bits of random x are for constant \varepsilon >0 simultaneously secure against generic attacks. Every generic algorithm using t generic steps (group operations) for distinguishing bit strings of j consecutive shift bits of x from random bit strings has at most advantage O((\lg q)j\sqrt{t} (2^j/q)^1/4).

Category / Keywords: Hard bit, secure bit, discrete logarithm, exponentiation, fractions of exponentiation, simultaneous security of bits, one-way function, generic network, generic one-wayness.

Publication Info: Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.

Date: received June 16th, 1998.

Contact author: schnorr at cs uni-frankfurt de

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

Short URL: ia.cr/1998/020

Discussion forum: Show discussion | Start new discussion