Paper 2026/1064

Post-Quantum Security of Practical Correlation-Robust Hashing

Haruhisa Kosuge, NTT Social Informatics Laboratories

Keita Xagawa, Technology Innovation Institute

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. The most commonly analyzed constructions are the Matyas-Meyer-Oseas (MMO) construction and its variants, such as \(\widehat{\mathsf{MMO}}\). Existing analyses of such constructions, however, are classical and do not justify security against quantum adversaries that can make superposition queries to the underlying random permutation or ideal cipher. We analyze the post-quantum security of these block-cipher-based correlation-robust 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 two MMO variants, the \(\widehat{\mathsf{MMO}}\) and $\mathsf{EncFF}$ (Encryption with Feed-Forward) constructions. 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}\). They also yield security in the quantum random permutation model (QRPM) as a special case. Consequently, CR-type hash functions used in various existing protocol analyses can be instantiated with the covered MMO-type constructions while preserving the corresponding hash-replacement arguments against quantum adversaries in the QICM/QRPM. This applies to representative analyses of OT extension, (correlated) GGM trees, certain distributed point/comparison function constructions, and half-gates garbling. When the remaining components are post-quantum secure or are modeled as ideal functionalities, this yields post-quantum security of the resulting protocol instantiations under the corresponding composition theorem. Thus, our results provide post-quantum justification for practical block-cipher-based correlation-robust hashing in many efficient secure computation protocols. Technically, our proof reduces CR-type security to the multi-key security of an Even-Mansour-like tweakable block cipher and then analyzes it using reprogramming-and-resampling techniques building on the work of Alagic et al.~(Eurorcrypt 2022). To handle adaptive key leakage, we introduce the conditional min-entropy with leakage (cmel) advantage, a quantity that isolates the information-theoretic entropy loss caused by leakage from the quantum ideal-cipher analysis. Without leakage, our bounds guarantee security up to roughly \(q_E,q_C \ll 2^{\rho/3}\), where \(q_E\) and \(q_C\) are the numbers of primitive and construction queries and \(\rho\) is the min-entropy of the secret shift; this query complexity is tight.

@misc{cryptoeprint:2026/1064,
      author = {Akinori Hosoyamada and Haruhisa Kosuge and Keita Xagawa},
      title = {Post-Quantum Security of Practical Correlation-Robust Hashing},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/1064},
      year = {2026},
      url = {https://eprint.iacr.org/2026/1064}
}