Lenstra, Shamir, Tomlinson, & Tromer on Bernstein

[Trei, Peter]

http://www.cryptosavvy.com/mesh.pdf

Analysis of Bernstein's Factorization Circuit
Arjen K. Lenstra 1 , Adi Shamir 2 , Jim Tomlinson 3 , Eran Tromer 2

Abstract. In [1], Bernstein proposed a circuit-based implementation of
the matrix step of the number field sieve factorization algorithm. We
show that under the non-standard cost function used in [1], these cir-cuits
indeed offer an asymptotic improvement over other methods but
to a lesser degree than previously claimed: for a given cost, the new
method can factor integers that are 1.17 times larger (rather than 3.01).
We also propose an improved circuit design based on a new mesh rout-ing
algorithm, and show that for factorization of 1024-bit integers the
matrix step can, under an optimistic assumption about the matrix size,
be completed within a day by a device that costs a few thousand dollars.
We conclude that from a practical standpoint, the security of RSA relies
exclusively on the hardness of the relation collection step of the number
field sieve.

Keywords: factorization, number field sieve, RSA, mesh routing

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com