On Digital Signatures Based on Group Actions: QROM Security and Ring Signatures

Bläser, M; Chen, Z; Duong, DH; Joux, A; Nguyen, T; Plantard, T; Qiao, Y; Susilo, W; Tang, G

On Digital Signatures Based on Group Actions: QROM Security and Ring Signatures

Bläser, M Chen, Z Duong, DH Joux, A Nguyen, T Plantard, T Qiao, Y

Susilo, W Tang, G

Permalink

Publisher:: Springer Nature
Publication Type:: Chapter
Citation:: Post-Quantum Cryptography, 2024, 14771 LNCS, pp. 227-261
Issue Date:: 2024-01-01

Closed Access

	Filename	Description	Size
	978-3-031-62743-9_8.pdf	Published version	786.01 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Bläser, M
dc.contributor.author	Chen, Z
dc.contributor.author	Duong, DH
dc.contributor.author	Joux, A
dc.contributor.author	Nguyen, T
dc.contributor.author	Plantard, T
dc.contributor.author	Qiao, Y https://orcid.org/0000-0003-4334-1449
dc.contributor.author	Susilo, W
dc.contributor.author	Tang, G
dc.date.accessioned	2024-09-09T05:50:44Z
dc.date.available	2024-09-09T05:50:44Z
dc.date.issued	2024-01-01
dc.identifier.citation	Post-Quantum Cryptography, 2024, 14771 LNCS, pp. 227-261
dc.identifier.isbn	9783031627422
dc.identifier.uri	http://hdl.handle.net/10453/180763
dc.description.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.
dc.language	en
dc.publisher	Springer Nature
dc.relation	http://purl.org/au-research/grants/arc/DP200100950
dc.relation	http://purl.org/au-research/grants/arc/LP220100332
dc.relation.ispartof	Post-Quantum Cryptography
dc.relation.ispartofseries	Lecture Notes in Computer Science
dc.relation.isbasedon	10.1007/978-3-031-62743-9_8
dc.rights	info:eu-repo/semantics/closedAccess
dc.subject.classification	Artificial Intelligence & Image Processing
dc.subject.classification	46 Information and computing sciences
dc.title	On Digital Signatures Based on Group Actions: QROM Security and Ring Signatures
dc.type	Chapter
utslib.citation.volume	14771 LNCS
pubs.organisational-group	University of Technology Sydney
pubs.organisational-group	University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
pubs.organisational-group	University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
pubs.organisational-group	University of Technology Sydney/Strength - CQSI - Centre for Quantum Software and Information
pubs.organisational-group	University of Technology Sydney/All Manual Groups
pubs.organisational-group	University of Technology Sydney/All Manual Groups/Centre for Quantum Software and Information (QSI)
utslib.copyright.status	closed_access	*
dc.date.updated	2024-09-09T05:50:42Z
pubs.publication-status	Published
pubs.volume	14771 LNCS

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.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/180763