TY - GEN
T1 - Online-Extractability in the Quantum Random-Oracle Model
AU - Don, Jelle
AU - Fehr, Serge
AU - Majenz, Christian
AU - Schaffner, Christian
N1 - Publisher Copyright:
© 2022, International Association for Cryptologic Research.
PY - 2022
Y1 - 2022
N2 - We show the following generic result: When 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 (almost) 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.
AB - We show the following generic result: When 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 (almost) 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.
U2 - 10.1007/978-3-031-07082-2_24
DO - 10.1007/978-3-031-07082-2_24
M3 - Article in proceedings
AN - SCOPUS:85132108721
SN - 9783031070815
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 677
EP - 706
BT - Proceedings of 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques
A2 - Dunkelman, Orr
A2 - Dziembowski, Stefan
PB - Springer
T2 - 41<sup>st</sup> Annual International Conference on the Theory and Applications of Cryptographic Techniques
Y2 - 30 May 2022 through 3 June 2022
ER -