Paper 2026/1347

Revisiting the Quantum Indifferentiability of Merkle-Damgård: Proof Limitations and Optimal Consistency

Abstract

The quantum indifferentiability of the Merkle-Damgård (MD) domain extender is a foundational problem in post-quantum cryptography. Recently, Gorjan et al. identified critical flaws in existing consistency proofs for this construction, invalidating prior security guarantees. Quantum indifferentiability proofs typically reduce to two oracle-indistinguishability games: the indistinguishability game and the consistency game. To analyze the systems arising in these games, we formalize and generalize Zhandry's compressed oracle proof technique into a modular quantum game-playing framework for systems constructed from random functions. On the positive side, we develop an error-propagation technique within our framework to track coherence penalties and bad sampling branches for the consistency game. This yields a tight consistency bound of $O(q_s^{3/2}/2^{n/2})$, matching the optimal complexity of generic quantum collision attacks. Benefiting from the same formalization, we also identify a fundamental obstruction in the indistinguishability game---a gap also present in Zhandry's original proof. Specifically, under sequential adaptive queries, the simulated quantum state inevitably leaks into the ``bad database'' subspace and yields a lower bound on the corresponding oracle deviation. This clarifies why completing the full quantum indifferentiability proof requires additional ideas.