A
Menu
March 04, 2021 preprint Open access Aachen paper

Online-Extractability in the Quantum Random-Oracle Model

arXiv (Cornell University)

DOI: 10.48550/arxiv.2103.03085 Full text (OA) OpenAlex

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 non-asymptotic post-quantum security proof of the textbook Fujisaki-Okamoto transformation, i.e, without adjustments to facilitate the proof.

Authors 4

  1. Jelle Don

    Centrum Wiskunde & Informatica

    Affiliation as printed

    Centrum Wiskunde & Informatica (CWI) , Amsterdam , Netherlands

    [Centrum Wiskunde & Informatica]

  2. Serge Fehr Aachen Mathematical Institute

    Leiden University · Centrum Wiskunde & Informatica

    Affiliation as printed

    Centrum Wiskunde & Informatica (CWI) , Amsterdam , Netherlands

    Mathematical Institute , Leiden University , Netherlands

    [Centrum Wiskunde & Informatica]

  3. Christian Majenz

    Centrum Wiskunde & Informatica · QuSoft

    Affiliation as printed

    Centrum Wiskunde & Informatica (CWI) , Amsterdam , Netherlands

    QuSoft , Amsterdam , Netherlands

    [Centrum Wiskunde & Informatica]

  4. Christian Schaffner

    QuSoft · University of Amsterdam

    Affiliation as printed

    Institute for Logic, Language and Computation , University of Amsterdam , Amsterdam , Netherlands

    QuSoft , Amsterdam , Netherlands

    University of Amsterdam

Cited by 3 stored of 3

3 results

No patents citing this paper on Lens.org (checked 2026-10-11).

References 29