Paper 2025/947

Quantum Rewinding for IOP-Based Succinct Arguments

Alessandro Chiesa, École Polytechnique Fédérale de Lausanne
Marcel Dall'Agnol, Princeton University
Zijing Di, École Polytechnique Fédérale de Lausanne
Ziyi Guan, École Polytechnique Fédérale de Lausanne
Nicholas Spooner, Cornell University
Abstract

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*.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
succinct argumentspost-quantum securityquantum rewinding
Contact author(s)
alessandro chiesa @ epfl ch
dallagnol @ princeton edu
zijing di @ epfl ch
ziyi guan @ epfl ch
nspooner @ cornell edu
History
2025-05-29: revised
2025-05-24: received
See all versions
Short URL
https://ia.cr/2025/947
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/947,
      author = {Alessandro Chiesa and Marcel Dall'Agnol and Zijing Di and Ziyi Guan and Nicholas Spooner},
      title = {Quantum Rewinding for {IOP}-Based Succinct Arguments},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/947},
      year = {2025},
      url = {https://eprint.iacr.org/2025/947}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.