Quantum Rewinding for IOP-Based Succinct Arguments
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909854825709568 |
|---|---|
| author | Chiesa, Alessandro Agnol, Marcel Dall Di, Zijing Guan, Ziyi Spooner, Nicholas |
| author_facet | Chiesa, Alessandro Agnol, Marcel Dall Di, Zijing Guan, Ziyi Spooner, Nicholas |
| contents | We analyze the post-quantum security of succinct interactive arguments constructed from interactive oracle proofs (IOPs) and vector commitment schemes. 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 collapsing. Our proof builds on and extends prior work on the post-quantum security of Kilians succinct interactive argument, which is instead based on probabilistically checkable proofs (PCPs). We introduce a new quantum rewinding strategy that works across any number of rounds. As a consequence of our results, we obtain standard-model post-quantum secure succinct arguments with the best asymptotic complexity known. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_05360 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quantum Rewinding for IOP-Based Succinct Arguments Chiesa, Alessandro Agnol, Marcel Dall Di, Zijing Guan, Ziyi Spooner, Nicholas Cryptography and Security Quantum Physics We analyze the post-quantum security of succinct interactive arguments constructed from interactive oracle proofs (IOPs) and vector commitment schemes. 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 collapsing. Our proof builds on and extends prior work on the post-quantum security of Kilians succinct interactive argument, which is instead based on probabilistically checkable proofs (PCPs). We introduce a new quantum rewinding strategy that works across any number of rounds. As a consequence of our results, we obtain standard-model post-quantum secure succinct arguments with the best asymptotic complexity known. |
| title | Quantum Rewinding for IOP-Based Succinct Arguments |
| topic | Cryptography and Security Quantum Physics |
| url | https://arxiv.org/abs/2411.05360 |