Paper 2022/1184

On digital signatures based on isomorphism problems: QROM security and ring signatures

Zhili Chen, University of Technology Sydney
Dung Hoang Duong, University of Wollongong
Ngoc Tuong Nguyen, University of Wollongong
Youming Qiao, University of Technology Sydney
Willy Susilo, University of Wollongong
Gang Tang, University of Technology Sydney

At Eurocrypt 2022, Tang et al proposed a practical digital signature scheme in the context of post-quantum cryptography. The construction of that scheme is based on the assumed hardness of the alternating trilinear form equivalence problem (ATFE), the Goldreich-Micali-Widgerson (GMW) zero-knowledge protocol for graph isomorphism, and the Fiat-Shamir (FS) transformation. We refer to that scheme as the ATFE-GMW-FS scheme. The security of the ATFE-GMW-FS scheme was only proved in the random oracle model (ROM), and its security in the quantum random oracle model (QROM) was left as an open problem. In this paper, we study the ATFE-GMW-FS scheme from two perspectives, namely the QROM security and (linkable) ring signature schemes. First, we provide two approaches of proving its QROM security, based on the perfect unique response property and lossy identification schemes, respectively. Second, we design (linkable) ring signatures based on the ATFE-GMW-FS scheme, inspired by a recent result of Beullens, Katsumata and Pintore (Asiacrypt 20) on isogeny-based cryptography.

Note: Preliminary version

Available format(s)
Public-key cryptography
Publication info
QROM alternating trilinear forms ring signatures digital signatures isomorphism problems
Contact author(s)
zhili chen @ student uts edu au
hduong @ uow edu au
ntn807 @ uowmail edu au
Youming Qiao @ uts edu au
wsusilo @ uow edu au
gang tang-1 @ student uts edu au
2022-09-09: approved
2022-09-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Zhili Chen and Dung Hoang Duong and Ngoc Tuong Nguyen and Youming Qiao and Willy Susilo and Gang Tang},
      title = {On digital signatures based on isomorphism problems: QROM security and ring signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1184},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.