Paper 2026/2777

Tamper-Resilient Quantum Key Encapsulation with Coherent Ciphertexts from qOWFs in the QROM

Abstract

Kitagawa et al. (CRYPTO 2024) constructed the first tamper-resilient, chosen-ciphertext-secure public-key encryption from quantum-secure one-way functions (qOWFs). However, their construction assumes authenticated classical channels and measures intermediate signed-phase states to produce classical ciphertexts. Therefore we ask whether coherent quantum ciphertexts can support active security and certified deletion over unauthenticated classical and quantum channels. We construct the first tamper-resilient quantum key-encapsulation mechanism (QKEM) from qOWFs with coherent quantum ciphertexts and genuine validity-feedback confidentiality in the quantum random-oracle model. Our scheme, designated Signed-Fourier QKEM, retains signed coherence through honest encapsulation to form a state-consuming quantum ciphertext. Aside from an authentic root verification key, all transmitted classical metadata and quantum registers are subject to arbitrary adversarial tampering and entanglement. With one quantum public key per independent signing domain and a challenge serial unused in pre-challenge decapsulation queries, we prove session-key confidentiality under genuine different-header decapsulation, including queries sharing the challenge serial, and genuine same-header validity feedback. We also establish fixed-header key robustness against adaptive decapsulation attacks, bounding wrong-key acceptance by a negligible probability. Furthermore, our scheme provides publicly verifiable computational certified deletion, protecting session-key privacy against subsequent, complete exposure of the receiver's secret state. Finally, composing our QKEM with a classical one-time private data encapsulation mechanism yields header-restricted chosen-ciphertext confidentiality for arbitrary polynomial-length messages.