Black-Box Separations in Quantum Cryptography
summary
States a conditional black-box separation: any key‑agreement protocol that uses classical messages, up to d quantum queries per party, and has perfect completeness can be broken with a polynomial number of classical oracle queries assuming a new polynomial compatibility conjecture about low‑degree, low‑influence multilinear polynomials. Proof introduces a quantum version of epsilon‑heavy queries via the compressed‑oracle/Fourier view and shows query‑efficiency bounds; unconditionally breaks protocols when one party is classical and proves the conjecture only for exponentially small influences.
AI-written summary · about
chapters (21)
- 0:00Black-Box Separations in a Quantum Worl Case of Key Agreements from One-Way Functions
- 1:00Assumptions in Cryptography
- 2:18Secret Key vs. Public Key Cryptography
- 5:30Cryptography in a Quantum World
- 6:24Black-Box Reductions and Separations in a Quantum World
- 9:21Black-Box Separations in a Quantum World
- 12:14Key Agreement vs. OWFs in Quantum World
- 14:23Outline
- 14:53Key Agreement using a Random Oracle
- 16:34Why caring about KA using random oracles?
- 17:34Random Oracles →? Key Agreements
- 18:43Quantum access to random oracle [BDFLSZ'10]
- 20:03Previous Results (Fine Grained Setting)
- 23:42Grievances
- 27:40Adapting &-heavy attack to quantum parties?.
- 28:53Quantum E-Heavy Queries (Intuition)
- 33:14Quantum E-Heavy Query Attack
- 36:20Analysis of the attack, intuition
- 39:47Basic Definitions for the PC Conjecture
- 41:09Polynomial Compatibility Conjecture
- 45:54Open Problems
related talks
32mQuantum Obfuscation of Classical Circuits
20mOn the computational hardness needed for quantum cryptography
59mAn Introduction to Quantum Obfuscation
37mBlack-Box Uselessness: Composing Separations in Cryptography
01h 08mNew Quantum Cryptographic Primitives II
59mQuantum cryptography and quantum complexity
56mQuantum 4
16mQuantum Information Meets Cryptography