Paper 2026/128
The Impossibility of Post-Quantum Public Indifferentiability for Merkle-Damgard
Abstract
The Merkle-Damgård construction (in its strengthened form as used in SHA-256 and SHA-512, the untruncated members of SHA-2) is not classically indifferentiable from a Variable-Input-Length (VIL) random oracle because of the length-extension attack. Nevertheless, Dodis, Ristenpart, and Shrimpton showed that Merkle-Damgård is publicly indifferentiable, a weaker notion that still justifies replacing a VIL random oracle by Merkle-Damgård in many security proofs when all inputs to a random oracle are public (e.g., Fiat-Shamir and full-domain-hash signatures). In this paper, we show that this replacement fails in the post-quantum setting: (Strengthened) Merkle-Damgård is not publicly indifferentiable from a VIL random oracle against quantum distinguishers with superposition access to the underlying primitive (while construction queries remain classical), even if the compression function is ideally random. We first formalize post-quantum public indifferentiability so that the corresponding composition theorem extends to the quantum random oracle model. We also introduce a post-quantum version of sequential indifferentiability, an even weaker notion. We then prove that (strengthened) Merkle-Damgård satisfies neither notion by showing that an explicit quantum distinguisher achieves non-negligible advantage against any efficient simulator, using Zhandry's compressed-oracle technique. We thus obtain an explicit, conjecture-free separation between an indifferentiability-style notion in the classical setting and its post-quantum analogue.
Note: minor changes
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- A major revision of an IACR publication in CRYPTO 2026
- Keywords
- Merkle-Damgardpost-quantum securitypublic indifferentiabilitysequential indifferentiability
- Contact author(s)
- akinori hosoyamada @ ntt com
- History
- 2026-06-05: last of 2 revisions
- 2026-01-27: received
- See all versions
- Short URL
- https://ia.cr/2026/128
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/128,
author = {Akinori Hosoyamada},
title = {The Impossibility of Post-Quantum Public Indifferentiability for Merkle-Damgard},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/128},
year = {2026},
url = {https://eprint.iacr.org/2026/128}
}
