American Institute of Mathematical Sciences

November  2020, 14(4): 535-553. doi: 10.3934/amc.2020027

Group signature from lattices preserving forward security in dynamic setting

 Department of Mathematics, Indian Institute of Technology Kharagpur, Kharagpur-721302, India

* Corresponding author: Meenakshi Kansal

Received  October 2018 Revised  March 2019 Published  November 2020 Early access  September 2019

We propose the first lattice-based dynamic group signature scheme achieving forward security. Our scheme is proven to be secure against framing attack, misidentification attack and preserves anonymity under the learning with errors (${\mathsf{LWE}}$) and short integer solution (${\mathsf{SIS}}$) assumptions in the random oracle model. More interestingly, our setting allows the group manager to generate distinct certificates to distinct users which can be updated by the users themselves without any interaction with the group manager. Furthermore, our scheme is dynamic where signing key of a user is not fixed during the setup and is issued only at the joining time of the user.

Citation: Meenakshi Kansal, Ratna Dutta, Sourav Mukhopadhyay. Group signature from lattices preserving forward security in dynamic setting. Advances in Mathematics of Communications, 2020, 14 (4) : 535-553. doi: 10.3934/amc.2020027
References:
 [1] S. Agrawal, D. Boneh and X. Boyen, Efficient lattice (H)IBE in the standard model, in Advances in cryptology—EUROCRYPT 2010, Lecture Notes in Comput. Sci., Springer, Berlin, 6110 (2010), 553–572. doi: 10.1007/978-3-642-13190-5_28. [2] M. Ajtai, Generating hard instances of lattice problems (extended abstract), in Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, ACM, New York, (1996), 99–108. doi: 10.1145/237814.237838. [3] J. Alwen and C. Peikert, Generating shorter bases for hard random lattices, Theory of Computing Systems, 48 (2011), 535-553.  doi: 10.1007/s00224-010-9278-3. [4] E. Brickell, D. Pointcheval, S. Vaudenay and M. Yung, Design validations for discrete logarithm based signature schemes, in Public Key Cryptography, Lecture Notes in Comput. Sci., Springer, Berlin, 1751 (2000), 276–292. doi: 10.1007/978-3-540-46588-1_19. [5] J. Camenisch, G. Neven and M. Rückert, Fully anonymous attribute tokens from lattices, in International Conference on Security and Cryptography for Networks, Springer, 2012, 57–75. doi: 10.1007/978-3-642-32928-9_4. [6] D. Cash, D. Hofheinz, E. Kiltz and C. Peikert, Bonsai trees, or how to delegate a lattice basis, in Advances in cryptology—EUROCRYPT 2010, Lecture Notes in Comput. Sci., Springer, Berlin, 6110 (2010), 523–552. doi: 10.1007/978-3-642-13190-5_27. [7] C. Gentry, C. Peikert and V. Vaikuntanathan, Trapdoors for hard lattices and new cryptographic constructions, in STOC'08, ACM, New York, (2008), 197–206. doi: 10.1145/1374376.1374407. [8] S. D. Gordon, J. Katz and V. Vaikuntanathan, A group signature scheme from lattice assumptions, in Advances in cryptology—ASIACRYPT 2010, Lecture Notes in Comput. Sci., Springer, Berlin, 6477 (2010), 395–412. doi: 10.1007/978-3-642-17373-8_23. [9] U. Hohenberger, Honest verifier zk and fiat-shamir (lecture 1), (2007), https://www.cs.jhu.edu/susan/600.641/scribes/lecture11.pdf. [10] F. Laguillaumie, A. Langlois, B. Libert and D. Stehlé, Lattice-based group signatures with logarithmic signature size, in Advances in cryptology—ASIACRYPT 2013. Part Ⅱ, Lecture Notes in Comput. Sci., Springer, Heidelberg, 8270 (2013), 41–61. doi: 10.1007/978-3-642-42045-0_3. [11] B. Libert, S. Ling, F. Mouhartem, K. Nguyen and H. X. Wang, Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions, in Advances in Cryptology—ASIACRYPT 2016. Part Ⅱ, Lecture Notes in Comput. Sci., Springer, Berlin, 10032 (2016), 373–403. doi: 10.1007/978-3-662-53890-6_13. [12] B. Libert and M. Yung, Fully forward-secure group signatures, in Cryptography and Security: From Theory to Applications, Springer, (2012), 156–184. doi: 10.1007/978-3-642-28368-0_13. [13] S. Ling, K. Nguyen, D. Stehlé and H. X. Wang, Improved zero-knowledge proofs of knowledge for the ISIS problem, and applications, in Public Key Cryptography—PKC 2013, Lecture Notes in Comput. Sci., Springer, Heidelberg, 7778 (2013), 107–124. doi: 10.1007/978-3-642-36362-7_8. [14] S. Ling, K. Nguyen and H. X. Wang, Group signatures from lattices: simpler, tighter, shorter, ring-based, in Public-key Cryptography—PKC 2015, Lecture Notes in Comput. Sci., Springer, Heidelberg, 9020 (2015), 427–449. doi: 10.1007/978-3-662-46447-2_19. [15] S. Ling, K. Nguyen, H. X. Wang and Y. H. Xu, Forward-secure group signatures from lattices, International Conference on Post-Quantum Cryptography, 11505 (2019), 44–64, arXiv: 1801.08323. doi: 10.1007/978-3-030-25510-7_3. [16] O. Regev, On lattices, learning with errors, random linear codes, and cryptography, Journal of the ACM (JACM), 56 (2009), Art. 34, 40 pp. doi: 10.1145/1568318.1568324.

