Lattice-based sequential aggregate signatures with lazy verification

doi:10.1016/S1005-8885(15)60691-4

Acta Metallurgica Sinica(English letters) ›› 2015, Vol. 22 ›› Issue (6): 36-44.doi: 10.1016/S1005-8885(15)60691-4

• Wireless • Previous Articles Next Articles

Lattice-based sequential aggregate signatures with lazy verification

Zhang Yanhua, Hu Yupu, Jiang Mingming, Xue Lili

1. State Key Laboratory of Integrated Service Networks, Xidian University, Xi’an 71007, China 2. School of Computer Science and Technology, Huaibei Normal University, Huaibei 23500, China

Online:2015-12-31

Abstract

Abstract: This paper proposes the first lattice-based sequential aggregate signature (SAS) scheme with lazy verification that is provably secure in the random oracle model. As opposed to large integer factoring and discrete logarithm based systems, the security of the construction relies on worst-case lattice problem, namely, under the small integer solution (SIS) assumption. Generally speaking, SAS schemes enable any group of signers ordered in a chain to sequentially combine their signatures such that the size of the aggregate signature is much smaller than the total size of all individual signatures. Unlike prior such proposals, the new scheme does not require a signer to retrieve the keys of other signers and verify the aggregate-so-far before adding its own signature, and the signer can add its own signature to an unverified aggregate and forward it along immediately, postponing verification until load permits or the necessary public keys are obtained. Indeed, the new scheme does not even require a signer to know the public keys of other signers.

Key words: sequential aggregate signatures, lattice-based cryptography, lazy verification, small integer solution

Zhang Yanhua, Hu Yupu, Jiang Mingming, Xue Lili. Lattice-based sequential aggregate signatures with lazy verification[J]. Acta Metallurgica Sinica(English letters), 2015, 22(6): 36-44.

References

1. Kent S, Lynn C, Seo K. Secure border gateway protocol (S-BGP). IEEE Journal of Selected Areas in Communications, 2000, 18(4): 582-592

2. Boneh D, Gentry C, Lynn B, et al. Aggregate and verifiably encrypted signatures from bilinear maps. Advances in Cryptology: Proceedings of the 22nd International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’03), May 4-8, 2003, Warsaw, Poland. LNCS 2656. Berlin, Germany: Springer-Verlag, 2003: 416-432

3. Neven G. Efficient sequential aggregate signed date. Advances in Cryptology: Proceedings of the 27th International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’08), Apr 13-17, 2008, Istanbul, Turkey. LNCS 4965. Berlin, Germany: Springer-Verlag, 2008: 52-69

4. Lysyanskaya A, Micali S, Reyzin L, et al. Sequential aggregate signatures from trapdoor permutations. Advances in Cryptology: Proceedings of the 23rd International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’04), May 2-6, 2004, Interlaken, Switzerland. LNCS 3027. Berlin, Germany: Springer-Verlag, 2004: 74-90

5. Brogle K, Goldberg S, Reyzin L. Sequential aggregate signatures with lazy verification from trapdoor permutations. Advances in Cryptology: Proceedings of the 18th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT’12), Dec 2-6, 2012, Beijing, China. LNCS 7658. Berlin, Germany: Springer-Verlag, 2012: 644-662

6. Ajtai M. Generating hard instances of lattice problems (extended abstract). Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC’96), May 22-24, 1996, Philadelphia, PA, USA. New York, NY, USA: ACM, 1996: 99-108

7. Gentry C, Peikert C, Vaikuntanathan V. How to use a short basis: trapdoors for hard lattices and new cryptographic constructions. Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC’08), May 17-20, 2008, Victoria, Canada. New York, NY, USA: ACM, 2008: 197-206

8. Regev O. On lattices, learning with errors, random linear codes, and cryptography. Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC’05), May 22-24, 2005, Baltimore, MD,USA. New York, NY, USA: ACM, 2005: 84-93

9. Lyubashevsky V, Peikert C, Regev O. On ideal lattices and learning with errors over rings. Advances in Cryptology: Proceedings of the 29th International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’10), May 30-Jun 3, 2010, Nice, France. LNCS 6110. Berlin, Germany: Springer-Verlag, 2010: 1-23

10. Lindner R, Peikert C. Better key sizes (and attacks) for LWE-based encryption. Topics in Cryptology: Proceedings of the Cryptographers’ Track at the RSA Conference (CT-RSA’11), Feb 14-18, 2011, San Francisco, CA, USA. LNCS 6558. Berlin, Germany: Springer-Verlag, 2011: 319-339

11. Stehlé D, Steinfeld R. Making NTRU as secure as worst-case problems over ideal lattices. Advances in Cryptology: Proceedings of the 30th International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’11), May 15-19, 2011, Tallinn, Estonia. LNCS 6632. Berlin, Germany: Springer-Verlag, 2011: 27-47

