Paper 2026/1064

Post-Quantum Security of Practical Correlation-Robust Hashing

Abstract

Correlation-robust (CR) hashing and its variants are central components in efficient secure-computation protocols, including OT extension, garbled-circuit optimizations such as Free-XOR and half-gates, and GGM-style tree constructions. In practice, these hashes are typically instantiated from block ciphers such as AES. Prominent constructions include the Matyas-Meyer-Oseas (MMO) construction and its variants such as \(\widehat{\mathsf{MMO}}\). Existing analyses, however, are classical and do not cover quantum adversaries with superposition access to the underlying random permutation or ideal cipher. We establish post-quantum security for these practical block-cipher-based CR hashes. In the quantum ideal cipher model (QICM), we prove multi-user tweakable correlation robustness with leakage (mTCRL) for the MMO construction, and multi-user tweakable circular correlation robustness with leakage (mTCCRL) for \(\widehat{\mathsf{MMO}}\) and the Encryption-with-Feed-Forward ($\mathsf{EncFF}$) construction. These results also imply the corresponding leakage-free and single-user guarantees: CR and TCR for MMO, and CR, CCR, TCR, and TCCR for \(\widehat{\mathsf{MMO}}\) and \(\mathsf{EncFF}\). Security in the quantum random permutation model (QRPM) follows as a special case. We further verify that, in the QICM/QRPM, the above MMO-type constructions securely instantiate CR-type hashes used in various existing protocol analyses. This covers several representative analyses involving OT extension, half-gates garbling, (correlated) GGM trees, and certain distributed point/comparison function constructions. When the remaining components are post-quantum secure or modeled as ideal functionalities, the resulting protocol instantiations are post-quantum secure in the corresponding model. Technically, our proof relies on the reprogramming-and-resampling technique of Alagic et al.~(Eurocrypt 2022). To handle adaptive key leakage, as needed for some malicious OT-extension analyses, we introduce the conditional min-entropy with leakage (cmel) advantage, which separates leakage-induced entropy loss from the quantum ideal-cipher analysis. Without leakage, our bounds guarantee security up to roughly \(2^{\rho/3}\) queries, where \(\rho\) is the min-entropy of the secret shift.