International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Claus-Peter Schnorr

Publications

Year
Venue
Title
2001
PKC
2000
ASIACRYPT
2000
JOFC
1998
EPRINT
Almost All Discrete Log Bits Are Simultaneously Secure
Claus P. Schnorr
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>).
1998
JOFC
1997
EUROCRYPT
1996
CRYPTO
1995
EUROCRYPT
1994
EUROCRYPT
1993
FSE
Parallel FFT-Hashing
Claus-Peter Schnorr Serge Vaudenay
1992
EUROCRYPT
1992
EUROCRYPT
1991
EUROCRYPT
1991
JOFC
1991
JOFC
1990
EUROCRYPT
1989
CRYPTO
1989
EUROCRYPT
1988
CRYPTO
1988
EUROCRYPT
1984
CRYPTO
1984
EUROCRYPT
1983
CRYPTO
1982
EUROCRYPT
Is the RSA Scheme Safe?
Claus-Peter Schnorr
1982
EUROCRYPT

Program Committees

PKC 2005
PKC 2004
PKC 2001
Eurocrypt 2001
Eurocrypt 1999
Eurocrypt 1997
Eurocrypt 1996
Eurocrypt 1993
Eurocrypt 1991
Eurocrypt 1987
Crypto 1986
Eurocrypt 1984