logo

SCIENCE CHINA Information Sciences, Volume 63 , Issue 8 : 182101(2020) https://doi.org/10.1007/s11432-019-9861-3

Improved lattice-based CCA2-secure PKE in the standard model

More info
  • ReceivedFeb 12, 2019
  • AcceptedApr 4, 2019
  • PublishedJul 7, 2020

Abstract

Based on the identity-based encryption (IBE) from lattices by Agrawal et al. (Eurocrypt'10),Micciancio and Peikert (Eurocrypt'12) presented a CCA1-secure public-key encryption (PKE), which has the best known efficiency in the standard modeland can be used to obtain a CCA2-secure PKEfrom lattices by using the generic BCHK transform (SIAM J Comput, 2006)with a cost of introducing extra overheads to both computation and storage for the use of other primitivessuch as signatures and commitments.In this paper, we propose a more efficient standard model CCA2-secure PKE from latticesby carefully combining a different message encoding (which encodes the message into the most significant bits of the LWE's “secret term”) with several nice algebraic properties of the tag-based lattice trapdoor and the LWE problem (such asunique witness and additive homomorphism).Compared to the best known lattice-based CCA1-secure PKE in the standard model due to Micciancio and Peikert (Eurocrypt'12), wenot only directly achieve the CCA2-security without using any generic transform (and thus do not use signatures or commitments), butalso reduce the noise parameter roughly by a factor of 3.This improvement makes our CCA2-secure PKE more efficient in terms of bothcomputation and storage. In particular,when encrypting a 256-bit (respectively, 512-bit) message at 128-bit (respectively, 256-bit) security,the ciphertext size of our CCA2-secure PKE is even 33%–44% (respectively, 36%–46%) smaller than that of their CCA1-secure PKE.


Acknowledgment

Jiang ZHANG is supported by National Key Research and Development Program of China (Grant Nos. 2017YFB0802005, 2018YFB0804105), National Natural Science Foundation of China (Grant No. 61602046), Young Elite Scientists Sponsorship Program by CAST (Grant No. 2016QNRC001), and Opening Project of Guangdong Provincial Key Laboratory of Data Security and Privacy Protection (Grant No. 2017B030301004). Yu YU is supported by National Natural Science Foundation of China (Grant Nos. 61872236, 61572192), National Cryptography Development Fund (Grant No. MMJJ20170209), and Anhui Initiative in Quantum Information Technologies (Grant No. AHY150100). Shuqin FAN is supported by National Key Research and Development Program of China (Grant No. 2017YFB0802005). Zhenfeng ZHANG is supported by National Key Research and Development Program of China (Grant No. 2017YFB0802005) and National Natural Science Foundation of China (Grant No. U1536205).


References

[1] Diffie W, Hellman M. New directions in cryptography. IEEE Trans Inform Theor, 1976, 22: 644-654 CrossRef Google Scholar

[2] Rivest R L, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems. Commun ACM, 1978, 21: 120-126 CrossRef Google Scholar

[3] Goldwasser S, Micali S. Probabilistic encryption. J Comput Syst Sci, 1984, 28: 270-299 CrossRef Google Scholar

[4] Naor M, Yung M. Public-key cryptosystems provably secure against chosen ciphertext attacks. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, Baltimore, 1990. 427--437. Google Scholar

[5] Rackoff C, Simon D R. Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack. In: Advances in Cryptology--CRYPTO '91. Berlin: Springer, 1992. 433--444. Google Scholar

[6] NIST. Post-quantum cryptography standardization. 2016. http://csrc.nist.gov/groups/ST/post-quantum-crypto/submission-requirements/index.html. Google Scholar

[7] Fujisaki E, Okamoto T. Secure Integration of Asymmetric and Symmetric Encryption Schemes. J Cryptol, 2013, 26: 80-101 CrossRef Google Scholar

[8] Pointcheval D. Chosen-ciphertext security for any one-way cryptosystem. In: Public Key Cryptography. Berlin: Springer, 2000. 129--146. Google Scholar

[9] Targhi E E, Unruh D. Post-quantum security of the Fujisaki-Okamoto and OAEP transforms. In: Theory of Cryptography. Berlin: Springer, 2016. 192--216. Google Scholar

