NTRUCCA: How to strengthen NTRUEncrypt to chosen-ciphertext security in the standard model

Ron Steinfeld*, San Ling, Josef Pieprzyk, Christophe Tartary, Huaxiong Wang

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review

9 Citations (Scopus)

Abstract

NTRUEncrypt is a fast and practical lattice-based public-key encryption scheme, which has been standardized by IEEE, but until recently, its security analysis relied only on heuristic arguments. Recently, Stehlé and Steinfeld showed that a slight variant (that we call pNE) could be proven to be secure under chosen-plaintext attack (IND-CPA), assuming the hardness of worst-case problems in ideal lattices. We present a variant of pNE called NTRUCCA, that is IND-CCA2 secure in the standard model assuming the hardness of worst-case problems in ideal lattices, and only incurs a constant factor overhead in ciphertext and key length over the pNE scheme. To our knowledge, our result gives the first IND-CCA2 secure variant of NTRUEncrypt in the standard model, based on standard cryptographic assumptions. As an intermediate step, we present a construction for an All-But-One (ABO) lossy trapdoor function from pNE, which may be of independent interest. Our scheme uses the lossy trapdoor function framework of Peikert and Waters, which we generalize to the case of (k - 1)-of-k-correlated input distributions.

Original languageEnglish
Title of host publicationPublic Key Cryptography, PKC 2012 - 15th International Conference on Practice and Theory in Public Key Cryptography, Proceedings
EditorsMarc Fischlin, Johannes Buchmann, Mark Manulis
Place of PublicationHeidelberg
PublisherSpringer, Springer Nature
Pages353-371
Number of pages19
ISBN (Electronic)9783642300578
ISBN (Print)9783642300561
DOIs
Publication statusPublished - 2012
Event15th International Conference on Practice and Theory in Public Key Cryptography, PKC 2012 - Darmstadt, Germany
Duration: 21 May 201223 May 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7293 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other15th International Conference on Practice and Theory in Public Key Cryptography, PKC 2012
CountryGermany
CityDarmstadt
Period21/05/1223/05/12

Fingerprint Dive into the research topics of 'NTRUCCA: How to strengthen NTRUEncrypt to chosen-ciphertext security in the standard model'. Together they form a unique fingerprint.

Cite this