Lattice-based certificateless encryption scheme

Abstract

Certificateless public key cryptography (CLPKC) can solve the problems of certificate management in a public key infrastructure (PKI) and of key escrows in identity-based public key cryptography (ID-PKC). In CL-PKC, the key generation center (KGC) does not know the private keys of all users, and their public keys need not be certificated by certification authority (CA). At present, however, most certificateless encryption schemes are based on large integer factorization and discrete logarithms that are not secure in a quantum environment and the computation complexity is high. To solve these problems, we propose a new certificateless encryption scheme based on lattices, more precisely, using the hardness of the learning with errors (LWE) problem. Compared with schemes based on large integer factorization and discrete logarithms, the most operations are matrix-vector multiplication and inner products in our scheme, our approach has lower computation complexity. Our scheme can be proven to be indistinguishability chosen ciphertext attacks (IND-CPA) secure in the random oracle model.

Keywords

lattice-based cryptography / LWE / identitybased encryption (IBE) / post-quantum cryptography / certificateless encryption

References

[1] Al-Riyami S, Paterson K G. Certificateless public key cryptography. Lecture Notes in Computer Science, 2003, 2894: 452-473

[2] Al-Riyami S, Paterson K G. CBE from CL-PKE: a generic construction and efficient schemes. Lecture Notes in Computer Science, 2005, 3386: 398-415

[3] Baek J, Safavi-Naini R, Susilo W. Certificateless public key encryption without pairing. Lecture Notes in Computer Science, 2005, 3650: 134-148

[4] Lai J Z, Deng R H, Liu S L, Kou W D. RSA-based certificateless public key encryption. Lecture Notes in Computer Science, 2009, 5451: 24-34

[5] Yum D H, Lee P J. Generic construction of certificateless encryption. Lecture Notes in Computer Science, 2004, 3043: 802-811

[6] Libert B, Quisquater J J. On constructing certificateless cryptosystems from identity based encryption. Lecture Notes in Computer Science, 2006, 3958: 474-490

[7] Cheng Z H, Chen L Q, Ling L, Comley R. General and efficient certificateless public key encryption constructions. Lecture Notes in Computer Science, 2007, 4575: 83-107

[8] Dent A W, Libert B, Paerson K G. Certificateless encryption schemes strongly secure in the standard model. Lecture Notes in Computer Science, 2008, 4939: 344-359

[9] Huang Q, Wong D S. Generic certificateless encryption in the standard model. Lecture Notes in Computer Science, 2007, 4752: 278-291

[10] 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. 2008, 197-206

[11] Regev O. On lattices, learning with errors, random linear codes, and cryptography. Journal of ACM, 2009, 56(6): Article No. 34

[12] Lyubashevsky V, Peikert C, Regev O. On ideal lattices and learning with errors over rings. Journal of ACM, 2013, 60(6): Article No. 43

[13] Lindner R, Peikert C. Better key sizes (and attacks) for LWE-based encryption. Lecture Notes in Computer Science, 2011, 6558: 319-339

[14] Stehlé D, Steinfeld R. Making NTRU as secure as worst-case problems over ideal lattices. Lecture Notes in Computer Science, 2011, 6632: 27-47

[15] Cash D, Hofheinz D, Kiltz E, Peikert C. Bonsai trees, or how to delegate a lattice basis. Lecture Notes in Computer Science, 2010, 6110: 523-552

[16] Agrawal S, Boneh D, Boyen X. Efficient lattice (H) IBE in the standard model. Lecture Notes in Computer Science, 2010, 6110: 553-572

[17] Agrawal S, Boneh D, Boyen X. Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE. Lecture Notes in Computer Science, 2010, 6223: 98-115

[18] Guang Y, Gu C X, Zhu Y F, Zheng Y H, Fei J L. Certificateless fully homomorphic encryption based on LWE problem. Journal of Electronics and Information Technology, 2013, 35(4): 988-993

[19] Gentry C. Fully homomorphic encryption using ideal lattices. In: Proceedings of STOC2009, 169-178

[20] Gentry C. Toward basing fully homomorphic encryption on worst-case hardness. Lecture Notes in Computer Science, 2010, 6223: 116-137

[21] Brakerski Z, Vaikuntanathan V. Fully homomorphic encryption from ring-LWE and security for key dependent messages. Lecture Notes in Computer Science, 2011, 6841: 505-524

[22] Brakerski Z, Vaikuntanathan V. Efficient fully homomorphicencryption from (standard) LWE. In: Proceedings of 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. 2011, 97-106

[23] Zhang G Y. Fuzzy certificateless identity-based encryption protocol from lattice. Applied Mechanics and Materials, 2013, 380: 2262-2266

[24] Lyubashevsky V. Lattice signatures without trapdoors. Lecture Notes in Computer Science, 2012, 7237: 738-755

[25] Gordon D, Katz J, Vaikuntanathan V. A group signature scheme from lattice assumptions. Lecture Notes in Computer Science, 2010, 6477: 395-412

[26] Rückert M. Lattice-based blind signatures. Lecture Notes in Computer Science, 2010, 6477: 413-430

[27] Rückert M. Strongly unforgeable signatures and hierarchical identitybased signatures from lattices without random oracles. Lecture Notes in Computer Science, 2010, 6061: 182-200

[28] Micciancio D, Regev O. Worst-case to average-case reductions based on gaussian measures. SIAM Journal on Computing, 2007, 37(1): 267-302

[29] Alwen J, Peiker C. Generating shorter bases for hard random lattices. Lecture Notes in Computer Science, 2009, 75-86

[30] Regev O. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM, 2009, 56(6): Article No.34

[31] Peikert C. Public-key cryptosystems from the worst-case shortest vector problem. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing. 2009, 333-342

[32] Boneh D, Freeman D. Linearly homomorphic signatures over binary fields and new tools for lattice-based signatures. Lecture Notes in Computer Science, 2011, 6571: 1-16

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg