## CryptoDB

### Arjen K. Lenstra

#### Publications

Year
Venue
Title
2017
EUROCRYPT
2015
EPRINT
2015
EPRINT
2014
EPRINT
2014
ASIACRYPT
2014
CHES
2012
CRYPTO
2010
EPRINT
This paper reports on the factorization of the 768-bit number RSA-768 by the number field sieve factoring method and discusses some implications for RSA.
2010
EPRINT
This paper describes our implementation of phase one of the elliptic curve method on the Cell processor and reports on actual record factors obtained. Our implementation uses a new and particularly efficient variable radix multiplication of independent interest.
2010
CRYPTO
2009
PKC
2009
CRYPTO
2007
ASIACRYPT
2007
EUROCRYPT
2007
EPRINT
We describe how we reached a new factoring milestone by completing the first special number field sieve factorization of a number having more than 1024 bits, namely the Mersenne number $2^{1039}-1$. Although this factorization is orders of magnitude `easier' than a factorization of a 1024-bit RSA modulus is believed to be, the methods we used to obtain our result shed new light on the feasibility of the latter computation.
2006
EUROCRYPT
2006
EPRINT
We have shown how, at a cost of about $2^{52}$ calls to the MD5 compression function, for any two target messages $m_1$ and $m_2$, values $b_1$ and $b_2$ can be constructed such that the concatenated values $m_1\|b_1$ and $m_2\|b_2$ collide under MD5. Although the practical attack potential of this construction of \emph{target collisions} is limited, it is of greater concern than random collisions for MD5. In this note we sketch our construction. To illustrate its practicality, we present two MD5 based X.509 certificates with identical signatures but different public keys \emph{and} different Distinguished Name fields, whereas our previous construction of colliding X.509 certificates required identical name fields. We speculate on other possibilities for abusing target collisions.
2005
EPRINT
We announce the construction of a pair of valid X.509 certificates with identical signatures.
2005
EPRINT
We introduce VSH, {\em very smooth hash}, a new $S$-bit hash function that is provably collision-resistant assuming the hardness of finding nontrivial modular square roots of very smooth numbers modulo an $S$-bit composite. By very smooth, we mean that the smoothness bound is some fixed polynomial function of~$S$. We argue that finding collisions for VSH has the same asymptotic complexity as factoring using the Number Field Sieve factoring algorithm, i.e., subexponential in~$S$. %We show how our asymptotic argument can be turned into a practical method to %select parameters so that VSH meets a desired security level. VSH is theoretically pleasing because it requires just a single multiplication modulo the~$S$-bit composite per $\Omega(S)$ message-bits (as opposed to $O(\log S)$ message-bits for previous provably secure hashes). It is relatively practical. A preliminary implementation on a 1GHz Pentium III processor that achieves collision resistance at least equivalent to the difficulty of factoring a 1024-bit RSA modulus, runs at 1.1 MegaByte per second, with a moderate slowdown to 0.7MB/s for 2048-bit RSA security. VSH can be used to build a fast, provably secure randomised trapdoor hash function, which can be applied to speed up provably secure signature schemes (such as Cramer-Shoup) and designated-verifier signatures.
2005
EPRINT
We introduce {\em Twin RSA}, pairs of RSA moduli $(n,n+2)$, and formulate several questions related to it. Our main questions are: is Twin RSA secure, and what is it good for?
2004
JOFC
2003
ASIACRYPT
2002
ASIACRYPT
2002
CHES
2002
PKC
2001
ASIACRYPT
2001
ASIACRYPT
2001
PKC
2001
PKC
2001
JOFC
2000
ASIACRYPT
2000
CRYPTO
2000
EUROCRYPT
2000
EUROCRYPT
2000
PKC
1999
ASIACRYPT
1999
JOFC
1998
ASIACRYPT
1996
ASIACRYPT
1996
ASIACRYPT
1995
CRYPTO
1995
CRYPTO
1995
CRYPTO
1994
ASIACRYPT
1993
CRYPTO
1993
EUROCRYPT
1993
JOFC
1992
EUROCRYPT
1992
EUROCRYPT
1990
EUROCRYPT
1989
EUROCRYPT

Asiacrypt 2015
Eurocrypt 2013
Asiacrypt 2012
Eurocrypt 2012
Crypto 2011
Asiacrypt 2011
Eurocrypt 2010
Asiacrypt 2009
Asiacrypt 2008
CHES 2008
Eurocrypt 2008
PKC 2007
Asiacrypt 2007
Asiacrypt 2006
Crypto 2006
Eurocrypt 2006
Crypto 2005
Eurocrypt 2005
Asiacrypt 2005
Asiacrypt 2004
PKC 2004
Eurocrypt 2004
PKC 2003
Asiacrypt 2003
Eurocrypt 2002
Asiacrypt 2002
PKC 2001
Eurocrypt 2001
Asiacrypt 2001
CHES 2000
PKC 2000
Crypto 2000
PKC 1999
Crypto 1999
PKC 1998
Eurocrypt 1998
Eurocrypt 1996
Eurocrypt 1991