Paper 2024/022

Fully Dynamic Attribute-Based Signatures for Circuits from Codes

San Ling, Nanyang Technological University
Khoa Nguyen, University of Wollongong
Duong Hieu Phan, Institut Polytechnique de Paris
Khai Hanh Tang, Nanyang Technological University
Huaxiong Wang, Nanyang Technological University
Yanhong Xu, Shanghai Jiao Tong University

Attribute-Based Signature (ABS), introduced by Maji et al. (CT-RSA'11), is an advanced privacy-preserving signature primitive that has gained a lot of attention. Research on ABS can be categorized into three main themes: expanding the expressiveness of signing policies, enabling new functionalities, and providing more diversity in terms of computational assumptions. We contribute to the development of ABS in all three dimensions, by providing a fully dynamic ABS scheme for arbitrary circuits from codes. The scheme is the first ABS from code-based assumptions and also the first ABS system offering the \texttt{full dynamicity} functionality (i.e., attributes can be enrolled and revoked simultaneously). Moreover, the scheme features much shorter signature size than a lattice-based counterpart proposed by El Kaafarani and Katsumata (PKC'18). In the construction process, we put forward a new theoretical abstraction of Stern-like zero-knowledge (ZK) protocols, which are the major tools for privacy-preserving cryptography from codes. Our main insight here actually lies in the questions we ask about the fundamental principles of Stern-like protocols that have remained unchallenged since their conception by Stern at CRYPTO'93. We demonstrate that these long-established principles are not essential, and then provide a refined framework generalizing existing Stern-like techniques and enabling enhanced constructions.

Available format(s)
Publication info
A major revision of an IACR publication in PKC 2024
Attribute-based signaturescode-based cryptographyfull dynamicitynew primitivesStern-like protocols
Contact author(s)
lingsan @ ntu edu sg
khoa @ uow edu au
hieu phan @ telecom-paris fr
khaihanh tang @ ntu edu sg
hxwang @ ntu edu sg
yanhong xu @ sjtu edu cn
2024-01-13: last of 2 revisions
2024-01-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {San Ling and Khoa Nguyen and Duong Hieu Phan and Khai Hanh Tang and Huaxiong Wang and Yanhong Xu},
      title = {Fully Dynamic Attribute-Based Signatures for Circuits from Codes},
      howpublished = {Cryptology ePrint Archive, Paper 2024/022},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.