Attribute-based signatures on lattices

doi:10.1016/S1005-8885(16)60049-3

中国邮电高校学报(英文) ›› 2016, Vol. 23 ›› Issue (4): 83-90.doi: 10.1016/S1005-8885(16)60049-3

Attribute-based signatures on lattices

谢佳,胡予濮,高军涛,高雯,李雪莲

西安电子科技大学

收稿日期:2015-11-25 修回日期:2016-05-25 出版日期:2016-08-30 发布日期:2016-08-30
通讯作者: 谢佳 E-mail:xiejia199325@163.com
基金资助:
自然科学基金;中央高校基本科研业务费;陕西省自然科学基金

Attribute-based signatures on lattices

Received:2015-11-25 Revised:2016-05-25 Online:2016-08-30 Published:2016-08-30
Contact: Jia XIE E-mail:xiejia199325@163.com

摘要/Abstract

摘要： Because of its wide application in anonymous authentication and attribute-based messaging, the attribute-based signature scheme has attracted the public attention since it was proposed in 2008. However, most of the existing attribute-based signature schemes are no longer secure in quantum era. Fortunately, lattice-based cryptography offers the hope of withstanding quantum computers. And lattices has elevated it to the status of a promising potential alternative to cryptography based on discrete log and factoring, owing to implementation simplicity, provable security reductions and quantum-immune. In this paper, the first lattice attribute-based signature scheme in random oracle model is proposed, which is proved existential unforgeability and perfect privacy. Compared with the current attribute-based signature schemes, our new attribute-based signature scheme can resist quantum attacks and has much shorter public-key size and signature size. Furthermore, this scheme is extended into an attribute-based signature scheme on number theory research unit (NTRU) lattice, which is also secure even in quantum era and has much higher efficiency than the former.

关键词: attribute, signature, lattice, unforgeability, perfect privacy

Abstract: Because of its wide application in anonymous authentication and attribute-based messaging, the attribute-based signature scheme has attracted the public attention since it was proposed in 2008. However, most of the existing attribute-based signature schemes are no longer secure in quantum era. Fortunately, lattice-based cryptography offers the hope of withstanding quantum computers. And lattices has elevated it to the status of a promising potential alternative to cryptography based on discrete log and factoring, owing to implementation simplicity, provable security reductions and quantum-immune. In this paper, the first lattice attribute-based signature scheme in random oracle model is proposed, which is proved existential unforgeability and perfect privacy. Compared with the current attribute-based signature schemes, our new attribute-based signature scheme can resist quantum attacks and has much shorter public-key size and signature size. Furthermore, this scheme is extended into an attribute-based signature scheme on number theory research unit (NTRU) lattice, which is also secure even in quantum era and has much higher efficiency than the former.

Key words: attribute, signature, lattice, unforgeability, perfect privacy

中图分类号:

TN918.4 TP309.7

Xie Jia,Hu Yupu, Gao Juntao, Gao Wen, Li Xuelian. Attribute-based signatures on lattices[J]. JOURNAL OF CHINA UNIVERSITIES OF POSTS AND TELECOM, 2016, 23(4): 83-90.

参考文献

