Paper 2021/280

Online-Extractability in the Quantum Random-Oracle Model

Jelle Don, Serge Fehr, Christian Majenz, and Christian Schaffner


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 $\Sigma$-protocols in the quantum setting, and we offer the first non-asymptotic post-quantum security proof of the *textbook* Fujisaki-Okamoto transformation, i.e, without adjustments to facilitate the proof.

Available format(s)
Publication info
Preprint. MINOR revision.
QROMFujisaki-Okamotocommit-and-opensigma-protocolsonline extractabilitypost-quantum crypto
Contact author(s)
jelle don @ cwi nl
serge fehr @ cwi nl
christian majenz @ cwi nl
christian schaffner @ uva nl
2021-09-14: revised
2021-03-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jelle Don and Serge Fehr and Christian Majenz and Christian Schaffner},
      title = {Online-Extractability in the Quantum Random-Oracle Model},
      howpublished = {Cryptology ePrint Archive, Paper 2021/280},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.