Linkable and traceable anonymous authentication with fine-grained access control

Abstract

To prevent misuse of privacy, numerous anonymous authentication schemes with linkability and/or traceability have been proposed to ensure different types of accountabilities. Previous schemes cannot simultaneously achieve public linking and tracing while holding access control, therefore, a new tool named linkable and traceable anonymous authentication with fine-grained access control (LTAA-FGAC) is offered, which is designed to satisfy: (i) access control, i.e., only authorized users who meet a designated authentication policy are approved to authenticate messages; (ii) public linkability, i.e., anyone can tell whether two authentications with respect to a common identifier are created by an identical user; (iii) public traceability, i.e., everyone has the ability to deduce a double-authentication user’s identity from two linked authentications without the help of other parties. We formally define the basic security requirements for the new tool, and also give a generic construction so as to satisfy these requirements. Then, we present a formal security proof and an implementation of our proposed LTAA-FGAC scheme.

Graphical abstract

Keywords

anonymous authentication / access control / public linkability / public traceability

Peng Li received the PhD degree from Jinan University, China in 2021. He is currently a Postdoctoral Researcher with Jinan University, China. His research interests include cryptography and information security

Junzuo Lai received the PhD degree in computer science and technology from Shanghai Jiao Tong University, China in 2010. He is currently a professor with the College of Information Science Technology, Jinan University, China. From August 2008 to April 2013, he was a research fellow in Singapore Management University, Singapore. He has published more than 60 papers in international conferences and journals such as EUROCRYPT, ASIACRYPT, PKC, IEEE Transactions on Dependable and Secure Computing (TDSC) and IEEE Transactions on Information Forensics and Security (TIFS). His research interests include cryptography and information security

Dehua Zhou received the PhD degree from Shanghai Jiao Tong University, China in 2013. From 2016 to 2017, he was a visiting researcher at Pennsylvania State University, USA. Currently, he is an associate professor in the College of Information Science and Technology, Jinan University, China. His research interests include cryptography and information security

Lianguan Huang received the MS degree with the College of Cyber Security, Jinan University, China in 2023. He is currently an engineer with Huawei Technology. His research interests include privacy-preserving technologies and blockchain

Meng Sun received the BS degree from the School of Information Science and Technology, Northwest University, China in 2018. She is currently working toward the PhD degree with the College of Cyber Security, Jinan University, China. Her research interests include cryptography and information security

Wei Wu received the MS degree with the College of Cyber Security, Jinan University, China in 2022. He is currently an engineer with the Vehicle Cyber Security Lab, Huawei Technology, China. His research interests include privacy-preserving technologies and blockchain

Ye Yang received the MS degree with the College of Cyber Security, Jinan University, China in 2022. She is currently an engineer with the ByteDance Corporation. Her research interests include cryptography and information security

References

[1] Liu J K, Wong D S. On the security models of (threshold) ring signature schemes. In: Proceedings of the 7th International Conference on Information Security and Cryptology. 2005, 204−217

[2] Camenisch J, Stadler M. Efficient group signature schemes for large groups. In: Proceedings of the 17th Annual International Cryptology Conference. 1997, 410−424

[3] Kumawat S, Paul S. A new constant-size accountable ring signature scheme without random oracles. In: Proceedings of the 13th International Conference on Information Security and Cryptology. 2018, 157−179

[4] Libert B, Yung M. Efficient traceable signatures in the standard model. Theoretical Computer Science, 2011, 412(12−14): 1220−1242

[5] Hwang J Y, Chen L, Cho H S, Nyang D . Short dynamic group signature scheme supporting controllable linkability. IEEE Transactions on Information Forensics and Security, 2015, 10( 6): 1109–1124

[6] Boyen X, Haines T. Forward-secure linkable ring signatures. In: Proceedings of the 23rd Australasian Conference on Information Security and Privacy. 2018, 245−264

