Paper 2020/282

The Measure-and-Reprogram Technique 2.0: Multi-Round Fiat-Shamir and More

Jelle Don, Serge Fehr, and Christian Majenz


We revisit recent works by Don, Fehr, Majenz and Schaffner and by Liu and Zhandry on the security of the Fiat-Shamir transformation of $\Sigma$-protocols in the quantum random oracle model (QROM). Two natural questions that arise in this context are: (1) whether the results extend to the Fiat-Shamir transformation of *multi-round* interactive proofs, and (2) whether Don et al.'s $O(q^2)$ loss in security is optimal. Firstly, we answer question (1) in the affirmative. As a byproduct of solving a technical difficulty in proving this result, we slightly improve the result of Don et al., equipping it with a cleaner bound and an even simpler proof. We apply our result to digital signature schemes showing that it can be used to prove strong security for schemes like MQDSS in the QROM. As another application we prove QROM-security of a non-interactive OR proof by Liu, Wei and Wong. As for question (2), we show via a Grover-search based attack that Don et al.'s quadratic security loss for the Fiat-Shamir transformation of $\Sigma$-protocols is optimal up to a small constant factor. This extends to our new multi-round result, proving it tight up to a factor that depends on the number of rounds only, i.e. is constant for any constant-round interactive proof.

Note: Fixed a few minor errors.

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in CRYPTO 2020
Fiat-ShamirQROMpost-quantumzero-knowledgemulti-round interactive proofsNIZKidentification protocolsquantum random-oracle model
Contact author(s)
jelle don @ cwi nl
serge fehr @ cwi nl
c majenz @ uva nl
2022-03-07: last of 4 revisions
2020-03-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jelle Don and Serge Fehr and Christian Majenz},
      title = {The Measure-and-Reprogram Technique 2.0: Multi-Round Fiat-Shamir and More},
      howpublished = {Cryptology ePrint Archive, Paper 2020/282},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.