On the necessity of collapsing for post-quantum and quantum commitments

Marcel Dall'Agnol, Nicholas Spooner

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

Abstract

Collapse binding and collapsing were proposed by Unruh (Eurocrypt '16) as post-quantum strengthenings of computational binding and collision resistance, respectively. These notions have been very successful in facilitating the "lifting" of classical security proofs to the quantum setting. A basic and natural question remains unanswered, however: Are they the weakest notions that suffice for such lifting? In this work we answer this question in the affirmative by giving a classical commit-And-open protocol which is post-quantum secure if and only if the commitment scheme (resp. hash function) used is collapse binding (resp. collapsing). We also generalise the definition of collapse binding to quantum commitment schemes, and prove that the equivalence carries over when the sender in this commit-And-open protocol communicates quantum information. As a consequence, we establish that a variety of "weak" binding notions (sum binding, CDMS binding and unequivocality) are in fact equivalent to collapse binding, both for post-quantum and quantum commitments. Finally, we prove a "win-win" result, showing that a post-quantum computationally binding commitment scheme that is not collapse binding can be used to build an equivocal commitment scheme (which can, in turn, be used to build one-shot signatures and other useful quantum primitives). This strengthens a result due to Zhandry (Eurocrypt '19) showing that the same object yields quantum lightning.

Original languageEnglish (US)
Title of host publication18th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2023
EditorsOmar Fawzi, Michael Walter
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772839
DOIs
StatePublished - Jul 2023
Externally publishedYes
Event18th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2023 - Aveiro, Portugal
Duration: Jul 24 2023Jul 28 2023

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume266
ISSN (Print)1868-8969

Conference

Conference18th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2023
Country/TerritoryPortugal
CityAveiro
Period7/24/237/28/23

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Commitment schemes
  • Hash functions
  • Quantum cryptography
  • Quantum rewinding

Fingerprint

Dive into the research topics of 'On the necessity of collapsing for post-quantum and quantum commitments'. Together they form a unique fingerprint.

Cite this