FABS: Fast Attribute-Based Signatures

Liqun Chen; Long Meng; Yalan Wang; Nada El Kassem; Christopher JP Newton; Yangguang Tian; Jodie Knapp; Constantin Catalin Dragan; Daniel Gardham; Mark Manulis

Paper 2026/022

FABS: Fast Attribute-Based Signatures

Liqun Chen

, University of Surrey

Long Meng

, University of Surrey

Yalan Wang

, University of Surrey

Nada El Kassem

, University of Surrey

Christopher JP Newton

, University of Surrey

Yangguang Tian

, University of Surrey

Jodie Knapp

, University of Surrey

Constantin Catalin Dragan

, University of Surrey

Daniel Gardham

, University of Surrey

Mark Manulis

, Universität der Bundeswehr München

Abstract

Attribute-based signatures (ABS) provide fine-grained control over who can generate digital signatures and have many real-world applications. This paper presents a pair of fast ABS schemes: one for Key-Policy ABS (KP-ABS) and another for Signature-Policy ABS (SP-ABS). Both schemes support expressive policies using Monotone Span Programs (MSP), and offer practical features such as large universe, arbitrary attributes, and adaptive security. Most notably, we provide the first implementation of MSP-based ABS schemes and demonstrate that our schemes achieve the best-known asymptotic and concrete performance in this domain. Asymptotically, key generation, signing and verification time scale linearly with the number of attributes; verification requires only two pairing operations. In concrete terms, for 100 attributes, our KP-ABS scheme performs key generation, signing, and verification in 0.16s, 0.10s, and 0.13s, respectively; our SP-ABS scheme achieves times of 0.082s, 0.26s, and 0.21s for the same operations.

Note: This is the full version of the paper, which has been accepted by USENIX Security Symposium 2026.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Major revision. USENIX Security Symposium 2026
Keywords: Attribute-Based Signatures (ABS)Key-Policy ABS Signature-Policy ABS
Contact author(s): liqun chen @ surrey ac uk
long meng @ surrey ac uk
yalan wang @ surrey ac uk
nada elkassem @ surrey ac uk
c newton @ surrey ac uk
yangguang tian @ surrey ac uk
j knapp @ surrey ac uk
c dragan @ surrey ac uk
daniel gardham @ surrey ac uk
mark manulis @ unibw de
History: 2026-01-18: revised; 2026-01-06: received; See all versions
Short URL: https://ia.cr/2026/022
License: CC0

BibTeX

@misc{cryptoeprint:2026/022,
      author = {Liqun Chen and Long Meng and Yalan Wang and Nada El Kassem and Christopher JP Newton and Yangguang Tian and Jodie Knapp and Constantin Catalin Dragan and Daniel Gardham and Mark Manulis},
      title = {{FABS}: Fast Attribute-Based Signatures},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/022},
      year = {2026},
      url = {https://eprint.iacr.org/2026/022}
}