Cryptology ePrint Archive: Report 2020/282

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

Jelle Don and 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.

Category / Keywords: public-key cryptography / Fiat-Shamir, QROM, post-quantum, zero-knowledge, multi-round interactive proofs, NIZK, identification protocols, quantum random-oracle model

Original Publication (with minor differences): IACR-CRYPTO-2020

Date: received 3 Mar 2020, last revised 7 Mar 2022

Contact author: jelle don at cwi nl, serge fehr at cwi nl, c majenz at uva nl

Available format(s): PDF | BibTeX Citation

Note: Fixed a few minor errors.

Version: 20220307:115027 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]