Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier

Alessandro Chiesa, Fermi Ma, Nicholas Spooner, Mark Zhandry

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationProceedings - 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021
PublisherIEEE Computer Society
Pages49-58
Number of pages10
ISBN (Electronic)9781665420556
DOIs
StatePublished - 2022
Externally publishedYes
Event62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021 - Virtual, Online, United States
Duration: Feb 7 2022Feb 10 2022

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2022-February
ISSN (Print)0272-5428

Conference

Conference62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021
Country/TerritoryUnited States
CityVirtual, Online
Period2/7/222/10/22

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • post-quantum cryptography
  • quantum rewinding
  • succinct arguments

Fingerprint

Dive into the research topics of 'Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier'. Together they form a unique fingerprint.

Cite this