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  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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[9]

U. Hohenberger, Honest verifier zk and fiat-shamir (lecture 1), (2007), https://www.cs.jhu.edu/susan/600.641/scribes/lecture11.pdf. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[9]

U. Hohenberger, Honest verifier zk and fiat-shamir (lecture 1), (2007), https://www.cs.jhu.edu/susan/600.641/scribes/lecture11.pdf. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

Figure 1.  Node Labeling
Table 1.  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) $
[1]

Hui Xu, Guangbin Cai, Xiaogang Yang, Erliang Yao, Xiaofeng Li. Stereo visual odometry based on dynamic and static features division. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021059

[2]

Dandan Cheng, Qian Hao, Zhiming Li. Scale pressure for amenable group actions. Communications on Pure & Applied Analysis, 2021, 20 (3) : 1091-1102. doi: 10.3934/cpaa.2021008

[3]

Palash Sarkar, Subhadip Singha. Verifying solutions to LWE with implications for concrete security. Advances in Mathematics of Communications, 2021, 15 (2) : 257-266. doi: 10.3934/amc.2020057

[4]

Stefano Bianchini, Paolo Bonicatto. Forward untangling and applications to the uniqueness problem for the continuity equation. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2739-2776. doi: 10.3934/dcds.2020384

[5]

Roberto Civino, Riccardo Longo. Formal security proof for a scheme on a topological network. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021009

[6]

Chris Guiver, Nathan Poppelreiter, Richard Rebarber, Brigitte Tenhumberg, Stuart Townley. Dynamic observers for unknown populations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 3279-3302. doi: 10.3934/dcdsb.2020232

[7]

Arseny Egorov. Morse coding for a Fuchsian group of finite covolume. Journal of Modern Dynamics, 2009, 3 (4) : 637-646. doi: 10.3934/jmd.2009.3.637

[8]

Zhang Chen, Xiliang Li, Bixiang Wang. Invariant measures of stochastic delay lattice systems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 3235-3269. doi: 10.3934/dcdsb.2020226

[9]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021

[10]

Andrés Contreras, Juan Peypouquet. Forward-backward approximation of nonlinear semigroups in finite and infinite horizon. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021051

[11]

Palash Sarkar, Subhadip Singha. Classical reduction of gap SVP to LWE: A concrete security analysis. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021004

[12]

Zhimin Chen, Kaihui Liu, Xiuxiang Liu. Evaluating vaccination effectiveness of group-specific fractional-dose strategies. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021062

[13]

Simone Cacace, Maurizio Falcone. A dynamic domain decomposition for the eikonal-diffusion equation. Discrete & Continuous Dynamical Systems - S, 2016, 9 (1) : 109-123. doi: 10.3934/dcdss.2016.9.109

[14]

Xinyuan Liao, Caidi Zhao, Shengfan Zhou. Compact uniform attractors for dissipative non-autonomous lattice dynamical systems. Communications on Pure & Applied Analysis, 2007, 6 (4) : 1087-1111. doi: 10.3934/cpaa.2007.6.1087

[15]

Christoforidou Amalia, Christian-Oliver Ewald. A lattice method for option evaluation with regime-switching asset correlation structure. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1729-1752. doi: 10.3934/jimo.2020042

[16]

Francis Hounkpe, Gregory Seregin. An approximation of forward self-similar solutions to the 3D Navier-Stokes system. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021059

[17]

Joe Gildea, Adrian Korban, Abidin Kaya, Bahattin Yildiz. Constructing self-dual codes from group rings and reverse circulant matrices. Advances in Mathematics of Communications, 2021, 15 (3) : 471-485. doi: 10.3934/amc.2020077

[18]

Xianchao Xiu, Ying Yang, Wanquan Liu, Lingchen Kong, Meijuan Shang. An improved total variation regularized RPCA for moving object detection with dynamic background. Journal of Industrial & Management Optimization, 2020, 16 (4) : 1685-1698. doi: 10.3934/jimo.2019024

[19]

Yuncherl Choi, Taeyoung Ha, Jongmin Han, Sewoong Kim, Doo Seok Lee. Turing instability and dynamic phase transition for the Brusselator model with multiple critical eigenvalues. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021035

[20]

Shuting Chen, Zengji Du, Jiang Liu, Ke Wang. The dynamic properties of a generalized Kawahara equation with Kuramoto-Sivashinsky perturbation. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021098

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (385)
  • HTML views (741)
  • Cited by (0)

[Back to Top]