Black-Box Separations in Quantum Commitment Protocols

Protocol analysis of non-interactive commitments in classical and quantum settings, including discussions on OWF, NIC, PRS, and quantum communication implications. The results based on the Polynomial Compatibility Conjecture showcase advancements in post-quantum OWF and NIC scenarios.

• Quantum
• Commitment
• OWF
• NIC
• Protocol

lbra Follow

Uploaded on Sep 24, 2024 | 0 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.

Presentation Transcript

1. Black-Box Separations for Non-Interactive Commitments in a Quantum World Eurocrypt 2023 Kai-Min Chung (Academia Sinica) Yao-Ting Lin (UCSB) Mohammad Mahmoody (University of Virginia)

2. (Non-interactive) Commitment Commit phase Hiding Input: ? Receiver Sender Reveal phase Binding Receiver Sender

3. Commitment in the classical setting One-way function (OWF) (Interactive) Commitment [Impagliazzo & Luby 89][Naor 90][Hastad, Impagliazzo, Levin & Luby 99] Many constructions are black-box [Impagliazzo & Rudich 89][Reingold, Trevisan & Vadhan 04][Baecher, Brzuska & Fischlin 13] Injective OWF / One-way permutation Non-interactive commitment (NIC) Black-box Separation: OWF Injective OWF / OWP [Matsuda & Matsuura 11] Construct NIC from OWF? Black-box Separation: OWF NIC [Pass & Mahmoody 12]

4. Commitment in the quantum setting Quantum Communication + OWF NIC [Koshiba & Odaira 11][Bitansky & Brakerski 21] Black-box Separation: Pseudorandom State (PRS) OWF [Kretschmer 21] Quantum Communication + PRS NIC [Morimae & Yamakawa 22][Ananth, Qian & Yuen 22] Does classical communication + post-quantum OWF NIC ?

5. Our Result Assuming the Polynomial Compatibility Conjecture (PCC) [Austrin, Chung, Chung, Fu, Lin & Mahmoody 22], we prove that classical communication + post-quantum OWF NIC (even holds for quantum decommitment) Corollary: Assuming the PCC, 1. Post-quantum OWF Post-quantum injective OWF Improve the result of [Cao & Xue 21]. 2. Classical communication + PRS NIC Complement the positive result: OWF/PRS NIC with Q.commitment & C.decommitment [Bitansky & Brakerski 21] [Morimae & Yamakawa 22] [Ananth, Qian & Yuen 22]

6. Q.Computation C.Communication model OWF Receiver Sender Input: ? {0,1} Classical Commitment Classical Decommitment - - - - Completeness + Hiding + Binding Sender/Receiver can make quantum queries to the oracle (OWF) Commitment and decommitment are classical Our result holds even for quantum decommitment

7. Separating primitive ? from OWF Impagliazzo-Rudich 89: Breaking the security of every construction of ? in random oracle model Separating ? from OWF If ?is NIC, then it doesn t work directly RO from ? bits to 3? bits is injective with overwhelming probability Use the idea in [Pass & Mahmoody 12]

8. Proof idea in [Pass & Mahmoody12] Heavy-query learning technique [IR89][Barak & Mahmoody 08] For every NIC based on a OWF ?, Either Cheating receiver relative to RO that breaks hiding: 1. Learns all (poly. many) sender s heavy queries 2. Output the more likely input bit Or two consistentsender s views ?0,?1 corresponding to ? = 0/1 Partially fixed random oracle ? that is fixed over ? ?0 ? ?1 Cheating sender relative to ? that breaks binding: Output com,decom0 in ?0, or output com,decom1 in ?1 A random function fixed over poly. points is one-way.

9. Challenges 1. Quantum queries cannot be recorded: When the honest sender makes quantum queries, how to define the cheating receiver? 2. How to adversarially construct an oracle such that the cheating sender can always break binding relative to the oracle the oracle is one-way

10. Learning quantum heavy-queries Quantum queries cannot be recorded: [Austrin, Chung, Chung, Fu, Lin & Mahmoody 22] extends the heavy- query learning technique to the quantum setting by using the compressed oracle technique [Zhandry 19]. Heavy-query learner asks classical queries that are heavy for the quantum algorithm. Outline of our attack: Cheating receiver learns sender s quantum heavy-queries. Polynomial Compatibility Conjecture the existence of compatible oracle Compatible oracles the support of a poly-degree multilinear polynomial Schwartz Zippel lemma for ?2 the abundance of compatible oracles

11. Implication of our attack For every NIC based on a post-quantum OWF ?, either 1. ? RO, there is a poly-query cheating receiver that breaks hiding. 2. ? is uniform over a set of functions from ? bits to ? bits such that supp(?) (2?)2? poly(?) and there is a cheating sender with poly-qubit advice that breaks binding. Remain to prove that the oracle is one-way in the non-uniform setting

12. Proving the one-wayness Question: - The oracle? is uniform over a set of functions from ? bits to ? bits such that supp(?) (2?)2? poly(?) - The adversary is given poly-qubit advice and can make poly. quantum queries to ?. Solution: Tweak the proof in [Chung, Guo, Liu & Qian 20].

13. Open Questions Separation without conjecture? Barrier result to Aaronson-Ambainis conjecture? Other black-box separations in QCCC model?

14. Thanks for your attention!