[10] Canetti R, Goldreich O, Halevi S. The random oracle methodology, revisited. J ACM, 2004, 51: 557-594 CrossRef Google Scholar

[11] Gertner Y, Malkin T, Myers S. Towards a separation of semantic and CCA security for public key encryption. In: Theory of Cryptography. Berlin: Springer, 2007. 434--455. Google Scholar

[12] Sahai A. Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security. In: Proceedings of the 40th Annual Symposium on Foundations of Computer Science, New York City, 1999. 543--553. Google Scholar

[13] Dolev D, Dwork C, Naor M. Nonmalleable Cryptography. SIAM J Comput, 2000, 30: 391-437 CrossRef Google Scholar

[14] Cramer R, Shoup V. Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack. SIAM J Comput, 2001, 33: 167--226. Google Scholar

[15] Wee H. Efficient chosen-ciphertext security via extractable hash proofs. In: Proceedings of the 30th Annual Conference on Advances in Cryptology. Berlin: Springer, 2010. 314--332. Google Scholar

[16] Boneh D, Canetti R, Halevi S, et al. Chosen-ciphertext security from identity-based encryption. SIAM J Comput, 2006, 36(5): 1301--1328. Google Scholar

[17] Kiltz E. Chosen-ciphertext security from tag-based encryption. In: Theory of Cryptography. Berlin: Springer, 2006. 581--600. Google Scholar

[18] Peikert C, Waters B. Lossy trapdoor functions and their applications. In: STOC 2008. ACM, 2008. 187--196. Google Scholar

[19] Rosen A, Segev G. Chosen-ciphertext security via correlated products. In: Theory of Cryptography. Berlin: Springer, 2009. 419--436. Google Scholar

[20] Kiltz E, Mohassel P, O'Neill A. Adaptive trapdoor functions and chosen-ciphertext security. In: Advances in Cryptology--EUROCRYPT 2010. Berlin: Springer, 2010. 673--692. Google Scholar

[21] Shor P W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J Comput, 1997, 26: 1484-1509 CrossRef Google Scholar

[22] Cramer R, Shoup V. A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In: Advances in Cryptology--CRYPTO '98. Berlin: Springer, 1998. 13--25. Google Scholar

[23] Katz J, Vaikuntanathan V. Smooth projective hashing and password-based authenticated key exchange from lattices. In: Advances in Cryptology--ASIACRYPT 2009. Berlin: Springer, 2009. 636--652. Google Scholar

[24] Peikert C, Vaikuntanathan V, Waters B. A framework for efficient and composable oblivious transfer. In: Advances in Cryptology--CRYPTO 2008. Berlin: Springer, 2008. 554--571. Google Scholar

[25] Benhamouda F, Blazy O, Ducas L, et al. Hash proof systems over lattices revisited. In: Public-Key Cryptography--PKC 2018. Berlin: Springer, 644--674. Google Scholar

[26] Han G, Li H, Qin B D. Chameleon all-but-one extractable hash proof and its applications. Sci China Inf Sci, 2018, 61: 099103 CrossRef Google Scholar

[27] Zhang J, Yu Y. Two-round pake from approximate SPH and instantiations from lattices. In: Advances in Cryptology--ASIACRYPT 2017. Berlin: Springer, 2017. 37--67. Google Scholar

[28] Kim S, Wu D J. Multi-theorem preprocessing NIZKs from lattices. In: Advances in Cryptology--CRYPTO 2018. Berlin: Springer, 2018. 733--765. Google Scholar

[29] Peikert C. Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In: Proceedings of the Annual ACM Symposium on Theory of Computing, Bethesda, 2009. 333--342. Google Scholar

[30] Wee H. Public key encryption against related key attacks. In: Public Key Cryptography--PKC 2012. Berlin: Springer, 2012. 262--279. Google Scholar

[31] Steinfeld R, Ling S, Pieprzyk J, et al. NTRUCCA: How to strengthen ntruencrypt to chosen-ciphertext security in the standard model. In: Public Key Cryptography--PKC 2012. Berlin: Springer, 2012. 353--371. Google Scholar

[32] Dowsley R, Hanaoka G, Imai H, et al. Reducing the ciphertext size of Dolev-Dwork-Naor like public key cryptosystems. Cryptology ePrint Archive, Report 2009/271, 2009. Google Scholar