[7] Lu Y, Tang Q, Wang G. ZebraLancer: private and anonymous crowdsourcing system atop open blockchain. In: Proceedings of the 38th IEEE International Conference on Distributed Computing Systems. 2018, 853−865

[8] Fujisaki E, Suzuki K. Traceable ring signature. In: Proceedings of the 10th International Conference on Practice and Theory in Public-Key Cryptography. 2007, 181−200

[9] Au M H, Susilo W, Yiu S M. Event-oriented k-times revocable-iff-linked group signatures. In: Proceedings of the 11th Australasian Conference on Information Security and Privacy. 2006, 223−234

[10] Wei V K. Tracing-by-linking group signatures. In: Proceedings of the 8th International Conference on Information Security. 2005, 149−163

[11] Nguyen L, Safavi-Naini R. Dynamic k-times anonymous authentication. In: Proceedings of the 3rd International Conference on Applied Cryptography and Network Security. 2005, 318−333

[12] Maji H K, Prabhakaran M, Rosulek M. Attribute-based signatures. In: Proceedings of Cryptographers’ Track at the RSA Conference 2011. 2011, 376−392

[13] Blömer J, Bobolz J, Diemert D, Eidens F. Updatable anonymous credentials and applications to incentive systems. In: Proceedings of 2019 ACM SIGSAC Conference on Computer and Communications Security. 2019, 1671−1685

[14] El Kaafarani A, Ghadafi E. Attribute-based signatures with user-controlled linkability without random oracles. In: Proceedings of the 16th IMA International Conference on Cryptography and Coding. 2017, 161−184

[15] Gu K, Wang K, Yang L . Traceable attribute-based signature. Journal of Information Security and Applications, 2019, 49: 102400

[16] Hébant C, Pointcheval D. Traceable constant-size multi-authority credentials. In: Proceedings of the 13th International Conference on Security and Cryptography for Networks. 2022, 411−434

[17] Fiore D, Garms L, Kolonelos D, Soriente C, Tucker I. Ring signatures with user-controlled linkability. In: Proceedings of the 27th European Symposium on Research in Computer Security. 2022, 405−426

[18] Garms L, Lehmann A. Group signatures with selective linkability. In: Proceedings of the 22nd IACR International Conference on Practice and Theory of Public-Key Cryptography. 2019, 190−220

[19] Slamanig D, Spreitzer R, Unterluggauer T. Adding controllable linkability to pairing-based group signatures for free. In: Proceedings of the 17th International Conference on Information Security. 2014, 388−400

[20] Krenn S, Samelin K, Striecks C. Practical group-signatures with privacy-friendly openings. In: Proceedings of the 14th International Conference on Availability, Reliability and Security. 2019, 10

[21] Zheng H, Wu Q, Qin B, Zhong L, He S, Liu J. Linkable group signature for auditing anonymous communication. In: Proceedings of the 23rd Australasian Conference on Information Security and Privacy. 2018, 304−321

[22] Zhang X, Liu J K, Steinfeld R, Kuchta V, Yu J. Revocable and linkable ring signature. In: Proceedings of the 15th International Conference on Information Security and Cryptology. 2020, 3−27

[23] Au M H, Liu J K, Susilo W, Yuen T H . Secure ID-based linkable and revocable-iff-linked ring signature with constant-size construction. Theoretical Computer Science, 2013, 469: 1–14

[24] Okamoto T, Takashima K. Efficient attribute-based signatures for non-monotone predicates in the standard model. In: Proceedings of the 14th International Conference on Practice and Theory in Public Key Cryptography. 2011, 35−52

[25] Okamoto T, Takashima K. Decentralized attribute-based signatures. In: Proceedings of the 16th International Conference on Practice and Theory in Public-Key Cryptography. 2013, 125−142

[26] Camenisch J, Drijvers M, Dzurenda P, Hajny J. Fast keyed-verification anonymous credentials on standard smart cards. In: Proceedings of the 34th IFIP TC 11 International Conference on ICT Systems Security and Privacy Protection. 2019, 286−298