12. Cash D, Hofheinz D, Kiltz E, et al. Bonsai trees, or how to delegate a lattice basis. Advances in Cryptology: Proceedings of the 29th International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’10), May 30-Jun 3, 2010, Nice, France. LNCS 6110. Berlin, Germany: Springer-Verlag, 2010: 523-552

13. Agrawal S, Boneh D, Boyen X. Efficient lattice (H) IBE in the standard model. Advances in Cryptology: Proceedings of the 29th International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’10), May 30-Jun 3, 2010, Nice, France. LNCS 6110. Berlin, Germany: Springer-Verlag, 2010: 553-572

14. Agrawal S, Boneh D, Boyen X. Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE. Advances in Cryptology: Proceedings of the 30th Annual Cryptology Conference (CRYPTO’10), Aug 15-19, 2010, Santa Barbara, CA, USA. LNCS 6223. Berlin, Germany: Springer-Verlag, 2010: 98-115

15. Gentry C. Fully homomorphic encryption using ideal lattices. Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC’09), May 31-Jun 2, 2009, Bethesda, MD, USA. New York, NY, USA: ACM, 2009: 169-178

16. Gentry C. Toward basing fully homomorphic encryption on worst-case hardness. Advances in Cryptology: Proceedings of the 30th Annual Cryptology Conference (CRYPTO’10), Aug 15-19, 2010, Santa Barbara, CA, USA. LNCS 6223. Berlin, Germany: Springer-Verlag, 2010: 116-137

17. Brakerski Z, Vaikuntanathan V. Fully homomorphic encryption from ring-LWE and security for key dependent messages. Advances in Cryptology: Proceedings of the 31st Annual Cryptology Conference (CRYPTO’11), Aug 14-18, 2011, Santa Barbara, CA, USA. LNCS 6841. Berlin, Germany: Springer-Verlag, 2011: 505-524

18. Brakerski Z, Vaikuntanathan V. Efficient fully homomorphic encryption from (standard) LWE. Proceedings of the 52nd IEEE Annual Symposium on Foundations of Computer Science (FOCS’11), Oct 22-25, 2011, Palm Springs, CA, USA. Piscataway, NJ, USA: IEEE, 2011: 97-106

19. Boyen X. Lattice mixing and vanishing trapdoors: a framework for fully secure short signature and more. Public Key Cryptography: Proceedings of the 13th International Conference on Practice and Theory in Public Key Cryptosystems (PKC’10), May 26-28, 2010, Paris, France. LNCS 6056. Berlin,Germany: Springer-Verlag, 2010: 499-517

20. Lyubashevsky V. Lattice signatures without trapdoors. Advances in Cryptology: Proceedings of the 31st International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’12), Apr 15-19, 2012, Cambridge, UK. LNCS 7237. Berlin, Germany: Springer-Verlag, 2012: 738-755

21. Dov Gordon S, Katz J, Vaikuntanathan V. A group signature scheme from lattice assumptions. Advances in Cryptology: Proceedings of the 16th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT-10), Dec 5-9, 2010, Singapore. LNCS 6477. Berlin, Germany: Springer-Verlag, 2010: 395-412

22. Rückert M. Lattice-based blind signatures. Advances in Cryptology: Proceedings of the 16th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT’10), Dec 5-9, 2010, Singapore. LNCS 6477. Berlin, Germany: Springer-Verlag, 2010: 413-430

23. Rückert M. Strongly unforgeable signatures and hierarchical identity-based signatures from lattices without random oracles. Post-Quantum Cryptography: Proceedings of the 3rd International Workshop (PQcrypto’10), May 25-28, 2010, Darmstadt, Germany. LNCS 6061. Berlin, Germany: Springer-Verlag, 2010: 182-200

24. El Bansarkhani R, Buchmann J. Towards lattice based aggregate signatures. Progress in Cryptology: Proceedings of the 7th International Conference on Cryptology in Africa (AFRICACRYPT’14), May 28-30, 2014, Marrakesh, Morocco. LNCS 8469. Berlin, Germany: Springer-Verlag, 2014: 336-355

25. Joël A, Chris P. Generating shorter bases for hard random lattices. Journal of Theory of Computing Systems, 2011, 48(3): 535-553

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

Metrics

Comments

Copyright © 2020 The Journal of China Universities of Posts and Telecommunications
　 Adress: P.O. Box 231,Beijing University of Posts and Telecommunications,10 Xi Tucheng Road,Beijing 100876,P.R.China　Post Code: 100081
Tel：86-010-62282493　Fax： 86-010-62283461　E-mail: jchupt@bupt.edu.cn
Support by: Beijing Magtech Co.Ltd

Lattice-based sequential aggregate signatures with lazy verification

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 0

Recommended Articles

Metrics

Comments