Paper 2022/248

Collapseability of Tree Hashes

Aldo Gunsing and Bart Mennink


One oft-endeavored security property for cryptographic hash functions is collision resistance: it should be computationally infeasible to find distinct inputs $x,x'$ such that $H(x) = H(x')$, where $H$ is the hash function. Unruh (EUROCRYPT 2016) proposed collapseability as its quantum equivalent. The Merkle-Damgård and sponge hashing modes have recently been proven to be collapseable under the assumption that the underlying primitive is collapseable. These modes are inherently sequential. In this work, we investigate collapseability of tree hashing. We first consider fixed length tree hashing modes, and derive conditions under which their collapseability can be reduced to the collapseability of the underlying compression function. Then, we extend the result to two methods for achieving variable length hashing: tree hashing with domain separation between message and chaining value, and tree hashing with length encoding at the end of the tree. The proofs are performed using the collapseability composability framework of Fehr (TCC 2018), that allows us to discard of deeply technical quantum details and to focus on proper composition of the tree hashes from their compression function.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. PQCrypto 2020
collapseabilitycollision resistancetree hashingcomposition
Contact author(s)
aldo gunsing @ ru nl
2022-03-02: received
Short URL
Creative Commons Attribution


      author = {Aldo Gunsing and Bart Mennink},
      title = {Collapseability of Tree Hashes},
      howpublished = {Cryptology ePrint Archive, Paper 2022/248},
      year = {2022},
      doi = {10.1007/978-3-030-44223-1_28},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.