[33] Agrawal S, Boneh D, Boyen X. Efficient lattice (H)IBE in the standard model. In: Advances in Cryptology--EUROCRYPT 2010. Berlin: Springer, 2010. 553--572. Google Scholar

[34] Agrawal S, Boneh D, Boyen X. Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE In: Advances in Cryptology--CRYPTO 2010. Berlin: Springer, 2010. 98--115. Google Scholar

[35] Cash D, Hofheinz D, Kiltz E, et al. Bonsai trees, or how to delegate a lattice basis. In: Advances in Cryptology--EUROCRYPT 2010. Berlin: Springer, 2010. 523--552. Google Scholar

[36] Yamada S. Adaptively secure identity-based encryption from lattices with asymptotically shorter public parameters. In: Advances in Cryptology--EUROCRYPT 2016. Berlin: Springer, 2016. 32--62. Google Scholar

[37] Zhang J, Chen Y, Zhang Z. Programmable hash functions from lattices: Short signatures and IBEs with small key sizes. In: Advances in Cryptology--CRYPTO 2016. Berlin: Springer, 2016. 303--332. Google Scholar

[38] Yamada S. Asymptotically compact adaptively secure lattice IBEs and verifiable random functions via generalized partitioning techniques. In: Advances in Cryptology--CRYPTO 2017. Berlin: Springer, 2017. 161--193. Google Scholar

[39] Döttling N, Garg S, Hajiabadi M, et al. New constructions of identity-based and key-dependent message secure encryption schemes. In: Public-Key Cryptography--PKC 2018. Berlin: Springer, 2018. 3--31. Google Scholar

[40] Micciancio D, Peikert C. Trapdoors for lattices: Simpler, tighter, faster, smaller. In: Advances in Cryptology--EUROCRYPT 2012. Berlin: Springer, 2012. 700--718. Google Scholar

[41] Canetti R, Halevi S, Katz J. Chosen-ciphertext security from identity-based encryption. In: EUROCRYPT 2004, LNCS, Berlin: Springer, 2004. 207--222. Google Scholar

[42] Boneh D, Katz J. Improved efficiency for CCA-secure cryptosystems built using identity-based encryption. In: Topics in Cryptology--CT-RSA 2005. Berlin: Springer, 2005. 87--103. Google Scholar

[43] Lyubashevsky V, Micciancio D. Asymptotically Efficient Lattice-Based Digital Signatures. J Cryptol, 2018, 31: 774-797 CrossRef Google Scholar

[44] Albrecht M R, Player R, Scott S. On the concrete hardness of learning with errors. Journal of Mathematical Cryptology, 2015, 9: 169--203. Google Scholar

[45] Ajtai M. Generating hard instances of the short basis problem. In: Automata, Languages and Programming. Berlin: Springer, 1999. 706--706. Google Scholar

[46] Gentry C, Peikert C, Vaikuntanathan V. Trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, 2008. 197--206. Google Scholar

[47] Regev O. On lattices, learning with errors, random linear codes, and cryptography. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing. New York: ACM, 2005. 84--93. Google Scholar

[48] Applebaum B, Cash D, Peikert C, et al. Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In: Advances in Cryptology--CRYPTO 2009. Berlin: Springer, 2009. 595--618. Google Scholar

[49] Lindner R, Peikert C. Better key sizes (and attacks) for LWE-based encryption. In: Topics in Cryptology--CT-RSA 2011. Berlin: Springer, 2011. 6558: 319--339. Google Scholar

[50] Bos J, Costello C, Ducas L, et al. Frodo: take off the ring practical, quantum-secure key exchange from LWE In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2016. 1006--1018. Google Scholar

[51] Stehlé D, Steinfeld R, Tanaka K, et al. Efficient public key encryption based on ideal lattices. In: Advances in Cryptology -- ASIACRYPT 2009. Berlin: Springer, 2009. 617--635. Google Scholar

[52] Lyubashevsky V, Peikert C, Regev O. On ideal lattices and learning with errors over rings. In: Advances in Cryptology--EUROCRYPT 2010. Berlin: Springer, 2010. 1--23. Google Scholar

[53] Stehlé D, Steinfeld R. Making NTRU as secure as worst-case problems over ideal lattices. In: Advances in Cryptology--EUROCRYPT 2011. Berlin: Springer, 2011. 27--47. Google Scholar

