@inproceedings{b9627696f5b5422fadcf7b72f23ca7ac,
title = "Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier",
abstract = "We prove that Kilian's four-message succinct argument system is post-quantum secure in the standard model when instantiated with any probabilistically checkable proof and any collapsing hash function (which in turn exist based on the post-quantum hardness of Learning with Errors). This yields the first post-quantum succinct argument system from any falsifiable assumption. At the heart of our proof is a new quantum rewinding procedure that enables a reduction to repeatedly query a quantum adversary for accepting transcripts as many times as desired. Prior techniques were limited to a constant number of accepting transcripts.",
keywords = "post-quantum cryptography, quantum rewinding, succinct arguments",
author = "Alessandro Chiesa and Fermi Ma and Nicholas Spooner and Mark Zhandry",
note = "Funding Information: We note, however, that if Kilian{\textquoteright}s protocol instantiated with a CRHF is not post-quantum secure, then it means that the CRHF is not collapsing. As shown by Zhandry [18], such a CRHF would yield strong cryptographic objects, namely “quantum lightning”, which have no known instantiations under well-studied assumptions. (More precisely, Zhandry [18] shows that non-collapsing CRHFs imply infinitely-often secure quantum lightning, a slightly weaker notion.) ACKNOWLEDGMENTS Part of this work was done while FM was visiting UC Berkeley and the Simons Institute for the Theory of Computing from Fall 2019 to Spring 2020. AC is supported by the Ethereum Foundation. FM thanks Justin Holmgren for helpful discussions. NS is supported by DARPA under Agreement No. HR00112020023. NS thanks Dominique Unruh for helpful discussions. Funding Information: Part of this work was done while FM was visiting UC Berkeley and the Simons Institute for the Theory of Computing from Fall 2019 to Spring 2020. AC is supported by the Ethereum Foundation. FM thanks Justin Holmgren for helpful discussions. NS is supported by DARPA under Agreement No. HR00112020023. NS thanks Dominique Unruh for helpful discussions. Publisher Copyright: {\textcopyright} 2022 IEEE.; 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021 ; Conference date: 07-02-2022 Through 10-02-2022",
year = "2022",
doi = "10.1109/FOCS52979.2021.00014",
language = "English (US)",
series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",
publisher = "IEEE Computer Society",
pages = "49--58",
booktitle = "Proceedings - 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021",
address = "United States",
}