Paper 2022/1058

Evaluating the Security of Merkle-Damgård Hash Functions and Combiners in Quantum Settings

Zhenzhen Bao, Tsinghua University, Nanyang Technological University
Jian Guo, Nanyang Technological University
Shun Li, Shanghai Jiao Tong University, Nanyang Technological University
Phuong Pham, Nanyang Technological University

In this work, we evaluate the security of Merkle-Damgård (MD) hash functions and their combiners (XOR and concatenation combiners) in quantum settings. Two main quantum scenarios are considered, including the scenario where a substantial amount of cheap quantum random access memory (qRAM) is available and where qRAM is limited and expensive to access. We present generic quantum attacks on the MD hash functions and hash combiners, and carefully analyze the complexities under both quantum scenarios. The considered securities are fundamental requirements for hash functions, including the resistance against collision and (second-)preimage. The results are consistent with the conclusions in the classical setting, that is, the considered resistances of the MD hash functions and their combiners are far less than ideal, despite the significant differences in the expected security bounds between the classical and quantum settings. Particularly, the generic attacks can be improved significantly using quantum computers under both scenarios. These results serve as an indication that classical hash constructions require careful security re-evaluation before being deployed to the post-quantum cryptography schemes.

Available format(s)
Attacks and cryptanalysis
Publication info
Published elsewhere. NSS 2022
Merkle-DamgårdHash CombinerXORConcatenationQuantumGeneric Attack
Contact author(s)
zzbao @ tsinghua edu cn
guojian @ ntu edu sg
shun li @ ntu edu sg
pham0079 @ e ntu edu sg
2023-01-09: revised
2022-08-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {Zhenzhen Bao and Jian Guo and Shun Li and Phuong Pham},
      title = {Evaluating the Security of Merkle-Damgård Hash Functions and Combiners in Quantum Settings},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1058},
      year = {2022},
      doi = {10.1007/978-3-031-23020-2_39},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.