Paper 2022/1184

On digital signatures based on group actions: QROM security and ring signatures

Markus Bläser, Saarland University
Zhili Chen, University of Technology Sydney
Dung Hoang Duong, University of Wollongong
Antoine Joux, Helmholtz Center for Information Security
Ngoc Tuong Nguyen, University of Wollongong
Thomas Plantard, Nokia Bell Labs
Youming Qiao, University of Technology Sydney
Willy Susilo, University of Wollongong
Gang Tang, University of Technology Sydney
Abstract

Group action based cryptography was formally proposed in the seminal paper of Brassard and Yung (Crypto 1990). Based on oneway 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 in the group action framework. 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 prove 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Major revision. PQCrypto 2024
Keywords
QROMalternating trilinear formsring signaturesdigital signaturesisomorphism problems
Contact author(s)
mblaeser @ cs uni-saarland de
zhili chen @ student uts edu au
hduong @ uow edu au
joux @ cispa de
ntn807 @ uowmail edu au
thomas plantard @ nokia-bell-labs com
Youming Qiao @ uts edu au
wsusilo @ uow edu au
gang tang-1 @ student uts edu au
History
2024-04-18: last of 4 revisions
2022-09-09: received
See all versions
Short URL
https://ia.cr/2022/1184
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1184,
      author = {Markus Bläser and Zhili Chen and Dung Hoang Duong and Antoine Joux and Ngoc Tuong Nguyen and Thomas Plantard and Youming Qiao and Willy Susilo and Gang Tang},
      title = {On digital signatures based on group actions: {QROM} security and ring signatures},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1184},
      year = {2022},
      url = {https://eprint.iacr.org/2022/1184}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.