show all references

References:
 [1] S. Agrawal, D. Boneh and X. Boyen, Efficient lattice (H)IBE in the standard model, in Advances in cryptology—EUROCRYPT 2010, Lecture Notes in Comput. Sci., Springer, Berlin, 6110 (2010), 553–572. doi: 10.1007/978-3-642-13190-5_28. [2] M. Ajtai, Generating hard instances of lattice problems (extended abstract), in Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, ACM, New York, (1996), 99–108. doi: 10.1145/237814.237838. [3] J. Alwen and C. Peikert, Generating shorter bases for hard random lattices, Theory of Computing Systems, 48 (2011), 535-553.  doi: 10.1007/s00224-010-9278-3. [4] E. Brickell, D. Pointcheval, S. Vaudenay and M. Yung, Design validations for discrete logarithm based signature schemes, in Public Key Cryptography, Lecture Notes in Comput. Sci., Springer, Berlin, 1751 (2000), 276–292. doi: 10.1007/978-3-540-46588-1_19. [5] J. Camenisch, G. Neven and M. Rückert, Fully anonymous attribute tokens from lattices, in International Conference on Security and Cryptography for Networks, Springer, 2012, 57–75. doi: 10.1007/978-3-642-32928-9_4. [6] D. Cash, D. Hofheinz, E. Kiltz and C. Peikert, Bonsai trees, or how to delegate a lattice basis, in Advances in cryptology—EUROCRYPT 2010, Lecture Notes in Comput. Sci., Springer, Berlin, 6110 (2010), 523–552. doi: 10.1007/978-3-642-13190-5_27. [7] C. Gentry, C. Peikert and V. Vaikuntanathan, Trapdoors for hard lattices and new cryptographic constructions, in STOC'08, ACM, New York, (2008), 197–206. doi: 10.1145/1374376.1374407. [8] S. D. Gordon, J. Katz and V. Vaikuntanathan, A group signature scheme from lattice assumptions, in Advances in cryptology—ASIACRYPT 2010, Lecture Notes in Comput. Sci., Springer, Berlin, 6477 (2010), 395–412. doi: 10.1007/978-3-642-17373-8_23. [9] U. Hohenberger, Honest verifier zk and fiat-shamir (lecture 1), (2007), https://www.cs.jhu.edu/susan/600.641/scribes/lecture11.pdf. [10] F. Laguillaumie, A. Langlois, B. Libert and D. Stehlé, Lattice-based group signatures with logarithmic signature size, in Advances in cryptology—ASIACRYPT 2013. Part Ⅱ, Lecture Notes in Comput. Sci., Springer, Heidelberg, 8270 (2013), 41–61. doi: 10.1007/978-3-642-42045-0_3. [11] B. Libert, S. Ling, F. Mouhartem, K. Nguyen and H. X. Wang, Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions, in Advances in Cryptology—ASIACRYPT 2016. Part Ⅱ, Lecture Notes in Comput. Sci., Springer, Berlin, 10032 (2016), 373–403. doi: 10.1007/978-3-662-53890-6_13. [12] B. Libert and M. Yung, Fully forward-secure group signatures, in Cryptography and Security: From Theory to Applications, Springer, (2012), 156–184. doi: 10.1007/978-3-642-28368-0_13. [13] S. Ling, K. Nguyen, D. Stehlé and H. X. Wang, Improved zero-knowledge proofs of knowledge for the ISIS problem, and applications, in Public Key Cryptography—PKC 2013, Lecture Notes in Comput. Sci., Springer, Heidelberg, 7778 (2013), 107–124. doi: 10.1007/978-3-642-36362-7_8. [14] S. Ling, K. Nguyen and H. X. Wang, Group signatures from lattices: simpler, tighter, shorter, ring-based, in Public-key Cryptography—PKC 2015, Lecture Notes in Comput. Sci., Springer, Heidelberg, 9020 (2015), 427–449. doi: 10.1007/978-3-662-46447-2_19. [15] S. Ling, K. Nguyen, H. X. Wang and Y. H. Xu, Forward-secure group signatures from lattices, International Conference on Post-Quantum Cryptography, 11505 (2019), 44–64, arXiv: 1801.08323. doi: 10.1007/978-3-030-25510-7_3. [16] O. Regev, On lattices, learning with errors, random linear codes, and cryptography, Journal of the ACM (JACM), 56 (2009), Art. 34, 40 pp. doi: 10.1145/1568318.1568324.
