Estimate all the {LWE, NTRU} schemes!

Martin R.  Albrecht; Benjamin R.  Curtis; Amit Deo; Alex Davidson; Rachel Player; Eamonn W.  Postlethwaite; Fernando Virdia; Thomas Wunderer

Paper 2018/331

Estimate all the {LWE, NTRU} schemes!

Martin R. Albrecht, Benjamin R. Curtis, Amit Deo, Alex Davidson, Rachel Player, Eamonn W. Postlethwaite, Fernando Virdia, and Thomas Wunderer

Abstract

We consider all LWE- and NTRU-based encryption, key encapsulation, and digital signature schemes proposed for standardisation as part of the Post-Quantum Cryptography process run by the US National Institute of Standards and Technology (NIST). In particular, we investigate the impact that different estimates for the asymptotic runtime of (block-wise) lattice reduction have on the predicted security of these schemes. Relying on the ``LWE estimator'' of Albrecht et al., we estimate the cost of running primal and dual lattice attacks against every LWE-based scheme, using every cost model proposed as part of a submission. Furthermore, we estimate the security of the proposed NTRU-based schemes against the primal attack under all cost models for lattice reduction.

Note: Uploading latest version

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Minor revision. Conference on Security and Cryptography for Networks (SCN'18)
Keywords: post-quantum cryptography public-key cryptography cryptanalysis learning with errors NTRU NIST
Contact author(s): benjamin curtis 2015 @ rhul ac uk
History: 2018-12-03: revised; 2018-04-10: received; See all versions
Short URL: https://ia.cr/2018/331
License: CC BY

BibTeX

@misc{cryptoeprint:2018/331,
      author = {Martin R.  Albrecht and Benjamin R.  Curtis and Amit Deo and Alex Davidson and Rachel Player and Eamonn W.  Postlethwaite and Fernando Virdia and Thomas Wunderer},
      title = {Estimate all the {{LWE}, {NTRU}} schemes!},
      howpublished = {Cryptology {ePrint} Archive, Paper 2018/331},
      year = {2018},
      url = {https://eprint.iacr.org/2018/331}
}