## CryptoDB

### Don Coppersmith

#### Publications

Year
Venue
Title
2008
JOFC
2004
EPRINT
Let $r,s,n$ be integers satisfying $0 \leq r < s < n$, $s \geq n^{\alpha}$, $\alpha > 1/4$, and $\gcd(r,s)=1$. Lenstra showed that the number of integer divisors of $n$ equivalent to $r \pmod s$ is upper bounded by $O((\alpha-1/4)^{-2})$. We re-examine this problem; showing how to explicitly construct all such divisors and incidentally improve this bound to $O((\alpha-1/4)^{-3/2})$.
2002
CRYPTO
2002
FSE
2002
EPRINT
We report on the design of Scream, a new software-efficient stream cipher, which was designed to be a more secure SEAL''. Following SEAL, the design of Scream resembles in many ways a block-cipher design. The new cipher is roughly as fast as SEAL, but we believe that it offers a significantly higher security level. In the process of designing this cipher, we re-visit the SEAL design paradigm, exhibiting some tradeoffs and limitations.
2002
EPRINT
We describe a cryptanalytical technique for distinguishing some stream ciphers from a truly random process. Roughly, the ciphers to which this method applies consist of a non-linear process'' (say, akin to a round function in block ciphers), and a linear process'' such as an LFSR (or even fixed tables). The output of the cipher can be the linear sum of both processes. To attack such ciphers, we look for any property of the non-linear process'' that can be distinguished from random. In addition, we look for a linear combination of the linear process that vanishes. We then consider the same linear combination applied to the cipher's output, and try to find traces of the distinguishing property. In this report we analyze two specific distinguishing properties''. One is a linear approximation of the non-linear process, which we demonstrate on the stream cipher SNOW. This attack needs roughly $2^{95}$ words of output, with work-load of about $2^{100}$. The other is a low-diffusion'' attack, that we apply to the cipher Scream-0. The latter attack needs only about $2^{43}$ bytes of output, using roughly $2^{50}$ space and $2^{80}$ time.
2002
EPRINT
We introduce a novel technique for computation of consecutive preimages of hash chains. Whereas traditional techniques have a memory-times-computation complexity of $O(n)$ per output generated, the complexity of our technique is only $O(log^2 \, n)$, where $n$ is the length of the chain. Our solution is based on the same principal amortization principle as \cite{J01}, and has the same asymptotic behavior as this solution. However, our solution decreases the real complexity by approximately a factor of two. Thus, the computational costs of our solution are approximately ${1 \over 2} log_2 \, n$ hash function applications, using only a little more than $log_2 \, n$ storage cells. A result of independent interest is the lower bounds we provide for the optimal (but to us unknown) solution to the problem we study. The bounds show that our proposed solution is very close to optimal. In particular, we show that there exists no improvement on our scheme that reduces the complexity by more than an approximate factor of two.
2001
JOFC
2000
CRYPTO
2000
JOFC
2000
CRYPTO
1999
CRYPTO
1998
EUROCRYPT
1998
FSE
1998
JOFC
1997
EUROCRYPT
1997
JOFC
1997
JOFC
1996
EUROCRYPT
1996
EUROCRYPT
1996
EUROCRYPT
1994
CRYPTO
1993
CRYPTO
1993
CRYPTO
1993
FSE
1993
JOFC
1985
CRYPTO
1985
CRYPTO
1985
CRYPTO

#### Program Committees

FSE 2005
Eurocrypt 2005
Asiacrypt 2004
FSE 2004
Eurocrypt 2003
Crypto 2003
FSE 2002
Eurocrypt 2002
Crypto 2002
FSE 2000
Eurocrypt 2000
FSE 1999
Crypto 1999
Eurocrypt 1999
Crypto 1998
FSE 1998
FSE 1997
FSE 1996
Crypto 1996
Crypto 1995 (Program chair)
Crypto 1994