Node Labeling
Comparative summary of lattice based group signature schemes
 Scheme Forward secure Dynamic Signature size Public key size Certificate size Signer's SK size [8] No No $N\cdot \tilde{\mathcal{O}}(n^2)$ $N\cdot \tilde{\mathcal{O}}(n^2)$ - $\tilde{\mathcal{O}}(n^2)$ [5] No No $N\cdot \tilde{\mathcal{O}}(n^2)$ $N\cdot \tilde{\mathcal{O}}(n^2)$ - $\tilde{\mathcal{O}}(n^2)$ [10] No No $\log N \cdot \tilde{\mathcal{O}}(n)$ $\log N \cdot \tilde{\mathcal{O}}(n^2)$ - $\tilde{\mathcal{O}}(n^2)$ [14] No No $\log N \cdot \tilde{\mathcal{O}}(n)$ $\log N \cdot \tilde{\mathcal{O}}(n^2)$ - $\tilde{\mathcal{O}}(n)$ [11] No Yes $\log N \cdot \tilde{\mathcal{O}}(n)$ $\log N \cdot \tilde{\mathcal{O}}(n^2)$ $\log N \cdot \mathcal{O}(n)$ $\tilde{\mathcal{O}}(n)$ [15] Yes No $\log N \cdot \tilde{\mathcal{O}}(n)$ $\log N \cdot \tilde{\mathcal{O}}(n^2)$ - $\log N \; \tilde{\mathcal{O}}(n^2)$ Ours Yes Yes $\log N\; \tilde{\mathcal{O}}(n^3)$ $\log N \cdot \tilde{\mathcal{O}}(n^2)$ $\log N \; \tilde{\mathcal{O}}(n^2)$ $\tilde{\mathcal{O}}(n)$
 Scheme Forward secure Dynamic Signature size Public key size Certificate size Signer's SK size [8] No No $N\cdot \tilde{\mathcal{O}}(n^2)$ $N\cdot \tilde{\mathcal{O}}(n^2)$ - $\tilde{\mathcal{O}}(n^2)$ [5] No No $N\cdot \tilde{\mathcal{O}}(n^2)$ $N\cdot \tilde{\mathcal{O}}(n^2)$ - $\tilde{\mathcal{O}}(n^2)$ [10] No No $\log N \cdot \tilde{\mathcal{O}}(n)$ $\log N \cdot \tilde{\mathcal{O}}(n^2)$ - $\tilde{\mathcal{O}}(n^2)$ [14] No No $\log N \cdot \tilde{\mathcal{O}}(n)$ $\log N \cdot \tilde{\mathcal{O}}(n^2)$ - $\tilde{\mathcal{O}}(n)$ [11] No Yes $\log N \cdot \tilde{\mathcal{O}}(n)$ $\log N \cdot \tilde{\mathcal{O}}(n^2)$ $\log N \cdot \mathcal{O}(n)$ $\tilde{\mathcal{O}}(n)$ [15] Yes No $\log N \cdot \tilde{\mathcal{O}}(n)$ $\log N \cdot \tilde{\mathcal{O}}(n^2)$ - $\log N \; \tilde{\mathcal{O}}(n^2)$ Ours Yes Yes $\log N\; \tilde{\mathcal{O}}(n^3)$ $\log N \cdot \tilde{\mathcal{O}}(n^2)$ $\log N \; \tilde{\mathcal{O}}(n^2)$ $\tilde{\mathcal{O}}(n)$

2020 Impact Factor: 0.935