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 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 \frac{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 \frac{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, N\"aslund [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 \frac{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)^{\frac14}).