International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Michael J. Wiener

Publications

Year
Venue
Title
2005
EPRINT
Bounds on Birthday Attack Times
Michael J. Wiener
We analyze a generic birthday attack where distinct inputs to some function $f$ are selected until two of the inputs map through $f$ to the same output, meaning that the attack has succeeded. We give tight bounds on the probability of attack success after a given number of inputs are selected as well as tight bounds on the expected number of inputs that must be selected for the attack to succeed. The types of functions considered include random functions with uniformly random outputs, random functions whose outputs have some arbitrary (biased) probability distribution, concrete functions that are balanced (all outputs have the same number of pre-images), and arbitrary concrete functions. In each case the bounds are given in terms of the probability ($1/\beta$) that a pair of inputs give the same output, which is different for each type of function. The expected number of steps required to complete a birthday attack in all cases is between $0.7\sqrt{\beta}$ and $2\sqrt{\beta}$. In some cases tighter bounds than this are given. Compared to previous work in this area, the analysis here gives tighter bounds and is more applicable to the most efficient practical methods used to carry out birthday attacks, such as a generalization of Pollard's rho-method and parallel collision search. However, significant challenges remain in proving bounds for these methods.
2004
JOFC
2003
EPRINT
Safe Prime Generation with a Combined Sieve
Michael J. Wiener
A number $p$ is a safe prime if both $p$ and $(p-1)/2$ are prime. This note describes a method of generating safe primes that is considerably faster than repeatedly generating random primes $q$ until $p=2q+1$ is also prime.
1999
JOFC
1996
CRYPTO
1996
EUROCRYPT
1992
CRYPTO
1990
EUROCRYPT
1989
EUROCRYPT
1988
CRYPTO

Program Committees

CHES 2009
Eurocrypt 2006
Crypto 2003
PKC 2003
CHES 2001
CHES 2000
Crypto 1999 (Program chair)
CHES 1999
Crypto 1997