A lattice-based signcryption scheme without random oracles

Abstract

In order to achieve secure signcryption schemes in the quantum era, Li Fagen et al. [Concurrency and Computation: Practice and Experience, 2012, 25(4): 2112–2122] and Wang Fenghe et al. [Applied Mathematics & Information Sciences, 2012, 6(1): 23–28] have independently extended the concept of signcryption to lattice-based cryptography. However, their schemes are only secure under the random oracle model. In this paper, we present a lattice-based signcryption scheme which is secure under the standard model. We prove that our scheme achieves indistinguishability against adaptive chosen-ciphertext attacks (IND-CCA2) under the learning with errors (LWE) assumption and existential unforgeability against adaptive chosen-message attacks (EUFCMA) under the small integer solution (SIS) assumption.

Keywords

signcryption / standard model / lattice-based cryptography / learning with errors problem / small integer solution problem

References

[1] Zheng Y. Digital signcryption or how to achieve cost(signature & encryption) _cost(signature) + cost(encryption). Lecture Notes in Computer Science, 1997, 1294: 165-179

[2] Boyen X. Multipurpose identity-based signcryption. Lecture Notes in Computer Science, 2003, 2729: 383-399

[3] Malone-Lee J, Mao W. Two birds one stone: signcryption using RSA. In: Proceedings of the 2003 RSA Conference on the Cryptographers’ Track. 2003, 211-226

[4] Barreto P, Libert B, McCullagh N, Quisquater J. Efficient and provablysecure identity-based signatures and signcryption from bilinear maps. Lecture Notes in Computer Science, 2005, 3788: 515-532

[5] Li F, Shirase M, Takagi T. Certificateless hybrid signcryption. Mathematical and Computer Modelling, 2013, 57(1): 324-343

[6] Shor P. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 1997, 26(5): 1484-1509

[7] Peikert C, Waters B. Lossy trapdoor functions and their applications. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing. 2008, 187-196

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

[9] Micciancio D, Peikert C. Trapdoors for lattices: Simpler, tighter, faster, smaller. Lecture Notes in Computer Science, 2012, 7237: 700-718

[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] 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

[12] Boyen X. Lattice mixing and vanishing trapdoors: A framework for fully secure short signatures and more. Lecture Notes in Computer Science, 2010, 6056: 499-517

[13] Li F, Muhaya F, Khan M, Takagi T. Lattice-based signcryption. Concurrency and Computation: Practice and Experience, 2012, 25(4): 2112-2122

[14] Wang F, Hu Y, Wang C. Post-quantum secure hybrid signcryption from lattice assumption. Applied Mathematics & Information Sciences, 2012, 6(1): 23-28

[15] Bellare M, Rogaway P. The exact security of digital signatures-how to sign with rsa and rabin. Lecture Notes in Computer Science, 1996, 1070: 399-416

[16] Canetti R, Goldreich O, Halevi S. The random oracle methodology, revisited. Journal of the ACM. 2004, 51(4): 557-594

[17] Yan J, Wang L, Wang L, Yang Y, Yao W. Efficient lattice-based signcryption in standard model. Mathematical Problems in Engineering. 2013, 2013: 1-18

[18] Ajtai M. Generating hard instances of the short basis problem. Lecture Notes in Computer Science, 1999, 1644: 1-9

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

[20] Peikert C. Bonsai trees (or, arboriculture in lattice-based cryptography). Cryptology ePrint Archive. 20<?Pub Caret?>09: Report 2009/359

[21] Regev O. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM, 2009, 56(34): 1-40

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

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg