Quantum Key Agreements and Random Oracles
This academic paper explores the impossibility of achieving key agreements using quantum random oracles, discussing the challenges and limitations in quantum communication, cryptographic protocols, quantum computation, and classical communication. The study delves into the implications of quantum random oracle models, classical versus quantum communication for key agreements, and the quest for secure key agreements in the presence of eavesdroppers. Various key concepts such as perfect completeness, use of random oracles, and quantum Impagliazzo-Rudich results are analyzed to understand the complexities of achieving secure key agreements in quantum scenarios.
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
On the Impossibility of Key Agreements from Quantum Random Oracles Per Austrin (KTH Royal Institute of Technology) Kai-Min Chung (Academia Sinica) Hao Chung (Carnegie Mellon University) Shiuan Fu (Academia Sinica) Yao-Ting Lin (Academia Sinica UC Santa Barbara) Mohammad Mahmoody (University of Virginia)
Random Oracles Private Key Cryptography OT TDP Can we get key agreements from random oracles? KA PKE Random Oracle Model CRH OWF SKE SIG COM PRG PRF
Key Agreements Two-party interactive protocol Goal: share a secret key against eavesdroppers Start with private local randomness: ??and ?? Finally, they output their own keys ??and ??. Alice Bob ?? ?? Transcript ? ?? ?? Def. We say a key agreement protocol is with perfect completeness if Pr ??= ?? = 1.
Random Oracles Key Agreements Impagliazzo and Rudich (STOC 89): We cannot use RO to get KA! (RO is the only assumption) KA in which Alice, Bob: ? queries Eve: ?(?6)queries What if we allow the parties to use quantum computation?
Quantum communicationKey Agreements (Bennett-Brassard 1984): Quantum communication gives us unconditional secure KAs. What if the communication is still classical ? Can quantum computation + a random oracle + classical communication give us key agreements?
Quantum Random Oracle Model (QROM) [Boneh et.al, ASIACRYPT 11] QROM = regular ROM + query/answer in superposition ?,?????,? ?,?????,? ?(?) RO query Eve Bob Alice Transcript ?
Main Question: Quantum Impagliazzo-Rudich results? Hosoyamada-Yamakawa (Best Paper Award, ASIACRYPT 20) Question: Does there exist a KA where Alice and Bob can 1. only do classical communication 2. perform local quantum computation 3. make ? quantum queries to the random oracle but every eavesdropper needs a super-polynomial ??(?)number of queries to find the key.
Out Results If we break KAs in QROM with poly. queries, it would imply the fully black-box separation. Suppose Alice and Bob both make ? queries: 1. Classical Alice + Quantum Bob: - We construct an ? ?2-query attack on every KA in QROM 2. Quantum Alice + Quantum Bob: - We propose a parametrized conjecture that would imply an ???? ? -query attack on every KA in QROM. - We prove the conjecture with worse parameter which implies an ??? ? - query attack on every KA in QROM. 3. A Barrier result: - If Aaronson-Ambainis Conjecture is false, then there exists a KA with imperfect completeness that is secure against classical eavesdroppers.
Plan Black-Box Constructions/ Reductions Warm-up: an attack in classical case Our Results
Impossibility of Constructions/Reductions? It seems very hard to construct KAs from OWFs. Can we prove the impossibility of doing so? To prove unconditional impossibility, we have to prove (1) OWFs exist: also very hard (2) KAs do not exist: but KAs seem to exist We have to restrict ourselves to some general and interesting enough framework.
(Fully) Black-Box Reduction [ [Reingold Reingold- -Trevisan Trevisan- -Vadhan Vadhan, TCC 04] Primitive P by using primitive Q as a black box KA OWF , TCC 04] Q Adv of P Primitive Q Primitive P Reduction from a primitive P to Q in a black-box way Q Adversary of Q Adversary of P The implementation of Q and the adversary of P could be inefficient, since they are given as oracles.
Quantum Black-Box Separations [Hosoyamada-Yamakawa, ASIACRYPT 20] They proved that there does not exist QBB reduction from CRH to OWP/TDP. Q Implement a primitive P by using Q as a black box quantumly Implementation of Q Implementation of P Adv Reduction from a primitive P to Q in a quantum black-box way of P Q Adversary of Q Adversary of P
An Attack on every KA with Perfect Completeness in Random Oracle Model
The Heavy-Query-Learning Attack [Barak [Barak- -Mahmoody Mahmoody, CRYPTO 09] , CRYPTO 09] ??= dom ?? ??= dom ?? ??= dom(?) ? Set of query- answer pairs ? ?(?) ??= (??,?,??) ??= (??,?,??) ? Eve s attack: 1. Initialize an empty list ? (which is a partial function) 2. While( ? ??s.t.Pr ? ?? ?,? ?) Query ? and obtain the answer ? Update ? ? {(?,?)} 3. Sample a fake view ?? ? ??, we have Pr ? ???,? < ? = (?? ,?,?? ) ?? ?,?
The Heavy-Query-Learning Attack Eve s query complexity: ?(?/?) Choose ? = 1/10?. Domain With high probability, we have ?? ?? ??= ?? ,?? and ? are consistent with ?? ?? each other will be consistent with ?? ?? ?? ??= ??= ?? Perfect completeness
Generalize the Heavy-Query-Learning Attack? Technical issues: 1. No well-defined query sets ??and ?? 2. No inverse sampling But the heavy-query-learning attack crucially relies on them. ? ??= ( ?? ,?) ??= ( ?? ,?) ?
Our Results Result 1: Breaking every KA protocol with perfect completeness with Classical Alice and Quantum Bob. Number of queries: Alice, Bob: ? Eve: ?(?2) RO
Proof Sketch The attack is the same as the heavy-query-learning attack. Classical Alice query set ?? + inverse sampling Our proof was inspired by Zhandry s compressed oracle technique [Zhandry, CRYPTO 19]. 1. Augment an additional oracle register that starts with uniform superposition in the computational basis and then delay the sampling of the oracle 2. View the oracle in the Fourier basis, then it will record the queries made by the algorithm Computational basis: truth table number of non- ? entries in ? ) 3. The final state of any ?-query algorithm is of the form ?,?: ? ???????? Fourier basis: database ? ( the size of ? ?
Proof Sketch Deferred-measurement principle: All Alice s and Bob s intermediate measurements (except for those used for generating transcript) can be deferred. Given transcript ? and a list ?, we define the purified view of the protocol: 1. Run the protocol in superposition from scratch. 2. Calculate the post-measurement state corresponding to (?,?). ??,? = ??,?,??????? ???????? ?,?,?: ? 2? - ?,?: Alice s & Bob s register - ???: oracle register corresponding to ?? - ? ??: oracle register corresponding to ???(??) ?? - ?: transcript register
??,? = ??,?,??????? ???????? Proof Sketch ?,?,?: ? 2? WLOG, suppose (quantum) Bob measures all his qubits at the end. Therefore, the measurement outcome ? and the transcript ? can be seen as the view of Bob. For every ? and ?, consider the following (subnormalized) state ?: ? 2???,?,??? ?????? Measuring this state in the computational basis would give you the oracles that are possible to generate (?,?,?) and are consistent with ?. Let ???? quantum analogue of the query set ?? ?? ?? ?,?be the database that has the most non- ? entries in that state.
Proof Sketch ?,?are disjoint, then we can show that there exists a full and ???? If ?? oracle that is consistent with the real execution and ?? . ?,? ?,? ???? ???? ?? ?? Perfect completeness ??= ??= ?? Remark: [BKSY11] constructed a simpler attack on KAs with perfect completeness, but we do not know if it can be generalized to the CAQB setting.
Our Results Result 2: Conditionally breaking every KA protocol with perfect completeness between Quantum Alice and Quantum Bob We proposed a parametrized conjecture about low-degree and low-influence polynomials which would imply a poly- query attack. RO
Quantum Heavy Queries Intuitively, the zero ? in the Fourier basis reflects the algorithm s ignorance on that entry. Def. (Quantum ?-heavy query): For a purified view ??,? of the protocol, we say ? domain is a quantum ?- heavy query if ???,? where ? ? 0 ? ? ??is the projection onto the non- ? elements which acts on the ? entry of the database. 2 ? That is, the probability of obtaining non- ? outcomes by measuring the ? entry in the Fourier basis is at least ?.
Quantum Heavy-Query-Learning Attack Suppose the key is 1-bit. Eve s attack: 1. Initialize an empty list ? 2. While( ? ?? ? is a quantum ?- heavy query) Query ? classically and get the answer ? Update the purified view by computing the description of the post-measurement state corresponding to (?,?). 3. Output the more likely key bit in the purified view. By standard expectation arguments Eve s query complexity: ?(?/?)
Polynomial Compatibility Conjecture (PCC) There exists ?( ) = 1/poly( ) s.t. for every non-negative integer N,? 0 and distributions ? and ? over multilinear polynomials Eve s query complexity: poly(?) complexity: exp(?) Eve s query 1. of degree ? 2. with variables ?1, ,?? 1,1 3. with unit 2-norm. 4. low average-influence, i.e., ? [?], ??~?Inf?? 1 and E?~?Inf?? ?(?) exp(?) then there exists ? supp(?), ? supp(?) and ? 1,1? s.t ? ? 0 and ? ? 0. We show that this would imply the success of our attack.
Our Results Result 3: We prove the conjecture with exponentially small influences. Number of queries: Alice, Bob: ? Eve: exp(?) Breaking every KA with perfect completeness between Quantum Alice and Quantum Bob who both make a constant number of queries
Our Results Result 4: If Aaronson-Ambainis Conjecture is false, then there exists a KA with imperfect completeness against classical eavesdroppers. If we want to obtain separations for KAs with imperfect completeness, then we have to either 1. prove Aaronson-Ambainis Conjecture 2. construct an attack that makes quantum queries.
Open Problems Prove/Disprove our conjecture Construct an attack that makes quantum queries Prove the impossibility of KAs with imperfect completeness
