## CryptoDB

### Don Coppersmith

#### Publications

**Year**

**Venue**

**Title**

2004

EPRINT

Divisors in Residue Classes, Constructively
Abstract

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

EPRINT

Scream: a software-efficient stream cipher
Abstract

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

Cryptanalysis of stream ciphers with linear masking
Abstract

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

Almost Optimal Hash Sequence Traversal
Abstract

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.

#### 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

#### Coauthors

- Jean-Sébastien Coron (1)
- Matthew K. Franklin (1)
- François Grieu (1)
- Shai Halevi (5)
- Nick Howgrave-Graham (1)
- Markus Jakobsson (1)
- Charanjit S. Jutla (5)
- John Kelsey (1)
- Lars R. Knudsen (1)
- Hugo Krawczyk (1)
- Yishay Mansour (1)
- Chris J. Mitchell (1)
- David Naccache (1)
- S. V. Nagaraj (1)
- Jacques Patarin (1)
- Michael K. Reiter (1)
- Phillip Rogaway (2)
- Bruce Schneier (1)
- Adi Shamir (1)
- Igor E. Shparlinski (1)
- Julien P. Stern (1)
- Jacques Stern (2)
- Serge Vaudenay (2)
- David Wagner (1)