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

摘要

We revisit recent works by Don, Fehr, Majenz and Schaffner and by Liu and Zhandry on the security of the Fiat-Shamir (FS) transformation of Σ-protocols in the quantum random oracle model (QROM). Two natural questions that arise in this context are: (1) whether the results extend to the FS 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 FS transformation of Σ-protocols is optimal up to a small constant factor. This extends to our new multi-round result, proving it tight up to a factor depending on the number of rounds only, i.e. is constant for constant-round interactive proofs.