Paper 2022/786

On the necessity of collapsing

Marcel Dall'Agnol, University of Warwick
Nicholas Spooner, University of Warwick
Abstract

Collapsing and collapse binding were proposed by Unruh (Eurocrypt '16) as post-quantum strengthenings of collision resistance and computational binding (respectively). These notions have been very successful in facilitating the "lifting" of classical security proofs to the quantum setting. A natural question remains, however: is collapsing is the weakest notion that suffices 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). This result also establishes that a variety of "weaker" post-quantum computational binding notions (sum binding, CDMS binding and unequivocality) are in fact equivalent to collapse binding. Finally, we establish a "win-win" result, showing that a post-quantum collision resistant hash function that is not collapsing can be used to build an equivocal hash function (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. For this result we make use of recent quantum rewinding techniques.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
quantum commitment hash function collapsing
Contact author(s)
msagnol @ pm me
nicholas spooner @ warwick ac uk
History
2022-06-20: approved
2022-06-18: received
See all versions
Short URL
https://ia.cr/2022/786
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/786,
      author = {Marcel Dall'Agnol and Nicholas Spooner},
      title = {On the necessity of collapsing},
      howpublished = {Cryptology ePrint Archive, Paper 2022/786},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/786}},
      url = {https://eprint.iacr.org/2022/786}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.