[27] Tan S Y, Groß T. Monipoly—an expressive q-SDH-based anonymous attribute-based credential system. In: Proceedings of the 26th International Conference on the Theory and Application of Cryptology and Information Security. 2020, 498−526

[28] Urquidi M, Khader D, Lancrenon J, Chen L. Attribute-based signatures with controllable linkability. In: Proceedings of the 7th International Conference on Trusted Systems. 2016, 114−129

[29] El Kaafarani A, Chen L, Ghadafi E, Davenport J. Attribute-based signatures with user-controlled linkability. In: Proceedings of the 13th International Conference on Cryptology and Network Security. 2014, 256−269

[30] Drǎgan C C, Gardham D, Manulis M. Hierarchical attribute-based signatures. In: Proceedings of the 17th International Conference on Cryptology and Network Security. 2018, 213−234

[31] Wei J, Huang X, Hu X, Liu W. Revocable threshold attribute-based signature against signing key exposure. In: Proceedings of the 11th International Conference on Information Security Practice and Experience. 2015, 316−330

[32] Ding S, Zhao Y, Liu Y. Efficient traceable attribute-based signature. In: Proceedings of the 13th IEEE International Conference on Trust, Security and Privacy in Computing and Communications. 2014, 582−589

[33] El Kaafarani A, Ghadafi E, Khader D. Decentralized traceable attribute-based signatures. In: Proceedings of Cryptographer’s Track at the RSA Conference 2014. 2014, 327−348

[34] Ghadafi E. Stronger security notions for decentralized traceable attribute-based signatures and more efficient constructions. In: Proceedings of Cryptographer’s Track at the RSA Conference 2015. 2015, 391−409

[35] Ali S T, Amberker B B . Attribute-based group signature without random oracles with attribute anonymity. International Journal of Information and Computer Security, 2014, 6( 2): 109–132

[36] Kuchta V, Sharma G, Sahu R A, Markowitch O. Generic framework for attribute-based group signature. In: Proceedings of the 13th International Conference on Information Security Practice and Experience. 2017, 814−834

[37] Kaaniche N, Laurent M. Attribute-based signatures for supporting anonymous certification. In: Proceedings of the 21st European Symposium on Research in Computer Security. 2016, 279−300

[38] Kapadia A, Tsang P P, Smith S W. Attribute-based publishing with hidden credentials and hidden policies. In: Proceedings of Network and Distributed System Security Symposium. 2007, 1−14

[39] Zhang Y, Chen X, Li J, Wong D S, Li H. Anonymous attribute-based encryption supporting efficient decryption test. In: Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security. 2013, 511−516

[40] Li J, Ren K, Zhu B, Wan Z. Privacy-aware attribute-based encryption with user accountability. In: Proceedings of the 12th International Conference on Information Security. 2009, 347−362

[41] Lipmaa H. Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments. In: Proceedings of the 9th Theory of Cryptography Conference on Theory of Cryptography. 2012, 169−189

[42] Groth J, Maller M. Snarky signatures: minimal signatures of knowledge from simulation-extractable SNARKs. In: Proceedings of the 37th Annual International Cryptology Conference on Advances in Cryptology. 2017, 581−612

[43] Guan Z, Wan Z, Yang Y, Zhou Y, Huang B . BlockMaze: an efficient privacy-preserving account-model blockchain based on zk-SNARKs. IEEE Transactions on Dependable and Secure Computing, 2022, 19( 3): 1446–1463

Acknowledgements

This work was supported by the National Natural Science Foundation of China (Grant Nos. U2001205, 61932010), Guangdong Basic and Applied Basic Research Foundation (Nos. 2023B1515040020, 2019B030302008), and Guangdong Provincial Key Laboratory of Power System Network Security (No. GPKLPSNS-2022-KF-05).

Competing interests

The authors declare that they have no competing interests or financial conflicts to disclose.

RIGHTS & PERMISSIONS

2025 Higher Education Press