Paper 2019/149

Improved Lattice-based CCA2-Secure PKE in the Standard Model

Jiang Zhang, Yu Yu, Shuqin Fan, and Zhenfeng Zhang


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 model and can be used to obtain a CCA2-secure PKE from 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 primitives such as signatures and commitments. In this paper, we propose a more efficient standard model CCA2-secure PKE from lattices by 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 as unique 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), we not only directly achieve the CCA2-security without using any generic transform (and thus do not use signatures or commitments), but also reduce the noise parameter roughly by a factor of 3. This improvement makes our CCA2-secure PKE more efficient in terms of both computation and storage. In particular, when encrypting a 256-bit (resp., 512-bit) message at 128-bit (resp., 256-bit) security, the ciphertext size of our CCA2-secure PKE is even 33-44% (resp., 36-46%) smaller than that of their CCA1-secure PKE.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
public-key encryptionlearning with errorschosen ciphertext securitystandard model
Contact author(s)
jiangzhang09 @ gmail com
yuyu @ yuyu hk
shuqinfan78 @ 163 com
zfzhang @ tca iscas ac cn
2019-02-20: received
Short URL
Creative Commons Attribution


      author = {Jiang Zhang and Yu Yu and Shuqin Fan and Zhenfeng Zhang},
      title = {Improved Lattice-based CCA2-Secure PKE in the Standard Model},
      howpublished = {Cryptology ePrint Archive, Paper 2019/149},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.