On Digital Signatures Based on Group Actions: QROM Security and Ring Signatures
Publication Name
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Abstract
Group action based cryptography was formally proposed in the seminal paper of Brassard and Yung (Crypto 1990). Based on one-way group action, there is a well-known digital signature design based on the Goldreich–Micali–Widgerson (GMW) zero-knowledge protocol for the graph isomorphism problem and the Fiat–Shamir (FS) transformation. Recently, there is a revival of activities on group action based cryptography and the GMW-FS design, as witnessed by the schemes SeaSign (Eurocrypt 2019), CSI-FiSh (Asiacrypt 2019), LESS (Africacrypt 2020), ATFE (Eurocrypt 2022), and MEDS (Africacrypt 2023). The contributions of this paper are two-fold: the first is about the GMW-FS design in general, and the second is on the ATFE-GMW-FS scheme. First, we study the QROM security and ring signatures of the GMW-FS design. We distil properties of the underlying group action for the GMW-FS design to be secure in the quantum random oracle model (QROM). We also show that this design supports a (linkable) ring signature construction following the work of Beullens, Katsumata and Pintore (Asiacrypt 2020). Second, we apply the above results to support the security of the ATFE-GMW-FS scheme in the QROM model. We then describe a linkable ring signature scheme based on it, and provide an implementation of the ring signature scheme. Preliminary experiments suggest that our scheme is competitive among existing post-quantum ring signatures.
Open Access Status
This publication is not available as open access
Volume
14771 LNCS
First Page
227
Last Page
261
Funding Number
ERC-669891