Wykład prof. Józefa Pieprzyka

"How to Strengthen NTRUEncrypt to Chosen-Ciphertext Security in the Standard Model"

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, which limited the confidence in its security. Recently, this situation has changed, when 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. However, for general purpose applications, it is widely accepted that an encryption scheme should satisfy the stronger notion of security under chosen-ciphertext attack (IND-CCA2), and the pNE scheme is insecure in this model. To fill this gap, 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."