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\alpha(x), assuming that the exponentiation function
exp\alpha(x) = \alphax 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-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-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 2sq we show that
the j least-significant bits of \lfloor x/2s\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' := \alpha2s
.
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} (2j/q)1/4).
|
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
}
