Paper 2025/1998

Non-Adaptive One-Way to Hiding not only Implies Adaptive Quantum Reprogramming, but also Does Better

, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100085, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China

Jiangxia Ge, China Telecom Quantum Information Technology Group Co., Ltd

Rui Xue, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100085, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China

Xiaogang Zhou, China Telecom Quantum Information Technology Group Co., Ltd

Abstract

As three frequently used techniques for adaptive reprogramming in the QROM, the adaptive One-Way to Hiding (O2H) proposed by Unruh (CRYPTO 2014), the GHHM adaptive reprogramming proposed by Grilo et al. (ASIACRYPT 2021), and the Pan-Zeng adaptive reprogramming proposed by Pan and Zeng (PKC 2024), address different reprogramming scenarios, and do not appear to imply one another. A recent breakthrough by Jaeger (ASIACRYPT 2025) reveals a surprising connection: all three of these adaptive techniques can be implied by a non-adaptive reprogramming technique called Fixed-Permutation O2H (FP-O2H). Furthermore, Jaeger's result also improves the security bounds for Unruh's adaptive O2H and the Pan-Zeng adaptive reprogramming theorem. In this paper, we reconsider the implication between FP-O2H and GHHM adaptive reprogramming. We first introduce a variant of FP-O2H, called the Double-Oracle-Fixed-Permutation O2H (DOFP-O2H). Then, by applying this variant, we derive a tighter upper bound for the GHHM adaptive reprogramming. Thereby, our result complements Jaeger’s findings by addressing the final piece, showing that the non-adaptive O2H not only implies adaptive reprogramming in the QROM but also yields tighter upper bounds. In addition, a direct application of our tighter GHHM adaptive reprogramming yields a tighter \textsf{EUF-CMA} security proof of the Fiat–Shamir transform in the QROM: the security loss with respect to the number of signing queries q_s decreases from O(q_s) to O(\sqrt{q_s}). Furthermore, we reconsider the implication between FP-O2H and the ABKM permutation resampling proposed by Alagic et al. (EUROCRYPT 2022). By applying our DOFP-O2H, we reprove the ABKM permutation resampling theorem, and derive the same upper bound as that of Alagic et al. This result suggests that the FP-O2H not only can be applied to analyze the reprogramming in the QROM, but also has potential for analyzing reprogramming in the random permutation setting.

@misc{cryptoeprint:2025/1998,
      author = {Heming Liao and Jiangxia Ge and Rui Xue and Xiaogang Zhou},
      title = {Non-Adaptive One-Way to Hiding not only Implies Adaptive Quantum Reprogramming, but also Does Better},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1998},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1998}
}