Post-quantum secure fully-dynamic logarithmic-size deniable group signature in code-based setting

Jayashree Dey; Ratna Dutta

doi:10.3934/amc.2022077

Article Contents

2024, Volume 18, Issue 5: 1155-1194. Doi: 10.3934/amc.2022077

This issue Previous Article Next Article $ \mathbb{Z}_{p^r}\mathbb{Z}_{p^s}\mathbb{Z}_{p^t} $-additive cyclic codes

Post-quantum secure fully-dynamic logarithmic-size deniable group signature in code-based setting

Jayashree Dey^1, , and
Ratna Dutta^1,

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

^*Corresponding author: Jayashree Dey
^*Corresponding author: Jayashree Dey

Received: March 2022

Revised: July 2022

Early access: September 2022

Published: October 2024

Abstract / Introduction Full Text(HTML) Figure(11) / Table(1) Related Papers Cited by

Abstract

Since its introduction by Chaum and Heyst, group signature has been one of the most active areas of cryptographic research with numerous applications to computer security and privacy. Group signature permits the members of a group to sign a document on behalf of the entire group keeping signer's identity secret and enabling disclosure of the signer's identity if required. In this work, we present the first code-based fully-dynamic group signature scheme which allows group members to join or leave the group at any point of time. We employ a code-based updatable Merkle-tree accumulator in our design to achieve logarithmic-size signature and utilize randomized Niederreiter encryption to trace the identity of the signer. More positively, we equipped our scheme with deniability characteristic whereby the tracing authority can furnish evidence showing that a given member is not the signer of a particular signature. Our scheme satisfies the security requirements of anonymity, non-frameability, traceability and tracing-soundness in the random oracle model under the hardness of generic decoding problem. We emphasize that our scheme provides full-dynamicity, features deniability in contrast to the existing code-based group signature schemes and works favourably in terms of signature size, group public key size and secret key size.

Keywords:

Mathematics Subject Classification: Primary: 94A60; Secondary: 94A62, 11T71, 68P27.

Citation:

Full Text(HTML)

Figure 1. A Merkle tree with $ 2^3 = 8 $ leaves

Download: Full-size image PowerPoint slide

Figure 2. Zero Knowledge Argument of Knowledge for the relation $ R_{\textsf{abs}} $

Download: Full-size image PowerPoint slide

Figure 3. Interaction between $\textsf{GM}$ and $\textsf{TM}$ in $\textsf{KeyGen}$ algorithm

Download: Full-size image PowerPoint slide

Figure 4. Interaction between $\textsf{GM}$ and $\textsf{U}$ in Join algorithm

Download: Full-size image PowerPoint slide

Figure 5. Notations and permuting techniques for constructing the ZKAoK

Download: Full-size image PowerPoint slide

Figure 6. Properties of vectors in $ \textsf{VALID}_G $

Download: Full-size image PowerPoint slide

Figure 7. Notations and permuting techniques for constructing the ZKAoK for $\textsf{FDGSD.Trace}$ algorithm

Download: Full-size image PowerPoint slide

Figure 8. Properties of vectors in $ \textsf{VALID}_T $

Download: Full-size image PowerPoint slide

Figure 9. Properties of vectors in $ \textsf{VALID}_D $

Download: Full-size image PowerPoint slide

Figure 10. The oracles queried by the adversary in the security experiments

Download: Full-size image PowerPoint slide

Figure 11. Game $ G_0 $ between challenger $ \mathcal{C} $ and adversary $ \mathcal{A} $ for Theorem 5.1

Download: Full-size image PowerPoint slide

Table 1. Summary of existing code-based group signatures

