Exploring Post-Quantum Cryptography and Constructive Reductions
Delve into the realm of post-quantum cryptography through an insightful journey of constructive reductions, rethinking cryptography assumptions, and the relationship between classical and post-quantum regimes. Discover the challenges, advancements, and goals in the quest for durable cryptographic algorithms that withstand quantum adversaries.
Uploaded on Sep 13, 2024 | 1 Views
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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Constructive Post-quantum Reductions Yael Kalai MSR/MIT Nir Bitansky TAU Zvika Brakerski Weizmann *Some slides inspired by Zvika
Post-quantum Cryptography classical protocol/scheme P2 P1 quantum adversary A A
Rethinking Cryptography Assumptions lattice instead of Factoring Adversary interface quantum vs classical signing oracle? Reductions OWFs still imply all symmetric key crypto?
(Security) Reductions A A breaks P P e.g. PRG R R breaks Q Q e.g. OWF/LWE Breaking P (e.g. PRG) is no easier than breaking Q (e.g. OWF)
Can classical reductions be lifted to post-quantum regime? Most classical reductions treat A as a black box .
Problematic in Interactive Setting A A ? P disturbed R R Q interactive P BB-reducible to LWE, but quantumly broken [BCMVV18]
Our Focus: Non-interactive Primitives/Assumptions A A A A A A A A reduction execution R R
Quantum Auxiliary Input A A A A A A A A ? ? ? ? ? ? ? R R Where does ? come from? - Expensive preprocessing - Intermediate state in a protocol - Friendly advice from aliens Auxiliary input state disturbed
Just Copy the State? A A A A A A A A ? ? ? ? R R Non-constructive Quantum cloning impossible!
Goal: Goal: Constructive Reductions A A R R breaks Q A A ? breaks P ? Win-Win: broken scheme explicit algorithmic advance Targeted also classically (uniform reductions) [Bellare, Rogaway] Goal II: Goal II: Durability, new algorithm should work forever.
Results Lifting large class of classical reductions Any R from breaking Q to breaking P such that: - R is black box - R is non-adaptive - P is a decision assumption (e.g. PRG) or has few solutions (e.g Injective OWF) Resulting post-quantum reduction is constructive and durable. Intermediate models of stateful adversaries, also of interest classically Negative result Restriction on P is somewhat inherent.
Bridge Between Stateful and Stateless Adversaries A A A A A A A A ? ? ? ? ? ? One-shot ? Gap A A A A A A A A Stateless classical reduction applicable
Bridge 1: One-Shot to Persistent A A A A A A A A ? ? ? ? ? ? One-shot ? quantum rewinding [Chiesa-Ma-Spooner-Zhandry] Gap 1 restriction to decision etc. A A A A A A A A ? ? ? ? Persistent keeps solving, without losing steam
Isnt Persistent Enough? A A A A A A A A ? ? ? ? Persistent keeps solving, without losing steam Solvable set drifts reduction queries may be correlated (e.g., Goldreich-Levin)
Bridge 2: Persistent to Memoryless A A Persistent A A A A A A ? ? ? ? simulation argument restriction to non-adaptive Gap 2 main tech contribution A A A A A A A A ? ? ? ? Memoryless (& persistent) keeps clock, strategy fixed ahead
Simulating Memoryless Behavior Idea: adversary state poly-bounded, limited memory of past queries To make ?-th query ??: plant real ??in random location A A A A ? ??? ??? ???, , ??? ??marginal of ?-th query A A ?? A A ? ? ? ??? #state-qubits ?-close to execution with predetermined oracles for ? ?2 (quantum mutual information argument)
Bridge 3: Memoryless to Stateless A A Memoryless A A A A A A ? ? ? ? keeps clock, strategy fixed ahead simulation argument restriction to non-adaptive Gap 3 (shuffle queries ) A A A A A A A A Stateless classical reduction applicable
Bridge Between Stateful and Stateless Adversaries A A A A A A A A ? ? ? ? ? ? One-shot ? Persistent main tech contribution Gap Memoryless also in cosmic [CFP22] A A A A A A A A Stateless classical reduction applicable
Food for Thought What about adaptive reductions? (PRGs from OWFs [HILL]) Thanks!
A Counterexample for Search Assumptions Non-interactive problems P,Q with classical reduction, but no constructive post-quantum reduction P: Given vk for digital signature scheme, and a random message m, output s which is a valid signature for m. Q: Given vk for digital signature scheme, and random messages (m1, m2), output (s1, s2) which are valid signature for (m1, m2). Classically: P-Solver Q-Solver Quantumly: tokenized signature schemes [BS18,CLLZ21] allow to generate a quantum state that can be used to generate exactly one valid signature.
