Paper 2025/947
Quantum Rewinding for IOP-Based Succinct Arguments
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
-
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} }