Abstract:

Many cryptosystems rely on the hardness of integer factorization, for
which the best algorithm known is the subexponential-time Number Field
Sieve. Exploration of the concrete costs of NFS implementations is thus
of considerable interest. Most research has focused on PC-based
implementations; these have successfully factored 512-bit integers, but
practically cannot scale much further. This talk will present
alternative implementations of the major steps in the NSF algorithm,
based on custom-built hardware devices that achieve considerable
parallelism "for free". These designs feature an interplay between
algorithmic and technological aspects: by devising algorithms that take
advantage of certain tradeoffs in chip manufacturing technology,
efficiency is increased by many orders of magnitude compared to previous
proposals. For example, using the new devices it appears possible to
break a 1024-bit RSA in one year at a cost of a few dozen million
dollars (previous predictions were in the trillions of dollars).


Joint work with Arjen Lenstra, Adi Shamir and Jim Tomlinson.