International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Online-Extractability in the Quantum Random-Oracle Model

Jelle Don , Centrum Wiskunde & Informatica (CWI)
Serge Fehr , Centrum Wiskunde & Informatica (CWI), Leiden University
Christian Majenz , Department of Applied Mathematics and Computer Science, Technical University of Denmark
Christian Schaffner , University of Amsterdam, QuSoft
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2022
Abstract: We show the following generic result: Whenever a quantum query algorithm in the quantum random-oracle model outputs a classical value t that is promised to be in some tight relation with H(x) for some x, then x can be efficiently extracted with almost certainty. The extraction is by means of a suitable simulation of the random oracle and works online, meaning that it is straightline, i.e., without rewinding, and on- the-fly, i.e., during the protocol execution and without disturbing it. The technical core of our result is a new commutator bound that bounds the operator norm of the commutator of the unitary operator that describes the evolution of the compressed oracle (which is used to simulate the random oracle above) and of the measurement that extracts x. We show two applications of our generic online extractability result. We show tight online extractability of commit-and-open Σ-protocols in the quantum setting, and we offer the first complete post-quantum security proof of the textbook Fujisaki-Okamoto transformation, i.e, without adjustments to facilitate the proof, including concrete security bounds.
Video from EUROCRYPT 2022
  title={Online-Extractability in the Quantum Random-Oracle Model},
  author={Jelle Don and Serge Fehr and Christian Majenz and Christian Schaffner},