Welcome to the resource topic for
**1998/020**

**Title:**

Almost All Discrete Log Bits Are Simultaneously Secure

**Authors:**
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 * shift bits*

lsb(2^{-i}x 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}-*fraction* 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 * key theorem* 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^{s}q 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^{2s
}.

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}).

**ePrint:**
https://eprint.iacr.org/1998/020

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .