Paper 2022/1184
On digital signatures based on group actions: QROM security and ring signatures
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)
- 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
-
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} }