nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

High-Speed Key Encapsulation from NTRU

verfasst von : Andreas Hülsing, Joost Rijneveld, John Schanck, Peter Schwabe

Erschienen in: Cryptographic Hardware and Embedded Systems – CHES 2017

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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, 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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel McBits Revisited

Nächstes Kapitel FPGA-based Key Generator for the Niederreiter Cryptosystem Using Binary Goppa Codes

A centered binomial distribution of parameter t is defined as \(\sum _{i=1}^{t}b_i - b_{t+i}\) where \(b_1, b_2, \dots , b_{2t}\) are uniform random bits.

If \(\mathsf {Sample}{\mathcal T}\) produced the uniform distribution on \({\mathcal T}\), then the attack would apply BKZ with blocksize 470 to the first 1285 columns of Eq. (2).

Note that, as is observed in [3], popular choices for the ring in Ring-LWE schemes typically make it convenient to use the NTT to perform multiplication. As was also the case in [3], however, our ring of choice is particularly unsuitable. In our case this is caused by q being a power of two, and the polynomials being of prime degree.

Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. IACR Cryptology ePrint Archive report 2015/046 (2015). https://eprint.iacr.org/2015/046. 242

Alkim, E., Ducas, L., Pöppelmann, T., Schwabe, P.: Post-quantum key exchange - a new hope. In: Holz, T., Savage, S. (eds.) Proceedings of the 25th USENIX Security Symposium. USENIX Association (2016). https://cryptojedi.org/papers/#newhope. 233, 234, 241, 248

Bernstein, D.J., Chuengsatiansup, C., Lange, T., van Vredendaal, C.: NTRU prime. IACR Cryptology ePrint Archive report 2016/461 (2016). https://eprint.iacr.org/2016/461. 233, 234, 236, 237, 242, 243, 244, 248

Bernstein, D.J., Lange, T.: eBACS: ECRYPT benchmarking of cryptographic systems. http://bench.cr.yp.to. 248

Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: The Keccak reference (2011). http://keccak.noekeon.org/. 236

Boneh, D., Dagdelen, Ö., Fischlin, M., Lehmann, A., Schaffner, C., Zhandry, M.: Random oracles in a quantum world. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 41–69. Springer, Heidelberg (2011). doi:10.1007/978-3-642-25385-0_3. https://eprint.iacr.org/2010/428. 243CrossRef

Bos, J., Costello, C., Ducas, L., Mironov, I., Naehrig, M., Nikolaenko, V., Raghunathan, A., Stebila, D.: Frodo: take off the ring! Practical, quantum-secure key exchange from LWE. In: Kruegel, C., Myers, A., Halevi, S. (eds.) Conference on Computer and Communications Security - CCS 2016, pp. 1006–1018. ACM (2016). https://doi.org/10.1145/2976749.2978425. 233, 248, 249

Bos, J.W., Costello, C., Naehrig, M., Stebila, D.: Post-quantum key exchange for the TLS protocol from the ring learning with errors problem. In: Bauer, L., Shmatikov, V. (eds.) 2015 IEEE Symposium on Security and Privacy, pp. 553–570. IEEE (2015). https://eprint.iacr.org/2014/599. 233, 248

Braithwaite, M.: Experimenting with post-quantum cryptography. Posting on the Google Security Blog (2016). https://security.googleblog.com/2016/07/experimenting-with-post-quantum.html. 233

10.

Chatterjee, S., Koblitz, N., Menezes, A., Sarkar, P.: Another look at tightness ii: practical issues in cryptography. IACR Cryptology ePrint Archive report 2016/360 (2016). https://eprint.iacr.org/2016/360. 234

11.

Chen, Y.: Lattice reduction and concrete security of fully homomorphic encryption. Ph.D. thesis, l’Université Paris Diderot (2013). 242

12.

Chen, Y., Nguyen, P.Q.: BKZ 2.0: better lattice security estimates. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 1–20. Springer, Heidelberg (2011). doi:10.1007/978-3-642-25385-0_1. http://www.iacr.org/archive/asiacrypt2011/70730001/70730001.pdf. 242CrossRef

13.

Cheon, J.H., Han, K., Kim, J., Lee, C., Son, Y.: A practical post-quantum public-key cryptosystem based on spLWE. In: Hong, S., Park, J.H. (eds.) ICISC 2016. LNCS, vol. 10157, pp. 51–74. Springer, Cham (2017). doi:10.1007/978-3-319-53177-9_3. https://eprint.iacr.org/2016/1055. 233, 248, 249CrossRef

14.

Cheon, J.H., Kim, D., Lee, J., Song, Y.: Lizard: cut off the tail! Practical post-quantum public-key encryption from LWE and LWR. IACR Cryptology ePrint Archive report 2016/1126 (2016). https://eprint.iacr.org/2016/1126. 233, 248

15.

Consortium for Efficient Embedded Security. EESS #1: Implementation aspects of NTRUEncrypt and NTRUSign v. 2.0. http://grouper.ieee.org/groups/1363/lattPK/submissions/EESS1v2.pdf. 236

16.

Cramer, R., Shoup, V.: Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack. SIAM J. Comput. 33(1), 167–226 (2003). http://www.shoup.net/papers/cca2.pdf. 233MathSciNetCrossRefMATH

17.

del Pino, R., Lyubashevsky, V., Pointcheval, D.: The whole is less than the sum of its parts: constructing more efficient lattice-based AKEs. In: Zikas, V., De Prisco, R. (eds.) SCN 2016. LNCS, vol. 9841, pp. 273–291. Springer, Cham (2016). doi:10.1007/978-3-319-44618-9_15. https://eprint.iacr.org/2016/435. 233, 236, 242

18.

Dent, A.W.: A designer’s guide to KEMs. In: Paterson, K.G. (ed.) Cryptography and Coding 2003. LNCS, vol. 2898, pp. 133–151. Springer, Heidelberg (2003). doi:10.1007/978-3-540-40974-8_12. http://www.cogentcryptography.com/papers/designer.pdf. 233, 238, 243CrossRef

19.

Fujisaki, E., Okamoto, T.: Secure integration of asymmetric and symmetric encryption schemes. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 537–554. Springer, Heidelberg (1999). doi:10.1007/3-540-48405-1_34. 243

20.

Hirschhorn, P.S., Hoffstein, J., Howgrave-Graham, N., Whyte, W.: Choosing NTRUEncrypt parameters in light of combined lattice reduction and MITM approaches. In: Abdalla, M., Pointcheval, D., Fouque, P.-A., Vergnaud, D. (eds.) ACNS 2009. LNCS, vol. 5536, pp. 437–455. Springer, Heidelberg (2009). doi:10.1007/978-3-642-01957-9_27. https://eprint.iacr.org/2005/045. 236CrossRef

21.

Hoffstein, J., Pipher, J., Schanck, J.M., Silverman, J.H., Whyte, W., Zhang, Z.: Choosing parameters for NTRUEncrypt. In: Handschuh, H. (ed.) CT-RSA 2017. LNCS, vol. 10159, pp. 3–18. Springer, Cham (2017). doi:10.1007/978-3-319-52153-4_1. https://eprint.iacr.org/2015/708. 236, 241, 242, 248CrossRef

22.

Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: a new high speed public key cryptosystem (1996). Draft from at CRYPTO 1996 rump session. http://web.securityinnovation.com/hubfs/files/ntru-orig.pdf. 237

23.

Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: a ring-based public key cryptosystem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 267–288. Springer, Heidelberg (1998). doi:10.1007/BFb0054868. 233, 236, 237, 238CrossRef

24.

Hoffstein, J., Pipher, J., Silverman, J.H.: Public key cryptosystem method and apparatus. United States Patent 6081597 (2000). Application filed 19 August 1997. http://www.freepatentsonline.com/6081597.html. 234

25.

Hoffstein, J., Silverman, J.H.: Speed enhanced cryptographic method and apparatus. United States Patent 7031468 (2006). Application filed 24 August 2001. http://www.freepatentsonline.com/7031468.html. 234

26.

Howgrave-Graham, N.: A hybrid lattice-reduction and meet-in-the-middle attack against NTRU. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 150–169. Springer, Heidelberg (2007). doi:10.1007/978-3-540-74143-5_9. http://www.iacr.org/archive/crypto2007/46220150/46220150.pdf. 241, 242CrossRef

27.