1. Maji H K, Prabhakaran M, Rosulek M. Attribute-based signature: achieving attribute privacy and collusion-resistance. 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: 376?392 2. Escala A, Herranz J, Morillo P. Revocable attribute based signatures with adaptive security in the standard model. Progress in Cryptology: Proceedings of the 4th International Conference on Cryptology in Africa (AFRICACRYPT’11), Jul 5?7, 2011, Dakar, Senegal. LNCS 6737. Berlin, Germany: Springer-Verlag, 2011: 224?241 3. Li J, Au M H, Susilo W, et al. Attribute-based signature and its applications. Proceedings of the 5th ACM Symposium on Information Computer and Communications Security (ASIACCS’10), Apr 13-16, 2010, Beijing, China. New York, NY, USA: ACM, 2010: 60?69 4. Herranz J, Laguillaumie F, Libert B, et al. Short attribute-based signatures for threshold predicates. Topics in Cryptology: Proceedings of the Cryptolographers’s Track at the RSA Conference 2012 (CT-RSA’12), Feb 27?Mar 2, 2012, San Francisco, CA, USA. LNCS 7178. Berlin, Germany: Springer-Verlag, 2012: 51? 67 5. Zeng F, Xu C X, Li Q Y, et al. Attribute-based signature scheme with constant size signature. Journal of Computational Information Systems, 2012, 8(7): 2875?2882 6. Okamoto T, Takashima K. Efficient attribute based signatures for non-monotone predicates in the standard model. Public-Key Cryptography: Proceedings of the 14th International Conference on Practice and Theory in Public Key Cryptography (PKC’11), Mar 6?9, 2011, Taormina, Italy. LNCS 6571. Berlin, Germany: Springer-Verlag, 2011: 35?52 7. Okamoto T, Takashima K. Decentralized attribute-based signatures. Public-Key Cryptography: Proceedings of the 16th International Conference on Practice and Theory in Public Key Cryptography (PKC13), Feb 26?Mar 1, 2013, Nara, Japan. LNCS 7778. Berlin, Germany: Springer-Verlag , 2013: 125?142 8. Li J, Kim K. Hidden attribute-based signatures without anonymity revocation. Information Sciences, 2010, 180(9): 1681?1689 9. Shahandashti S F, Safavi-Naini R. Threshold attribute-based signature and their application to anonymous credential systems. Progress in Cryptology: Proceedings of the 2nd International Conference on Cryptology in Africa (AFRICACRYPT’09), Jun 21?25, 2009, Gammarth, Tunisia. LNCS 5580. Berlin, Germany: Springer-Verlag, 2009: 198?216 10. Shor P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal of Computing, 1997, 26(5): 1484?1509 11. Bernstein D J. Introduction to post-quantum cryptography. In: Bernstein D J, Buchmann J, Dahmen E. Post-quantum cryptography. Berlin, Germany: Springer-Verlag, 2009: 1?14 12. Regev O. Lattice-based cryptography. Advances in Cryptology: Proceedings of the 26th Annual International Cryptology Conference (CRYPTO’06), Aug 20?24, 2006, Santa Barbara, CA, USA. LNCS 4117. Berlin, Germany: Springer-Verlag, 2006: 131?141 13. Ajtai M. Generating hard instances of the short basis problem. Automata, Languages and Programming: Proceedings of the 26th International Colloquium on Automata, Languages and Programming (ICALP’99), Jul 11?15, 1999, Prague, Czech. LNCS 1644. Berlin, Germany: Springer-Verlag, 1999: 1?9 14. Gentry C, Peikert C, Vaikuntanathan V. 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 15. Alwen J, Peiker C. Generating shorter bases for hard random lattices. Theory of Computing Systems, 2009, 48(3): 535?553 16. Micciancio D, Peikert C. Trapdoors for lattices: simpler, tighter, faster, smaller. Advances in Cryptology: Proceedings of the 31th Annual 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: 700?718 17. Laarhoven T, Mosca M, Van de Pol J. Finding shortest lattice vectors faster using quantum search. Designs, Codes and Cryptography, 2015, 77(2): 375?400 18. Lyubashevsky V, Wichs D. Simple lattice trapdoor sampling from a broad class of distributions. Public-Key Cryptography: Proceedings of 18th International Conference on Practice and Theory in Public-Key Cryptography (PKC’15), Mar 30?Apr 1, 2015, Gaithersburg, MD, USA. LNCS 9020. Berlin, Germany: Springer-Verlag, 2015: 716?730 19. Regev O. On lattices, learning with errors, random linear codes, and cryptography. Proceedings of 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 20. Stehlé D, Steinfeld R. Making NTRU as secure as worst-case problems over ideal lattices. Advances in Cryptology: Proceedings of the 30th Annual 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 21. Cash D, Hofheinz D, Kiltz E, et al. Bonsai trees, or how to delegate a lattice basis. Advances in Cryptology: Proceedings of the 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’10), May 30-Jun 3, 2010, Riviera, France. LNCS 6110. Berlin, Germany: Springer-Verlag, 2010: 523?552 22. Agrawal S, Boneh D, Boyen X. Efficient lattice (H)IBE in the standard model. Advances in Cryptology: Proceedings of 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’10), May 30?June 3, 2010, Riviera, France. LNCS 6110. Berlin, Germany: Springer-Verlag, 2010: 553?572 23. 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 International Cryptology Conference (CRYPTO’10), Aug 15?19, 2010, Santa Barbara, CA, USA. LNCS 6223. Berlin, Germany: Springer-Verlag, 2010: 98?115 24. Ducas L, Lyubashevsky V, Prest T. Efficient identity-based encryption over NTRU lattices. Advances in Cryptology: Proceedings of the 20th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT’14), Dec 7?11, 2014, Kaoshiung, China. LNCS 8874. Berlin, Germany: Springer-Verlag, 2014: 22?41 25. 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 26. Gentry C. Toward basing fully homomorphic encryption on worst-case hardness. Advances in Cryptology: Proceedings of the 30th Annual International Cryptology Conference (CRYPTO’10), Aug 15?19, 2010, Santa Barbara, CA, USA. LNCS 6223. Berlin, Germany: Springer-Verlag, 2010: 116?137 27. Brakerski Z, Vaikuntanathan V. Fully homomorphic encryption from ring-LWE and security for key dependent messages. Advances in Cryptology: Proceedings of 31st Annual International Cryptology Conference (CRYPTO’11), Aug 14?18, 2011, Santa Barbara, CA, USA. LNCS 6841. Berlin, Germany: Springer-Verlag, 2011: 505?524 28. Brakerski Z, Vaikuntanathan V. Efficient fully homomorphic encryption from (standard) LWE. Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS’11), Oct 22?25, 2011, Palm Springs, CA, USA. Piscataway, NJ, USA: IEEE, 2011: 97?106 29. Boyen X. Lattice mixing and vanishing trapdoors: A framework for fully secure short signature and more. Public-Key Cryptography: Proceedings of 13th International Conference on Practice and Theory in Public Key Cryptography (PKC’10), May 26?28, 2010, Paris, France. LNCS 6056. Berlin, Germany: Springer-Verlag, 2010: 499?517 30. Lyubashevsky V. Lattice signatures without trapdoors. Advances in Cryptology: Proceedings of the 31st Annual 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 31. Ducas L, Durmus A, Lepoint T, et al. Lattice signatures and bimodal gaussians. Advances in Cryptology: Proceedings of the 33th Annual International Cryptology Conference (CRYPTO’13), Aug 18?22, 2013, Santa Barbara, CA, USA. LNCS 8042. Berlin, Germany: Springer-Verlag, 2013:40?56 32. Laguillaumie F, Langlois A, Libert B, et al. Lattice-based group signatures with logarithmic signature size. Advances in Cryptology: Proceedings of the 19th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT’13), Dec 1?5, 2013, Bengaluru, India. LNCS 8270. Berlin, Germany: Springer-Verlag, 2013: 41?61 33. Langlois A, Ling S, Nguyen K, et al. Lattice-based group signature scheme with verifier-local revocation. Public-Key Cryptography: Proceedings of 7th International Conference on Practice and Theory in Public Key Cryptography (PKC’14), Mar 26?28, 2014, Buenos Aires, Argentina. LNCS 8383. Berlin, Germany: Springer-Verlag, 2014: 345?361 34. Nguyen P Q, Zhang J, Zhang Z F. Simpler efficient group signatures from lattices. Public-Key Cryptography: Proceedings of 18th International Conference on Practice and Theory in Public Key Cryptography (PKC’15), Mar 30?Apr 1, 2015, Gaithersburg, MD, USA. LNCS 9020. Berlin, Germany: Springer-Verlag, 2015: 401?426 35. Xie J, Hu Y P, Gao J T, et al. Efficient identity-based signature over NTRU lattice. Frontiers of Information Technology & Electronic Engineering, 2016, 17(2): 135?142 36. Garg S, Gentry C, Halevi S. Candidate multilinear maps from ideal lattices. Advances in Cryptology: Proceedings of the 32th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’13), May 26?30, 2013, Athens, Greece. LNCS 7881. Berlin, Germany: Springer-Verlag, 2013: 1?-17 37. Gentry C, Gorbunov S, Halevi S. Graph-induced multilinear maps from lattices. Theory of Cryptography: Proceedings of the 12th Theory of Cryptography Conference (TCC’15), Mar 23?25, 2015, Warsaw, Poland. LNCS 9015. Berlin, Germany: Springer-Verlag, 2015: 498?527 38. Hu Y P, Jia H W. Cryptanalysis of GGH map. Advances in Cryptology: Proceedings of the 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’16), LNCS 9665, May 8?12, 2016, Vienna, Austria. Berlin, Germany: Springer-Verlag, 2016: 537?565 39. Mao X P, Chen K F, Long Y, et al. Attribute-based signature on lattices. Journal of Shanghai Jiaotong University, 2014, 19(4): 406?411 40. Li M X, An N, Feng, E Y, et al. An attribute-based signature scheme from lattices. Journal of Sichuan University (Engineering Science Edition), 2015, 47(2): 102?107 (in Chinese) 41. Zhang Y H, Hu Y P, Jiang M M. An Attribute-based signature scheme from lattice assumption. Wuhan University Journal of Natural Sciences, 2015, 20(3): 207?213 42. 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'06), Oct 30?Nov 3, 2006, Alexandria, VA, USA. New York, NY, USA: ACM, 2006: 390?399

Attribute-based signatures on lattices

Attribute-based signatures on lattices

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

编辑推荐

Metrics

本文评价