Paper 2026/2370

Extract-Amplify-Measure: Single-Sided and Tight O2H with Applications to CCA Security in the Quantum Random Oracle Model

Abstract

The One-Way-to-Hiding (O2H) theorem is a useful tool for analyzing reprogramming in the quantum random oracle model (QROM). It bounds the distinguishing advantage by the probability $\epsilon$ that a one-wayness attacker finds the reprogrammed point. A sequence of works has improved the tightness of this theorem. Currently, the Measure-Rewind-Extract O2H (MRE-O2H) theorem proved by Ge et al. (ASIACRYPT 2024) achieves the tightest known upper bound of $O(\sqrt{q}\cdot\epsilon)$, where $q$ is the number of quantum queries. This theorem follows the Double-Sided idea introduced by Bindel et al. (TCC 2019), which requires the one-wayness attacker to access both the original and reprogrammed random oracles, thereby imposing stronger requirements on the reduction. Moreover, it incurs a $q$-dependent loss of $O(\sqrt{q})$. In this paper, we address these limitations by proving two Extract-Amplify-Measure (EAM) O2H theorems. First, we prove a Single-Sided EAM-O2H (SSEAM-O2H) theorem, which achieves the same $O(\sqrt{q}\cdot\epsilon)$ upper bound as the MRE-O2H theorem, while the resulting attacker only needs access to either the original or the reprogrammed random oracle, reducing the requirements on the underlying reduction. Second, we prove a Double-Sided EAM-O2H (DSEAM-O2H) theorem, which retains the Double-Sided idea used in the MRE-O2H theorem but removes the $q$-dependent loss, yielding a tight $O(\epsilon)$ upper bound. As applications, we revisit the security of several Fujisaki--Okamoto variants proposed by Hofheinz et al. (TCC 2017) in the QROM, namely $\textsf{U}^{\slashed{\bot}}$, $\mathsf{FO}^{\slashed{\bot}}$, $\mathsf{FO}^{\slashed{\bot}}_{m}$, $\mathsf{FO}^{\bot}$, and $\mathsf{FO}^{\bot}_{m}$, and obtain the following results: The \textsf{IND-CCA} security of $\textsf{U}^{\slashed{\bot}}$ can be reduced to the \textsf{OW-CPA} security of the underlying PKE scheme. Compared with the previous proofs by Bindel et al. (TCC 2019) and Kuchta et al. (EUROCRYPT 2020), we avoid both the square-root loss and the $q$-dependent loss in the underlying adversary's \textsf{OW-CPA} advantage. The \textsf{IND-CCA} security of $\mathsf{FO}^{\slashed{\bot}}$, $\mathsf{FO}^{\slashed{\bot}}_{m}$, $\mathsf{FO}^{\bot}$, and $\mathsf{FO}^{\bot}_{m}$ can be reduced to the \textsf{IND-CPA} security of the underlying PKE scheme. Compared with the previous proofs by Ge et al. (ASIACRYPT 2024), we reduce the $q$-dependent loss from $O(q^{1.5})$ to $O(q^{0.5})$. Assuming unique randomness recoverability, the \textsf{IND-CCA} security of $\mathsf{FO}^{\slashed{\bot}}$, $\mathsf{FO}^{\slashed{\bot}}_{m}$, $\mathsf{FO}^{\bot}$, and $\mathsf{FO}^{\bot}_{m}$ can be reduced to the \textsf{OW-CPA} security of the underlying PKE scheme. Compared with the previous proofs by Ge et al. (ASIACRYPT 2024), we avoid the $q$-dependent loss in the underlying adversary's \textsf{OW-CPA} advantage.