Batch NFS

D.J. Bernstein; T. Lange

doi:10.1007/978-3-319-13051-4_3

Batch NFS

D.J. Bernstein, T. Lange

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

9 Citaten (Scopus)

Samenvatting

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. Keywords: integer factorization, number-field sieve, price-performance ratio, batching, smooth numbers, elliptic curves, early aborts

Originele taal-2	Engels
Titel	Selected Areas in Cryptography -- SAC 2014: 21st International Conference, Montreal, QC, Canada, August 14-15, 2014, Revised Selected Papers
Redacteuren	A. Joux, A. Youssef
Uitgeverij	Springer
Pagina's	38-58
ISBN van geprinte versie	978-3-319-13050-7
DOI's	https://doi.org/10.1007/978-3-319-13051-4_3
Status	Gepubliceerd - 2014
Evenement	21st International Conference on Selected Areas in Cryptography (SAC 2014) - Sackville, Canada Duur: 14 aug. 2014 → 15 aug. 2014 Congresnummer: 21

Publicatie series

Naam	Lecture Notes in Computer Science
Volume	8781
ISSN van geprinte versie	0302-9743

Congres

Congres	21st International Conference on Selected Areas in Cryptography (SAC 2014)
Verkorte titel	SAC 2014
Land/Regio	Canada
Stad	Sackville
Periode	14/08/14 → 15/08/14
Ander	21st International Conference on Selected Areas in Cryptography

Toegang tot document

10.1007/978-3-319-13051-4_3

https://eprint.iacr.org/2014/921

Citeer dit

@inproceedings{cc7d90ac3ddf46388c0d30bd30fa49fa,

title = "Batch NFS",

abstract = "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. Keywords: integer factorization, number-field sieve, price-performance ratio, batching, smooth numbers, elliptic curves, early aborts",

author = "D.J. Bernstein and T. Lange",

year = "2014",

doi = "10.1007/978-3-319-13051-4_3",

language = "English",

isbn = "978-3-319-13050-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "38--58",

editor = "A. Joux and A. Youssef",

booktitle = "Selected Areas in Cryptography -- SAC 2014: 21st International Conference, Montreal, QC, Canada, August 14-15, 2014, Revised Selected Papers",

address = "Germany",

note = "21st International Conference on Selected Areas in Cryptography (SAC 2014), SAC 2014 ; Conference date: 14-08-2014 Through 15-08-2014",

}

Bernstein, DJ & Lange, T 2014, Batch NFS. in A Joux & A Youssef (uitgave), Selected Areas in Cryptography -- SAC 2014: 21st International Conference, Montreal, QC, Canada, August 14-15, 2014, Revised Selected Papers. Lecture Notes in Computer Science, vol. 8781, Springer, blz. 38-58, 21st International Conference on Selected Areas in Cryptography (SAC 2014), Sackville, New Brunswick, Canada, 14/08/14. https://doi.org/10.1007/978-3-319-13051-4_3

Batch NFS. / Bernstein, D.J.; Lange, T.
Selected Areas in Cryptography -- SAC 2014: 21st International Conference, Montreal, QC, Canada, August 14-15, 2014, Revised Selected Papers. uitgave / A. Joux; A. Youssef. Springer, 2014. blz. 38-58 (Lecture Notes in Computer Science; Vol. 8781).

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

TY - GEN

T1 - Batch NFS

AU - Bernstein, D.J.

AU - Lange, T.

N1 - Conference code: 21

PY - 2014

Y1 - 2014

N2 - 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. Keywords: integer factorization, number-field sieve, price-performance ratio, batching, smooth numbers, elliptic curves, early aborts

AB - 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. Keywords: integer factorization, number-field sieve, price-performance ratio, batching, smooth numbers, elliptic curves, early aborts

U2 - 10.1007/978-3-319-13051-4_3

DO - 10.1007/978-3-319-13051-4_3

M3 - Conference contribution

SN - 978-3-319-13050-7

T3 - Lecture Notes in Computer Science

SP - 38

EP - 58

BT - Selected Areas in Cryptography -- SAC 2014: 21st International Conference, Montreal, QC, Canada, August 14-15, 2014, Revised Selected Papers

A2 - Joux, A.

A2 - Youssef, A.

PB - Springer

T2 - 21st International Conference on Selected Areas in Cryptography (SAC 2014)

Y2 - 14 August 2014 through 15 August 2014

ER -

Batch NFS

Samenvatting

Publicatie series

Congres

Toegang tot document

Vingerafdruk

Citeer dit