International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 10 November 2014

Daniel J. Bernstein, Tanja Lange
ePrint Report ePrint Report
This paper shows, assuming standard heuristics regarding the number-field sieve, that a \"batch NFS\" circuit of area L^{1.181...+o(1)} factors L^{0.5+o(1)} separate B-bit RSA keys in time L^{1.022...+o(1)}. Here L=exp((log 2^B)^{1/3}(log log 2^B)^{2/3}). The circuit\'s area-time product (price-performance ratio) is just L^{1.704...+o(1)} per key. For comparison, the best area-time product known for a single key is L^{1.976...+o(1)}.

This paper also introduces new \"early-abort\" heuristics implying that \"early-abort ECM\" improves the performance of batch NFS by a superpolynomial factor, specifically exp((c+o(1))(log 2^B)^{1/6}(log log 2^B)^{5/6}) where c is a positive constant.

Expand

Additional news items may be found on the IACR news page.