[54] Alkim E, Ducas L, Pöppelmann T, et al. Post-quantum key exchange-a new hope. In: Proceedings of the 25th USENIX Security Symposium, Austin, 2016. Google Scholar

[55] Alkim E, Ducas L, Pöppelmann T, et al. Newhope without reconciliation. Cryptology ePrint Archive, Report 2016/1157, 2016. Google Scholar

[56] Boneh D, Dagdelen Ö Fischlin M, et al. Random oracles in a quantum world. In: Advances in Cryptology--ASIACRYPT 2011. Berlin: Springer, 2011. 41--69. Google Scholar

[57] Jiang H, Zhang Z, Chen L, et al. IND-CCA-secure key encapsulation mechanism in the quantum random oracle model, revisted. In: Advances in Cryptology -- CRYPTO 2018. Berlin: Springer, 2018. 96--125. Google Scholar

[58] Saito T, Xagawa K, Yamakawa T. Tightly-secure key-encapsulation mechanism in the quantum random oracle model. In: Advances in Cryptology -- EUROCRYPT 2018. Berlin: Springer, 2018. 520--551. Google Scholar

[59] Libert B, Sakzad A, Stehlé D, et al. All-but-many lossy trapdoor functions and selective opening chosen-ciphertext security from LWE In: Advances in Cryptology -- CRYPTO 2017. Berlin: Springer, 2017. 332--364. Google Scholar

[60] Banaszczyk W. New bounds in some transference theorems in the geometry of numbers. Math Ann, 1993, 296: 625-635 CrossRef Google Scholar

[61] Peikert C. An efficient and parallel Gaussian sampler for lattices. In: Advances in Cryptology--CRYPTO 2010. Berlin: Springer, 2010. 80--97. Google Scholar

[62] Ducas L, Micciancio D. Improved short lattice signatures in the standard model. In: Advances in Cryptology--CRYPTO 2014. Berlin: Springer, 2014. 335--352. Google Scholar

[63] Vershynin R. Introduction to the non-asymptotic analysis of random matrices. 2010,. arXiv Google Scholar

[64] Peikert C, Regev O, Stephens-Davidowitz N. Pseudorandomness of ring-LWE for any ring and modulus. In: STOC 2017. ACM, 2017. 461--473. Google Scholar

[65] Alwen J, Peikert C. Generating shorter bases for hard random lattices. In STACS, 2009, 75--86. Google Scholar

[66] Cramer R, Damgård I. On the amortized complexity of zero-knowledge protocols. In: CRYPTO 2009, LNCS, Berlin: Springer, 2009. 177--191. Google Scholar

[67] Shoup V. Sequences of Games: a Taming Complexity in Security Proofs. Cryptology ePrint Archive, Report 2004/332, 2004. Google Scholar

[68] Brakerski Z, Vaikuntanathan V. Efficient fully homomorphic encryption from (standard) LWE In: Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. Washington: IEEE Computer Society, 2011. 97--106. Google Scholar

  • Table 1  

    Table 1A concrete comparison of the ciphertext size of our CCA2-secure PKE and the CCA1-secure one in [40] for encrypting a 256-bit (respectively, 512-bit) message at 128-bit (respectively, 256-bit) security

    Scheme LWE parameter $(n,m,q,\alpha~q)$ Ciphertext size Decryption error Security strength
    MP12 [40] $(450,11905,3^{10},2.45)$ 24.74 KB (20.89 KB$^\dag$) $2^{-88}$ $2^{128}$
    $(660,19041,3^{11},5.2)$ 44.19 KB (37.10 KB$^\dag$)$2^{-115}$$2^{257}$
    This paper $(450,10740,3^{9},1.5)$ 13.80 KB (33%–44% $~\downarrow)$ $~\bf{2^{-100}}$$~~\bf{2^{131}}$
    $(660,17333,3^{10},3.1)$ 23.47 KB (36%–46% $~\downarrow)$ $~\bf{2^{-138}}$ $~~\bf{2^{260}}$
  •   

Copyright 2020  CHINA SCIENCE PUBLISHING & MEDIA LTD.  中国科技出版传媒股份有限公司  版权所有

京ICP备14028887号-23       京公网安备11010102003388号