Howgrave-Graham, N., Silverman, J.H., Singer, A., Whyte, W.: NAEP: provable security in the presence of decryption failures. Cryptology ePrint Archive, Report 2003/172 (2003). https://eprint.iacr.org/2003/172. 233

28.

Howgrave-Graham, N., Silverman, J.H., Whyte, W.: Choosing parameter sets for NTRUEncrypt with NAEP and SVES-3. In: Menezes, A. (ed.) CT-RSA 2005. LNCS, vol. 3376, pp. 118–135. Springer, Heidelberg (2005). doi:10.1007/978-3-540-30574-3_10. https://eprint.iacr.org/2005/045. 236CrossRef

29.

Itoh, T., Tsujii, S.: A fast algorithm for computing multiplicative inverses in \({GF}({2^m})\) using normal bases. Inf. Comput. 78(3), 171–177 (1988). https://sciencedirect.com/science/article/pii/0890540188900247. 246MathSciNetCrossRefMATH

30.

Kirchner, P., Fouque, P.-A.: Comparison between subfield and straightforward attacks on NTRU. IACR Cryptology ePrint Archive report 2012/387 (2016). https://eprint.iacr.org/2016/717. 234

31.

Krawczyk, H., Paterson, K.G., Wee, H.: On the security of the TLS protocol: a systematic analysis. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 429–448. Springer, Heidelberg (2013). doi:10.1007/978-3-642-40041-4_24. eprint.iacr.org/2013/339. 233CrossRef

32.

Laarhoven, T.: Search problems in cryptography. Ph.D. thesis, Eindhoven University of Technology (2015). http://www.thijs.com/docs/phd-final.pdf. 241

33.

Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 1–23. Springer, Heidelberg (2010). doi:10.1007/978-3-642-13190-5_1. http://www.di.ens.fr/~lyubash/papers/ringLWE.pdf. 234CrossRef

34.

NIST. Post-quantum crypto project (2016). http://csrc.nist.gov/groups/ST/post-quantum-crypto/. 232

35.

Saarinen, M.-J.O.: Ring-LWE ciphertext compression and error correction: tools for lightweight post-quantum cryptography. IACR Cryptology ePrint Archive report 2016/461 (2016). https://eprint.iacr.org/2016/1058. 233

36.

Sakshaugh, H.: Security analysis of the NTRUEncrypt public key encryption scheme. Master’s thesis, Norwegian University of Science and Technology (2007). https://brage.bibsys.no/xmlui/handle/11250/258846. 233, 243

37.

Schroeppel, R., Orman, H., O’Malley, S., Spatscheck, O.: Fast key exchange with elliptic curve systems. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 43–56. Springer, Heidelberg (1995). doi:10.1007/3-540-44750-4_4. https://pdfs.semanticscholar.org/edc9/5e3d34f42deabe82ff3e9237266e30adc1a7.pdf. 247

38.

Security Innovation. Security Innovation makes NTRUEncrypt patent-free (2017). https://www.securityinnovation.com/company/news-and-events/press-releases/security-innovation-makes-ntruencrypt-patent-free. 234

39.

Silverman, J.H.: Almost inverses and fast NTRU key creation. Technical report #014, NTRU Cryptosystems (1999). Version 1. https://assets.onboardsecurity.com/static/downloads/NTRU/resources/NTRUTech014.pdf. 246, 247

40.

Stam, M.: A key encapsulation mechanism for NTRU. In: Smart, N.P. (ed.) Cryptography and Coding 2005. LNCS, vol. 3796, pp. 410–427. Springer, Heidelberg (2005). doi:10.1007/11586821_27. 233, 243CrossRef

41.

Targhi, E.E., Unruh, D.: Quantum security of the Fujisaki-Okamoto and OAEP transforms. Cryptology ePrint Archive, Report 2015/1210 (2015). https://eprint.iacr.org/2015/1210. 243

Titel: High-Speed Key Encapsulation from NTRU
verfasst von: Andreas Hülsing
Joost Rijneveld
John Schanck
Peter Schwabe
Verlag: Springer International Publishing
Buch: Cryptographic Hardware and Embedded Systems – CHES 2017
Print ISBN: 978-3-319-66786-7

Electronic ISBN: 978-3-319-66787-4

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-66787-4_12

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner