Quantum Rewinding for IOP-Based Succinct Arguments

We analyze the post-quantum security of succinct interactive arguments constructed from interactive oracle proofs (IOPs) and vector commitment schemes. Specifically, we prove that an interactive variant of the BCS transformation is secure in the standard model against quantum adversaries when the vector commitment scheme is collapse binding. Prior work established the post-quantum security of Kilian’s succinct interactive argument, a special case of the BCS transformation for one-message IOPs (i.e., PCPs). That analysis is inherently limited to one message because the reduction, like all prior quantum rewinding reductions, aims to extract classical information (a PCP string) from the quantum argument adversary. Our reduction overcomes this limitation by instead extracting a quantum algorithm that implements an IOP adversary; representing such an adversary classically may in general require exponential complexity. Along the way we define collapse position binding, which we propose as the “correct” definition of collapse binding for vector commitment schemes, eliminating shortcomings of prior definitions. As an application of our results, we obtain post-quantum secure succinct arguments, in the standard model (no oracles), with the best asymptotic complexity known.