Quantum Cryptography Landscape and Results

How (not) to Build Quantum PKE in Minicrypt Xingjian Li Tsinghua University Joint work with Longcheng Li, Qian Li, Qipeng Liu

Landscape of Cryptography Impagliazzo s Five Worlds PKE commitment Key Agreement OWF Minicrypt Cryptomania

Landscape of Cryptography Impagliazzo s Five Worlds PKE commitment [IR89] Key Agreement OWF Minicrypt No Black box construction of Key Agreement only using OWF Cryptomania

Landscape of Quantum Cryptography PKE commitment(EFI) Microcrypt Key Agreement OWF Minicrypt Cryptomania

Landscape of Quantum Cryptography With Quantum Communication PKE commitment(EFI) Microcrypt Key Agreement OWF Minicrypt Cryptomania

Power of Quantum Communication Key Agreement: No assumption required [BB84]. Quantum PKE: Encryption Scheme from OWF using Quantum public key. [Col23,BGH+23, KMNY23,MW23] Commitments can build oblivious transfer, MPC [BCQ22 ]

Landscape of Quantum Cryptography Classical Communication Only PKE Any EFI separations? Microcrypt Key Agreement OWF Minicrypt Cryptomania

Our first result: Separating OWF and PKE [ACC+22]+ Conjecture [ACC+22] [ACC+22] Our Result Perfect Completeness Gen Q Q C C Enc Q C Q Q Dec Q Q C Q [ACC+22]: The adversary only makes classical queries, while the PKE makes quantum queries; Our adversary makes quantum queries

Our second result: Tight Characterization of qPKE Gen 1? pk ,sk Enc(|pk ,?) ??, ?? can be classical/quantum Dec sk,?? ? Adversary can receive poly(?) copies of |pk in security definition. Ourresult: If Gen only makes classical queries to OWF, then |pk must be mixed and unclonable. [Col23,BGH+23]: Pure |pk , Gen makes quantum queries [KMNY23, MW23]: Gen makes classical queries, |pk mixed and unclonable

Our third result: No PKE in any oracle model There is no PKE in any oracle model, if Dec does not make any query to the oracle. Merkle-type Key Agreement: Alice and Bob only make queries before messaging. ? ? ?

Model of Black box separation ?0= pk ?1= Enc(pk,?) ?? ?? PKE implies two round Key Agreement. OWF provided by the random oracle ?. For any protocol, by polynomial queries to ?, ? can guess ?. ? ??

Proof Sketch of [IR89] For simplicity, we only consider Merkle type key agreement in the talk. ?0= pk ?1= Enc(pk,?) ? ? ?????= (??,??) ?????= (??,??) via simulation, expecting Target of Eve: Sample a copy of Alice ????? ????? Not possible if there are intersection queries ?? ??. Strategy of Eve: Query the oracle until ?? ?? ??, then sample consistent ????? ,????? (?????,?????) .

Problems on Quantizing [IR89] ?0 ?1 ? ? ?????= (??,??) ?????= (??,??) ??,??is not well defined! The solution in [ACC+22]: For one side quantum case, cover the classical side. Two side quantum case: Based on some conjecture, Eve can cover quantum intersection through classical queries.

Rethink [IR89]: Information Theory ?0 ?1 ? ? ?? ?? ??implies the conditional mutual information (CMI) ? ?????:????? ?0,?1,?? = 0. The three parties form a Markov Chain ? ? ?, thus we can sample the joint distribution ??? from ??, by only conditioning on ?. Robustness of CMI.

Our Approach: Quantum Markov Chain Theorem([FR15]) For a quantum state ????, if the system has CMI ? ?:? ? ?, there exists a channel :? ?? , where ?? ??= (???), such that ???? ?? ?? ? ? . The strategy of our Eve: 1. Reduce ? ?:? ? ?; 2. Copy ? from the channel ; 3. Run the rest of ? , generate the key ?.

Repetition reduces CMI ?0 ?1 ? ? ...... ?2 ? ?1 ?? CMI can be reduced to any inverse poly small. Also works when the first message is quantum.

Our Approach: Quantum Markov Chain The strategy of our Eve: 1. Reduce ? ?:? ? ? by repeating ? for poly(?) times; 2. Copy ? from the channel in [FR15]; 3. Run the rest of ? .

Open Problems Rule out Quantum query Gen? Remove perfect completeness? Full Separation of any round Key Agreement?