CryptoDB
Almost All Discrete Log Bits Are Simultaneously Secure
Authors: |
- Claus P. Schnorr
|
Download: |
- URL: http://eprint.iacr.org/1998/020
- Search ePrint
- Search Google
|
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<sub>\alpha</sub>(x), assuming that the exponentiation function
exp<sub>\alpha</sub>(x) = \alpha<sup>x</sup> 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<sup>-i</sup>x mod q) for i=k+1,...,k+j. When we restrict
exp<sub>\alpha</sub> 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<sup>-j</sup>-<i>fraction</i> of exp<sub>\alpha</sub>.
For groups of odd group order q we show that every two
2<sup>-j</sup>-fractions of exp<sub>\alpha</sub> 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<sub>\alpha</sub>(x) iff the 2<sup>-j</sup>-fractions of
exp<sub>\alpha</sub> 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<sub>\alpha</sub> the individual bits of x
are secure when given exp<sub>\alpha</sub>(x) by the method of Hastad,
Naslund [HN98]. For groups of even order 2<sup>s</sup>q we show that
the j least-significant bits of \lfloor x/2<sup>s</sup>\rfloor, as
well as the j most-significant bits of x/q \in [0,1), are
simultaneously secure iff the 2<sup>-j</sup>-fractions of
exp<sub>\alpha'</sub> are one-way for \alpha' := \alpha<sup>2<sup>s</sup>
</sup>.
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<sub>\alpha</sub> 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<sup>j</sup>/q)<sup>1/4</sup>).
|
BibTeX
@misc{eprint-1998-11316,
title={Almost All Discrete Log Bits Are Simultaneously Secure},
booktitle={IACR Eprint archive},
keywords={Hard bit, secure bit, discrete logarithm, exponentiation, fractions of exponentiation, simultaneous security of bits, one-way function, generic network, generic one-wayness.},
url={http://eprint.iacr.org/1998/020},
note={Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive. schnorr@cs.uni-frankfurt.de. 10500 received June 16th, 1998.},
author={Claus P. Schnorr},
year=1998
}