High-Speed Key Encapsulation from NTRU
This paper presents software demonstrating that the 20-year-old NTRU cryptosystem is competitive with more recent lattice-based cryptosystems in terms of speed, key size, and ciphertext size. We present a slightly simplified version of textbook NTRU, sele
- PDF / 423,645 Bytes
- 21 Pages / 439.37 x 666.142 pts Page_size
- 111 Downloads / 211 Views
3
Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, Eindhoven, The Netherlands [email protected] 2 Digital Security Group, Radboud University, Nijmegen, The Netherlands [email protected], [email protected] Institute for Quantum Computing, University of Waterloo, Waterloo, Canada 4 Security Innovation, Wilmington, MA, USA [email protected]
Abstract. This paper presents software demonstrating that the 20year-old NTRU cryptosystem is competitive with more recent latticebased cryptosystems in terms of speed, key size, and ciphertext size. We present a slightly simplified version of textbook NTRU, select parameters for this encryption scheme that target the 128-bit post-quantum security level, construct a KEM that is CCA2-secure in the quantum random oracle model, and present highly optimized software targeting Intel CPUs with the AVX2 vector instruction set. This software takes only 307 914 cycles for the generation of a keypair, 48 646 for encapsulation, and 67 338 for decapsulation. It is, to the best of our knowledge, the first NTRU software with full protection against timing attacks. Keywords: Post-quantum crypto · Lattice-based crypto CCA2-secure KEM · QROM · AVX2
1
·
NTRU
·
Introduction
In December 2016, NIST issued a call for proposals for “post-quantum cryptography” [34] to select schemes for standardization. More specifically, NIST requests algorithms in three categories: public-key encryption, key exchange or key encapsulation mechanisms (KEMs), and digital signatures. Obviously, the central requirement is that proposed schemes are indeed “post-quantum”, i.e., that they resist attacks by a large quantum computer. This work has been supported by the European Commission through the ICT program under contract ICT-645622 (PQCRYPTO), and by the Netherlands Organisation for Scientific Research (NWO) through Veni 2013 project 13114. This work has also been supported by Canada’s NSERC CREATE program. The Institute for Quantum Computing is supported in part by the Government of Canada and the Province of Ontario. Permanent ID of this document: 65dcfe39848495fe9b2423ac0a563d43. Date: June 26, 2017. c International Association for Cryptologic Research 2017 W. Fischer and N. Homma (Eds.): CHES 2017, LNCS 10529, pp. 232–252, 2017. DOI: 10.1007/978-3-319-66787-4 12
High-Speed Key Encapsulation from NTRU
233
For encryption and key encapsulation, it seems that the most promising approach in terms of speed, key size, and ciphertext size is lattice-based cryptography. It is no coincidence that Google chose a lattice-based scheme, more specifically the Newhope Ring-LWE-based key exchange [2], for their post-quantum TLS experiment [9]. It is also not surprising that various recent papers propose constructions and parameters, often together with implementations, for latticebased encryption schemes and KEMs. See, for example, [2,3,7,8,13,14,17,35]. These schemes differ in terms of security notions (e.g., passive vs. active security), underlying hard problems (e.g., learning
Data Loading...
