Paper 2020/282

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

Jelle Don, Serge Fehr, and Christian Majenz

Abstract

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in CRYPTO 2020
Keywords
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
History
2022-03-07: last of 4 revisions
2020-03-04: received
See all versions
Short URL
https://ia.cr/2020/282
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/282,
      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{https://eprint.iacr.org/2020/282}},
      url = {https://eprint.iacr.org/2020/282}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.