Scheme	group $\textsf{pk}$ size	signer's $\textsf{sk}$ size	signature size	Code used	Model	Deniability
[2]	$\mathcal{O}(N^{\frac{1}{\sqrt{\log N}}})$	$\mathcal{O}(\lambda)$	$\mathcal{O}(N^{\frac{1}{\sqrt{\log N}}})$	Binary Goppa	Partial dynamic	No
[5]	$\mathcal{O}(\lambda^2)$	$\mathcal{O}(\lambda)$	$\mathcal{O}(\lambda^2)$	QC-MDPC	Partial dynamic	No
[18]	$\mathcal{O}(\lambda^2+\lambda N)$	$\mathcal{O}(\lambda )$	$\mathcal{O}(\lambda^2+ N+\log N)$	Binary Goppa	Static	No
[3]	$\mathcal{O}(\lambda^2)$	$\mathcal{O}(\lambda)$	$\mathcal{O}(\lambda^2+ N+\log N)$	QC-MDPC	Static	No
[32]	$\mathcal{O}(\lambda^2)$	$\mathcal{O}(\lambda \log N)$	$\mathcal{O}(\lambda \log N)$	Binary Goppa	Static	No
This work	$\mathcal{O}(\lambda^2)$	$\mathcal{O}(\lambda)+\log N$	$\mathcal{O}(\lambda \log N)$	Binary Goppa	Fully-dynamic	Yes
$\textsf{pk}$= Public key, $\textsf{sk}$= Secret key, $ \lambda $= Security parameter, $N (= 2^l)$=Number of group users, QC=Quasi-Cyclic, MDPC=Moderate Density Parity Check

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	Q. Alamélou, O. Blazy, S. Cauchie and P. Gaborit, A code-based group signature scheme, The 9th International Workshop on Coding and Cryptography–WCC, 2015.
[2]	Q. Alamélou, O. Blazy, S. Cauchie and P. Gaborit, A code-based group signature scheme, Des. Codes Cryptogr., 82 (2017), 469-493. doi: 10.1007/s10623-016-0276-6.
[3]	H. Assidi, E. B. Ayebie and E. M. Souidi, A code-based group signature scheme with shorter public key length, International Conference on Security and Cryptography, SCITEPRESS, 2 (2016), 432-439.
[4]	D. Augot, M. Finiasz and N. Sendrier, A fast provably secure cryptographic hash function, Cryptology ePrint Archive, 2003.
[5]	B. E. Ayebie, H. Assidi and E. M. Souidi, A new dynamic code-based group signature scheme, Codes, Cryptology and Information Security, Lecture Notes in Computer Science, Springer, Cham, 10194 (2017), 346-364. doi: 10.1007/978-3-319-55589-8_23.
[6]	A. Barg, Complexity issues in coding theory, Handbook of Coding Theory North-Holland, Amsterdam, 1/2 (1998), 649-754.
[7]	M. Bellare, D. Micciancio and B. Warinschi, Foundations of group signatures: Formal definitions, simplified requirements, and a construction based on general assumptions, Advances in Cryptology–EUROCRYPT 2003, Lecture Notes in Computer Science, Springer, Berlin, 2656 (2003), 614-629. doi: 10.1007/3-540-39200-9_38.
[8]	M. Bellare, H. Shi and C. Zhang, Foundations of group signatures: The case of dynamic groups, Topics in Cryptology-CT-RSA 2005, Lecture Notes in Computer Science, Springer, Berlin, 3376 (2005), 136-153. doi: 10.1007/978-3-540-30574-3_11.
[9]	E. Berlekamp, R. McEliece and H. V. Tilborg, On the inherent intractability of certain coding problems (corresp.), IEEE Transactions on Information Theory, 24 (1978), 384-386. doi: 10.1109/tit.1978.1055873.
[10]	D. Boneh, X. Boyen and H. Shacham, Short group signatures, Advances in Cryptology-CRYPTO 2004, Lecture Notes in Computer Science, Springer, Berlin, 3152 (2004), 41-55. doi: 10.1007/978-3-540-28628-8_3.
[11]	J. Bootle, A. Cerulli, P. Chaidos, E. Ghadafi and J. Groth, Foundations of fully dynamic group signatures, Applied Cryptography and Network Security, Lecture Notes in Computer Science, Springer, Cham, 9696 (2016), 117-136. doi: 10.1007/978-3-319-39555-5_7.
[12]	X. Boyen and B. Waters, Compact group signatures without random oracles, Advances in Cryptology–EUROCRYPT 2006, Lecture Notes in Computer Science, Springer, Berlin, 4004 (2006), 427-444. doi: 10.1007/11761679_26.
[13]	E. Bresson and J. Stern, Efficient revocation in group signatures, Public Key Cryptography–PKC 2001, Lecture Notes in Computer Science, Springer, Berlin, 1992 (2001), 190-206. doi: 10.1007/3-540-44586-2_15.
[14]	E. Brickell, D. Pointcheval, S. Vaudenay and M. Yung, Design validations for discrete logarithm based signature schemes, Public Key Cryptography, Lecture Notes in Computer Science, Springer, Berlin, 1751 (2000), 276-292. doi: 10.1007/978-3-540-46588-1_19.
[15]	D. Chaum and E. V. Heyst, Group signatures, Advances in Cryptology–EUROCRYPT 1991, Lecture Notes in Computer Science, Springer, Berlin, 547 (1991), 257-265.
[16]	N. T. Courtois, M. Finiasz and N. Sendrier, How to achieve a mceliece-based digital signature scheme, Advances in Cryptology–ASIACRYPT 2001, Lecture Notes in Computer Science, Springer, Berlin, 2248 (2001), 157-174. doi: 10.1007/3-540-45682-1_10.
[17]	M. F. Ezerman, H. T. Lee, S. Ling, K. Nguyen and H. Wang, A provably secure group signature scheme from code-based assumptions, Advances in Cryptology–ASIACRYPT 2015, Lecture Notes in Computer Science, Springer, Berlin, 9452 (2015), 260-285. doi: 10.1007/978-3-662-48797-6_12.
[18]	M. F. Ezerman, H. T. Lee, S. Ling, K. Nguyen and H. Wang, Provably secure group signature schemes from code-based assumptions, IEEE Trans. Inform. Theory, 66 (2020), 5754-5773. doi: 10.1109/TIT.2020.2976073.
[19]	A. Fiat and A. Shamir, How to prove yourself: Practical solutions to identification and signature problems, Advances in Cryptology–CRYPTO'86, Lecture Notes in Computer Science, Springer, Berlin, 263 (1987), 186-194. doi: 10.1007/3-540-47721-7_12.
[20]	S. D. Gordon, J. Katz and V. Vaikuntanathan, A group signature scheme from lattice assumptions, Advances in Cryptology–ASIACRYPT 2010, Lecture Notes in Computer Science, Springer, Berlin, 6477 (2010), 395-412. doi: 10.1007/978-3-642-17373-8_23.
[21]	A. Ishida, K. Emura, G. Hanaoka, Y. Sakai and K. Tanaka, Group signature with deniability: How to disavow a signature, IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences, 100 (2017), 1825-1837.
[22]	F. Laguillaumie, A. Langlois, B. Libert and D. Stehlé, Lattice-based group signatures with logarithmic signature size, Advances in Cryptology–ASIACRYPT 2013, Lecture Notes in Computer Science, Springer, Berlin, 8270 (2013), 41-61. doi: 10.1007/978-3-642-42045-0_3.
[23]	A. Langlois, S. Ling, K. Nguyen and H. Wang, Lattice-based group signature scheme with verifier-local revocation, Public-Key Cryptography–PKC 2014, Lecture Notes in Computer Science, Springer, Berlin, 8383 (2014), 345-361. doi: 10.1007/978-3-642-54631-0_20.
[24]	B. Libert, S. Ling, F. Mouhartem, K. Nguyen and H. Wang, Signature schemes with efficient protocols and dynamic group signatures from lattice assumptions, Advances in Cryptology–ASIACRYPT 2016, Lecture Notes in Computer Science, Springer, Berlin, 10032 (2016), 373-403. doi: 10.1007/978-3-662-53890-6_13.
[25]	B. Libert, S. Ling, K. Nguyen and H. Wang, Zero-knowledge arguments for lattice-based accumulators: logarithmic-size ring signatures and group signatures without trapdoors, Advances in Cryptology–EUROCRYPT 2016, Lecture Notes in Computer Science, Springer, Berlin, 9666 (2016), 1-31. doi: 10.1007/978-3-662-49896-5_1.
[26]	B. Libert, F. Mouhartem and K. Nguyen, A lattice-based group signature scheme with message-dependent opening, Applied Cryptography and Network Security, Lecture Notes in Computer Science, Springer, Cham, 9696 (2016), 137-155. doi: 10.1007/978-3-319-39555-5_8.
[27]	B. Libert, T. Peters and M. Yung, Scalable group signatures with revocation, Advances in Cryptology–EUROCRYPT 2012, Lecture Notes in Computer Science, Springer, Berlin, 7237 (2012), 609-627. doi: 10.1007/978-3-642-29011-4_36.
[28]	S. Ling, K. Nguyen and H. Wang, Group signatures from lattices: Simpler, tighter, shorter, ring-based, Public-Key Cryptography–PKC 2015, Lecture Notes in Computer Science, Springer, Berlin, 9020 (2015), 427-449. doi: 10.1007/978-3-662-46447-2_19.
[29]	S. Ling, K. Nguyen, H. Wang and Y. Xu, Lattice-based group signatures: Achieving full dynamicity (and deniability) with ease, Theoret. Comput. Sci., 783 (2019), 71-94. doi: 10.1016/j.tcs.2019.03.023.
[30]	F. J. MacWilliams and N. J. Sloane, The Theory of Error-Correcting Codes, North-Holland Mathematical Library, Vol. 16. North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977.
[31]	M. Naor and M. Yung, Public-key cryptosystems provably secure against chosen ciphertext attacks, Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, (1990), 427-437.
[32]	K. Nguyen, H. Tang, H. Wang and N. Zeng, New code-based privacy-preserving cryptographic constructions, Advances in Cryptology–ASIACRYPT 2019, Lecture Notes in Computer Science, Springer, Cham, 11922 (2019), 25-55.
[33]	P. Q. Nguyen, J. Zhang and Z. Zhang, Simpler efficient group signatures from lattices, Public-Key Cryptography–PKC 2015, Lecture Notes in Computer Science, Springer, Berlin, 9020 (2015), 401-426. doi: 10.1007/978-3-662-46447-2_18.
[34]	R. Nojima, H. Imai, K. Kobara and K. Morozov, Semantic security for the mceliece cryptosystem without random oracles, Des. Codes Cryptogr., 49 (2008), 289-305. doi: 10.1007/s10623-008-9175-9.
[35]	J. Stern, A new paradigm for public key identification, IEEE Trans. Inform. Theory, 42 (1996), 1757-1768. doi: 10.1109/18.556672.
[36]	G. Tsudik and S. Xu, Accumulating composites and improved group signing, Advances in Cryptology–ASIACRYPT 2003, Lecture Notes in Computer Science, Springer, Berlin, 2894 (2003), 269-286. doi: 10.1007/978-3-540-40061-5_16.