Unique Insights into Compressed Permutation Oracles
Explore the world of compressed permutation oracles in quantum computing, with a focus on CFO and CPO models. Delve into the quantum random oracle model, quantum random oracle techniques, the standard oracle, and more. Discover how these concepts are transforming cryptographic practices for post-quantum security.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Towards compressed permutation oracles Dominique Unruh RWTH Aachen University of Tartu
Overview Quantum Random Oracle Compressed (function) oracles (CFO) Compressed permutation oracles (CPO) Main result: towards CPO Can t edit this in PPT Android !!! Titel der Pr sentation | Name des Vortragenden | Organisationseinheit | 00.00.2000 | Die Fu zeile bietet Platz f r einen Text ber 3 Zeilen | Die Fu zeile bietet Platz f r einen Text ber 3 Zeilen | Die Fu zeile bietet Platz f r 3 Zeilen
Quantum random oracle model, QROM Analogue to random oracle in classical crypto, for (post-)quantum crypto Heuristic for modeling hash functions Random function, adversary has superposition access Titel der Pr sentation | Name des Vortragenden | Organisationseinheit | 00.00.2000 | Die Fu zeile bietet Platz f r einen Text ber 3 Zeilen | Die Fu zeile bietet Platz f r einen Text ber 3 Zeilen | Die Fu zeile bietet Platz f r 3 Zeilen
Quantum random oracle techniques Much harder to use than classical QROM Small-range distributions [Zhandry] One-way to hiding [Unruh] 2q-wise functions [Zhandry] Random function = random permutation [Zhandry] Compressed oracles [Zhandry] Titel der Pr sentation | Name des Vortragenden | Organisationseinheit | 00.00.2000 | Die Fu zeile bietet Platz f r einen Text ber 3 Zeilen | Die Fu zeile bietet Platz f r einen Text ber 3 Zeilen | Die Fu zeile bietet Platz f r 3 Zeilen
The standard oracle, StO Keep function in superposition Register Hx contains the output H(x). Initial state: Query: Indistinguishable from random function Titel der Pr sentation | Name des Vortragenden | Organisationseinheit | 00.00.2000 | Die Fu zeile bietet Platz f r einen Text ber 3 Zeilen | Die Fu zeile bietet Platz f r einen Text ber 3 Zeilen | Die Fu zeile bietet Platz f r 3 Zeilen
Compressed function oracle, CFO Decompression operation: Oracle: Indististinguishable from StO Titel der Pr sentation | Name des Vortragenden | Organisationseinheit | 00.00.2000 | Die Fu zeile bietet Platz f r einen Text ber 3 Zeilen | Die Fu zeile bietet Platz f r einen Text ber 3 Zeilen | Die Fu zeile bietet Platz f r 3 Zeilen
CFO features Query changes only queried H-output. Consequences: Superposition of states that are in most Hx Partial functions of size <= q Efficient representation Log of queries Titel der Pr sentation | Name des Vortragenden | Organisationseinheit | 00.00.2000 | Die Fu zeile bietet Platz f r einen Text ber 3 Zeilen | Die Fu zeile bietet Platz f r einen Text ber 3 Zeilen | Die Fu zeile bietet Platz f r 3 Zeilen
Use-view vs. make-view Two use-cases of CFO: Use-view / make-view Use-view: Have construction using a hash function, model hash function using CFO Make-view: Have construction implementing a random function model random function using CFO (a) Prove C(H) indistinguishable from CFO (b) Use: CFO indistinguishable from RF Titel der Pr sentation | Name des Vortragenden | Organisationseinheit | 00.00.2000 | Die Fu zeile bietet Platz f r einen Text ber 3 Zeilen | Die Fu zeile bietet Platz f r einen Text ber 3 Zeilen | Die Fu zeile bietet Platz f r 3 Zeilen
Permutation oracles why? CFO models random functions, sometimes need random invertible permutations Modeling ideal ciphers (use-view) Proving Luby-Rackoff (make-view) Proving SHA3 (use-view) CFO analysis inherently relies on: H-outputs independently distributed Very elusive!!! Titel der Pr sentation | Name des Vortragenden | Organisationseinheit | 00.00.2000 | Die Fu zeile bietet Platz f r einen Text ber 3 Zeilen | Die Fu zeile bietet Platz f r einen Text ber 3 Zeilen | Die Fu zeile bietet Platz f r 3 Zeilen
Compressed permutation oracle, CPO Random invertible permutation: H and H-1 Oracle state: like CFO: Two queries: CFO FLIP o CFO o FLIP Titel der Pr sentation | Name des Vortragenden | Organisationseinheit | 00.00.2000 | Die Fu zeile bietet Platz f r einen Text ber 3 Zeilen | Die Fu zeile bietet Platz f r einen Text ber 3 Zeilen | Die Fu zeile bietet Platz f r 3 Zeilen
CPO features Each query extends domain by <= 1 CFO: we already know FLIP: preserves size Reasoning about invariants Compressed representation, efficiency Indistinguishable from random permutation ????? Titel der Pr sentation | Name des Vortragenden | Organisationseinheit | 00.00.2000 | Die Fu zeile bietet Platz f r einen Text ber 3 Zeilen | Die Fu zeile bietet Platz f r einen Text ber 3 Zeilen | Die Fu zeile bietet Platz f r 3 Zeilen
Main result Recall make-view: Want to implement random permutation E.g., Luby-Rackoff indistinguishable from random perm. Proof steps: (a) C(H) indistinguishable CPO (b) CPO indistinguishable random perm. Main theorem: Once you prove (a), (b) follows for free! Titel der Pr sentation | Name des Vortragenden | Organisationseinheit | 00.00.2000 | Die Fu zeile bietet Platz f r einen Text ber 3 Zeilen | Die Fu zeile bietet Platz f r einen Text ber 3 Zeilen | Die Fu zeile bietet Platz f r 3 Zeilen
Proof sketch // symmetry // by (a) // C(H) perm, f random Titel der Pr sentation | Name des Vortragenden | Organisationseinheit | 00.00.2000 | Die Fu zeile bietet Platz f r einen Text ber 3 Zeilen | Die Fu zeile bietet Platz f r einen Text ber 3 Zeilen | Die Fu zeile bietet Platz f r 3 Zeilen
Funders Titel der Pr sentation | Name des Vortragenden | Organisationseinheit | 00.00.2000 | Die Fu zeile bietet Platz f r einen Text ber 3 Zeilen | Die Fu zeile bietet Platz f r einen Text ber 3 Zeilen | Die Fu zeile bietet Platz f r 3 Zeilen
