Suppose a prover computes a non-interactive proof which is composed of $k$ parallel repetitions of a sigma protocol with binary challenges (and knowledge error $\frac{1}{2}$), composed in parallel and transformed into a non-interactive proof by Fiat-Shamir.

The verifier samples a random subset of $m$-out-of-$k$ of the repetitions and verifies them. They accept if the chosen subset of repetitions are accepted.

A forger does not know which repetitions are verified, only that they are chosen uniformly at random.

Are there any works that discuss the soundness implications of only verifying a random subset of parallel repetitions? This is particularly of interest since a verifier may save in the verification costs by only verifying part of the proof.

Some thoughts: A malicious prover who wishes to mount an attack may compute $k-1$ of the commitment phases (as is done in the ZK simulator), and enumerating the last one until they yield a good hash that satisfies $m$ challenge bits. This can be achieved for small $m$ efficiently but succeeds with very low likelihood. There is also some kind of computational trade-off here for choosing a sufficient number of challenge bits that are 'good' in the sense that the verification succeeds for the corresponding repetitions, and the probability that the verifier selects a subset from the repetitions that are only 'good'.

  • $\begingroup$ It would certainly still be sound, but it's unclear that there would be any advantage compared to just sending $m$ proofs. If you want the verifier to put in less work than the prover, you should look into succinct proofs. $\endgroup$
    – lamontap
    Commented Sep 12, 2023 at 19:56
  • $\begingroup$ I'm well aware of succinct proofs. I think it is definitely better than sending $m$ proofs, but for small $m$ I still think it is not secure, which is why I am asking about it. $\endgroup$
    – Lev
    Commented Sep 12, 2023 at 21:14


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.