Quantum Computationally Predicate-Binding Commitments
Quantum Computationally Predicate-Binding Commitments play a crucial role in Quantum Zero-Knowledge Arguments for NP. The concept involves Quantum Bit Commitment and Computational Binding in a quantum setting, exploring the uniqueness and superposition of committed values. This work introduces new results in Computational Predicate-Binding, highlighting the complexities and applications in quantum computing.
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.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
Quantum Computationally Predicate-Binding Commitments with Application in Quantum Zero-knowledge Arguments for NP {0,1} ?? {0,1} ?1 {0,1} ?2 Jun YAN tjunyan@jnu.edu.cn Jinan University *Based on our eprint paper: https://eprint.iacr.org/2020/1510 Scan to download
With the general quantum binding, the committed value is no long unique; it could be a superposition Quantum bit commitment Our results Computational binding b Quantum-secure OWF The first QZKA for NP based on QOWF Open: what binding property can it satisfy? Quantum zero-knowledge arguments for NP Parallelization String commitment Plug in Blum s protocol ?? ?2 ?1 Technical part The first non-trivial quantum computational string binding that is both useful and can be instantiated with the minimal complexity assumption Computational predicate-binding: any polynomial-time bounded sender can t open a commitment in two ways so as to satisfy two inconsistent predicates, respectively : new results : known results
Synopsis 1. An overview (10 ) 2. Pattern-predicate and (string) predicate-binding (8 ) 3. Related and concurrent work (3 ) 4. The technical detail (3 ) 5. Take away (1 )
Bit commitment A bit commitment scheme is a two-stage interactive protocol between a sender and a receiver satisfying: Hiding: the receiver can t guess the committed bit during the commit stage Binding: the sender can t change the committed bit later in the reveal stage {0,1} b
Quantum bit commitment (QBC) Allow both quantum computation and communication In contrast to the classical bit commitment secure against quantum attacks, or post-quantum bit commitment Statistically-hiding and statistically-binding QBC is impossible either Introduce complexity assumption {0,1} b
A generic quantum bit commitment scheme [Yan20] An ensemble of quantum circuit pair ?0? ,?1(?) ? Any QBC can be converted into this form Nice properties: Non-interactivity Can be based on QOWF Semi-honest security implies the full security Information-theoretic strict-binding (the opening through the entanglement is unique) Unitary Quantum circuit ?? |0 |0 C R b Hiding C Any polynomial-time bounded sender can t open an honest commitment to b as 1-b R R S S R b (Honest-)binding C R =? |0 |0 ?? * [Yan20]: General Properties of Quantum Bit Commitments (or: A Generic Quantum Bit Commitment Scheme and Its Properties), eprint: 2020/1488
The general (weak) binding of QBC A superposition attack: the cheating sender can commit to a superposition, where the coefficients ?0,?1can be tuned arbitrarily + ?1 ?0 1 0 The committed value is no longer (classically) unique, possibly a superposition Understanding the binding when the QBC is composed in parallel to commit a string is notoriously hard [CDMS04, Unruh16] * [CDMS04]: Computational Collapse of Quantum State with Application to Oblivious Transfer, in TCC 2004 * [Unruh16]: Computationally Binding Quantum Commitments, in Eurocrypt 2016
An application of bit commitments: Blums zero-knowledge protocol H G 1 2 2 1 Commitment of (G) 4 3 3 4 0 0 0 1 1 0 1 0 1 0 0 0 0 1 0 0 1 2 3 4 1 2 3 4 0 0 0 1 1 0 1 0 1 0 0 0 0 1 0 0 G = Verifier Prover (Chinese Arthur) (Chinese Merlin) A challenge b = 0 or 1 Check that the opened graph is (G) b=0: permutation + key b=1: Hamiltonian cycle H + key Check that a Hamiltonian cycle is opened
The main question that motivates this work: What happen if we plug a generic (statistically-hiding) computationally-binding QBC scheme in Blum s protocol? Nontrivial, by noting that the quantum rewinding is generally impossible, and the quantum binding is generally weak But if possible, then it will reduce the number of rounds from polynomial (with classical constructions) to just three (solely based on quantum-secure OWF) , thanks to the non-interactivity of the QBC circumvent barriers only known for classical constructions [ARU14], thanks to the information- theoretic strict-binding of the QBC * [ARU14]: Quantum Attacks on Classical Proof Systems: The Hardness of Quantum Rewinding, in FOCS 2014
After a few thoughts: Good news: Watrous s quantum rewinding technique works as well towards establishing the statistical zero-knowledge property in our setting Bad news: the weak binding of QBC may deteriorate the computational soundness It could be a superposition of exponentially many graphs committed by the prover Our results: compose a generic computationally-binding quantum bit commitment scheme in parallel, which gives rise to a quantum string commitment scheme s.t. 1. It satisfies a non-trivial computational binding (predicate-binding) property, and 2. Can be used to establish the security of Blum s zero-knowledge protocol
Pattern-predicate and (string) predicate-binding motivated by the soundness analysis of Blum s protocol
The motivation of pattern-predicate (or just predicate) Contains the poly-time decidable predicate as a special case The verifier s final verification in Blum s protocol induces two predicates Informal: for a string ??? 0,1?to satisfy a predicate, it should exhibit a certain pattern somewhere Formal: a triplet of poly-time algorithms (??? ,? ,?( )) s.t. given a witness ? 0,1???? ? ??? ? = 1 if ? is a valid witness and 0 otherwise ? ? {1,2, ,?} indicates which portion of the string is to examine ?(?) is a string (the pattern) of length |? ? | May not be computable in poly time given the string ??? A string ??? 0,1?satisfies a pattern-predicate ? if there exists a witness ? such that ??? ? = 1 and ??? ? ? = ?(?) Example: two predicates induced by Blum s protocol Project the string str on indices within ?(?) ?0corresponds to the challenge 0 a permutation ? ?1corresponds to the challenge 1 an ?-cycle ? ? ??? a valid ?-cycle a valid permutation the whole set {1,2, ,?2} ? coordinates corresponding to edges of ? 1? ?( ) ?(?)
The motivation of predicate-binding (with quantum formalization) In Blum s protocol, the two predicates induce two projectors/subspaces: Corresponding to the challenge 0: measurement {P0,id P0}, where the projector ? ?2? ?2 |? ?|? ?? ?| 0 0|?? ? P0= The quantum circuit to commit a string ? 0,1?is given by ??= ?=1 ? ?? ? ??? Corresponding to the challenge 1: measurement {P1,id P1}, where the projector ? ?? ? |? ?|? ?1?| 0 0|?1? P1= The registers for the commitments check are not fixed ?:? ????? For soundness, we need to show that subspaces ?0 ?1, up to any efficiently realizable ? that does not touch the commitment registers ? ?2
0,1? Predicate-binding ?0 Let ?0,?1 be two inconsistent predicates; i.e. any string can satisfy at most one of them. ?1 Example: the predicates ?0,?1in Blum s protocol are inconsistent when the input graph ? is not Hamiltonian Predicate-binding w.r.t. (?0,?1) Informal: Open commitments so that the revealed value (possibly a superposition) satisfies ?0 w.p. 1 Can t open commitments so that the revealed value satisfies ?1 with non-negligible prob. 2 is negligible, for any ? that is efficiently realizable and does not touch Formal: ?1 ? ??? ? the commitment register ? ? ?0? Predicate-binding if predicate-binding w.r.t. any pair of inconsistent predicates
Main theorem (informal) The parallel composition of a generic computationally-binding quantum bit commitment scheme gives rise to a quantum computationally predicate-binding string commitment scheme. Caveats: 1. The QBC scheme is of the generic form, which is easy to handle technically 2. We actually did not prove the full predicate-binding (i.e. w.r.t. an arbitrary inconsistent predicate pair): we require that for at least one predicate, a fixed portion of strings is needed to check in order to decide whether a string satisfies this predicate
Related work Previously, we know nothing about the binding of the parallelization of a general QBC that is computationally binding: Unruh[Unruh16] studied collapse-binding QBC A general QBC can t be collapse-binding [Yan20]. Previously, some quantum string commitments with specific (computational) binding properties that are useful were proposed: ?-binding [CDMS04] ?-binding [DFS04] But neither of them can be instantiated with well founded assumptions. * [DFS04]: Zero-Knowledge Proofs and String Commitments Withstanding Quantum Attacks, in Crypto 2004
Concurrent work There are two concurrent work which realize quantum bit commitment with simpler exchanged quantum states (BB84 states), and with more desirable properties (than ours) including: Extractability Equivocality They are also solely based on quantum-secure one-way functions. These properties may result in wider applications (in theory). But at the cost of: Extremely high (polynomial) round complexity More complex constructions * [BCKM21]: One-way functions imply secure computation in a quantum world, in Crypto 2021 * [GLSV21]: Oblivious transfer is in miniqcrypt, in Eurocrypt 2021
The technical detail (towards predicate-binding) In one sentence: a more clever way to sum (possibly) exponentially many terms within a superposition to overcome the general exponential curse [CDMS04] Exponential blowup
A pictorial illustration Error only grows linearly in the depth of this tree Project an arbitrary superposition that satisfies ?0 on ?1 Triangle inequality + quantum bit honest-binding 2 Goal: ? ?0???1?( s ??|0 ) 1 0 2 2 ? ?0 ? 0,1? 1???1?( s ??|0 ) ? ?0 ? 0,1? 1???1?( s ??|0 ) +? 1 0 1 0 +? +? Sum over strings with the prefix ?? Sum over strings with the prefix ?? Sum over (two) strings with the prefix ?? ? ? 1 the two leafs below Sum over (two) strings with the prefix ?? ? ? 1 the two leafs belwo , given by , given by 0 1 0 1 +? +? +? Each leaf corresponds to one term in the Goal Quantum bit honest-binding <? <? <? <?
Take away ?0? ,?1(?) ? 1. A generic computationally-binding quantum bit commitment scheme, whose binding is rather weak but which has several nice properties that classical computationally-binding bit commitments do not have, could be useful in quantum cryptography Nice properties: Non-interactivity Can be based on QOWF Semi-honest security implies the full security Information-theoretic binding {0,1} b 2. It is non-trivial to establish any useful binding property of the parallel composition of a computationally-binding quantum bit commitment scheme
Download our paper to check more detail: https://eprint.iacr.org/2020/1510 24
