Identity-based Signatures from Lattices : Simpler, Faster, Shorter

• Autorzy: Tian M. , Huang L.

Identyfikatory

DOI

10.3233/FI-2016-1353

• Języki publikacji: EN

Abstrakty

EN

Identity-based signature is an important technique for light-weight authentication. Recently, many efforts have been made to construct identity-based signatures over lattice assumptions since they would remain secure in future quantum age. In this paper we present a new identitybased signature scheme from lattice problems. This scheme is more efficient than other lattice-based identity-based signature schemes in terms of both computation and communication complexities. We prove its security in the random oracle model under short integer solution assumption that is as hard as approximating several worst-case lattice problems. We also extend the scheme to an identity-based message recovery signature scheme that has better performance.

Słowa kluczowe

EN

identity-based signature; lattice; message recovery; performance

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 145, nr 2
• Strony: 171--187
• Opis fizyczny: Bibliogr. 29 poz., tab.

Twórcy

autor

Tian M.

• School of Computer Science and Technology & Suzhou Institute for Advanced Study, University of Science and Technology of China, China

autor

Huang L.

• School of Computer Science and Technology & Suzhou Institute for Advanced Study, University of Science and Technology of China, China

Bibliografia

• [1] Abe M, Okamoto T. A signature scheme with message recovery as secure as discrete logarithm. in: ASIACRYPT’99, Springer, LNCS 1999;1716: p.378–389.
• [2] Agrawal S, Boneh D, Boyen X. Efficient lattice (H)IBE in the standard model. in: EUROCRYPT 2010. Springer, LNCS 2010;6110:553–572. doi:10.1007/978-3-642-13190-5 28.
• [3] Agrawal S, Boneh D, Boyen X. Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE. in: CRYPTO 2010. Springer, LNCS 2010;6223:98–115. doi:10.1007/978-3-642-14623-7 6.
• [4] Ajtai M. Generating hard instances of lattice problems. STOC’96, ACM. 1996. TR96-007. Available from: http://www.eccc.unitrier.de/eccc. doi:10.1145/237814.237838.
• [5] Alwen J, Peikert C. Generating shorter bases for hard random lattices. Theory of Computing Systems. 2011; 48(3):535–553. doi:10.1007/s00224-010-9278-3.
• [6] Barr K, Asanović K. Energy-aware lossless data compression. ACM Transactions on Computer Systems (TOCS). 2006;24(3):250–291. doi:10.1145/1151690.1151692.
• [7] Barreto P, Libert B, McCullagh N, Quisquater J-J. Efficient and provably-secure identity-based signatures and signcryption from bilinear maps. in: ASIACRYPT 2005, Springer, LNCS 2005;3788:515–532. doi:10.1007/11593447 28.
• [8] Bellare M, Neven G. Multi-signatures in the plain public-key model and a general forking lemma. Proceedings of the 13th ACM conference on Computer and communications security, CCS 2006. ACM New York. 2006; p.390-399. doi:10.1145/1180405.1180453.
• [9] Boneh D, FranklinM. Identity-based encryption from theWeil pairing. in: Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology CRYPTO 2001. Springer, LNCS 2001;2139: p. 213-229.
• [10] Cash D, Hofheinz D, Kiltz E, Peikert C. Bonsai trees, or how to delegate a lattice basis. in: Advances in Cryptology, Proceedings EUROCRYPT 2010, Springer, LNCS 2010;6110:523–552. doi:10.1007/978-3-642-13190-5 27.
• [11] Choon J, Cheon J. An identity-based signature from gap Diffie-Hellman groups. in: 6th International Workshop on Practice and Theory in Public Key Cryptography. Miami, January 68, Proceedings PKC 2003, Springer, LNCS 2003;2567:18–30. doi:10.1007/3-540-36288-6 2.
• [12] Fiat A, Shamir A. How to prove yourself: practical solutions to identification and signature problems. in: Advances in Cryptology, Proceedings CRYPTO’86, Springer, LNCS 1987;263:186-194.
• [13] Gentry C, Peikert C, Vaikuntanathan V. Trapdoors for hard lattices and new cryptographic constructions. in: Proceedings of the fortieth annual ACM symposium on Theory of computing STOC 2008, ACM. 2008; p.197–206. doi:10.1145/1374376.1374407
• [14] Hess F. Efficient identity based signature schemes based on pairings. Selected Areas in Cryptography, Springer, LNCS 2003; p.310-324. doi:10.1007/3-540-36492-7 20.
• [15] Liu Z, Hu Y, Zhang X, Li F. Efficient and strongly unforgeable identity-based signature scheme from lattices in the standard model. Security and Communication Networks. 2013;6(1):69–77. doi:10.1002/sec.531.
• [16] Lyubashevsky V. Lattice signatures without trapdoors. in: Advances in Cryptology, Proceedings EUROCRYPT 2012, Springer. 2012;7237:738–755. doi:10.1007/978-3-642-29011-4 43.
• [17] Micciancio D, Regev O. Worst-case to average-case reductions based on Gaussian measures. SIAM J. Computing. 2007;37(1):267–302. doi:10.1137/S0097539705447360.
• [18] Nyberg K, Rueppel R. A new signature scheme based on the DSA giving message recovery. in: Proceedings of the 1st ACM conference on Computer and Communications Security CCS’93, ACM. 1993; p.58–61.
• [19] Nyberg K, Rueppel R. Message recovery for signature schemes based on the discrete logarithm problem. in: Advances in Cryptology - EUROCRYPT ’94. Workshop on the Theory and Application of Cryptographic Techniques, Italy, May 9-12, 1994. Proceedings EUROCRYPT’94, Springer, LNCS 1995;950: p.182–193. doi:10.1007/BFb0053434.
• [20] Paterson K, Schuldt J. Efficient identity-based signatures secure in the standard model. in: 11th Australasian Conference, ACISP 2006,Melbourne, July 3-5, 2006. Proceedings ACISP 2006, Springer, LNCS 2006;4058: p.207-222. doi:10.1007/11780656 18.
• [21] Regev O. Lattice-based cryptography. in: Advances in Cryptology, Proceedings CRYPTO 2006, Springer, LNCS 2006;4117: p.131–141. doi:10.1007/11818175 8.
• [22] Rückert M. Strongly unforgeable signatures and hierarchical identity-based signatures from lattices without random oracles, in: Post-Quantum Cryptography, Springer, LNCS 2010;6061: p.182–200. doi:10.1007/978-3-642-12929-2 14.
• [23] Shamir A. Identity-based cryptosystems and signature schemes, in: CRYPTO’84, Springer, LNCS 1985;196: p.47–53.
• [24] Shor, P.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Computing 1997;26(5):1484–1509.
• [25] Tian M, Huang L. Efficient identity-based signature from lattices. in: IFIP Advances in Information and Communication Technology, Springer, 2014;428: p.321–329. doi:10.1007/978-3-642-55415-5 26.
• [26] Tian M, Huang L, Yang W. A new hierarchical identity-based signature scheme from lattices in the standard model. I.J. Network Security, 2012;14(6):310–315.
• [27] Tian M, Huang L, Yang W. Efficient hierarchical identity–based signatures from lattices. Int. J. Electronic Security and Digital Forensics, 2013;5(1):1–10.
• [28] Von Neumann J. Various techniques used in connection with random digits, J. Research Nat. Bur. Stand., Appl. Math. Series. 1951;12(1):36–38.
• [29] Zhang F, Susilo W, Mu Y. Identity-based partial message recovery signatures (or how to shorten IDbased signatures). in:Financial Cryptography and Data Security, LNCS, Springer 2005;3570:45–56. doi:10.1007/11507840 5.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.