This paper is available on arxiv under CC 4.0 license. Authors: (1) Ruta Jawale; (2) Dakshita Khurana. Table of Links Abstract and Introduction Technical Overview Preliminaries Unclonable Non-Interactive Zero-Knowledge in the CRS Model Unclonable NIZK in the Quantum Ramdon Oracle Model Unclonable Signatures of Knowledge References 4 Unclonable Non-Interactive Zero-Knowledge in the CRS Model 4.1 Simulation-Extractable Definition (Post-Quantum (Quantum) Simulation-Extractable NIZK for in CRS Model). Let NP relation R with corresponding language L be given such that they can be indexed by a security parameter λ ∈ N. Definition 4.1 NP Π = ( ) is a post-quantum (quantum) non-interactive simulation-extractable zero-knowledge argument for NP in the CRS model if it has the following syntax and properties. Setup, P, V • Π is a post-quantum (quantum) non-interactive simulation sound, adaptive multi-theorem computational zero-knowledge argument for in the model (Definition 3.7). NP CRS • Simulation Extractability. Let Sim = ( ) be the simulator given by the adaptive multi-theorem computational zero-knowledge property. There exists a (quantum) polynomial-time circuit Ext and a negligible function such that for every oracle-aided polynomials-ize quantum circuit A and every λ ∈ N, Sim0, Sim1 negl(·) where is the list of queries from to Sim1. Q A REMARK 4.1. As defined in Definition 4.1, a simulation-extractable zero-knowledge protocol has simulation soundness [Sah99, SCO+01], is a proof of knowledge, and has adaptive computational soundness (Definition 3.5). (Post-Quantum Simulation-Extractable NIZK for NP in the CRS Model). Let NP relation R with corresponding language L be given. Theorem 4.2 Let Π = ( ) Setup, P,V be a non-interactive post-quantum simulation sound, adaptively multi-theorem computationally zero-knowledge protocol for NP (Definition 3.7). Let (Gen, Enc, Dec) be a post-quantum perfectly correct, IND-CPA secure encryption scheme (Definition 3.3). ( ) Setup, P,V as defined in Figure 1 will be a non-interactive post-quantum simulation-extractable, adaptively multi-theorem computationally zero-knowledge argument for L in the common reference string model (Definition 4.1). . Completeness follows from the perfect completeness of Π. Proof Perfect Completeness. Let Π.Sim = (Π.Sim0, Π.Sim1) be the adaptive multi-theorem computationally zero-knowledge simulator of Π. We define Sim0 with oracle access to Π.Sim0 as follows: Adaptively Multi-theorem Computationally Zero-Knowledge. Input: 1 λ . We will first switch the honest proofs for simulated proofs, using the adaptive multi-theorem zeroknowledge of Π. Later, we will see how we can switch the encryption of a valid witness to an encryption of 0, by using the security of the encryption scheme. We define a series of intermediary hybrids starting from encrypting all real witnesses to encrypting all zeros. The first intermediary hybrid switches the encryption sent in the last query from an encryption of a witness to an encryption of 0. We continue switching the encryption in the second to last query and so on, until we’ve switched the first proof that the adversary makes. Let (·) be a polynomial denoting the maximum number of queries that A makes. By a union bound and Equation (2), there must exist a hybrid indexed by (where we switch the ciphertext in the th proof from encrypting a witness to encrypting 0) where first distinguishes between the two ciphertexts with advantage 1/(p ′ (λ)q(λ)). That is, q i i A Proof of Claim 4.3. Let a polynomial p(·) and an oracle-aided polynomial-size quantum circuit A be given such that This concludes our proof. Hence our protocol must be multi-theorem zero-knowledge. This follows from Corollary 3.9 and Theorem 4.2. Proof. 4.2 Unclonability Definitions We consider two definitions of unclonability for NIZKs. The first one, motivated by simplicity, informally guarantees that no adversary given honestly proofs for “hard” instances is able to output more than one accepting proof for the same instance. Definition 4.5 ((Quantum) Hard Distribution). Let an NP relation R be given. (X ,W) is a (quantum) hard distribution over R if the following properties hold. • Syntax. (X ,W) is indexable by a security parameter λ ∈ N. For every choice of λ ∈ N, the support of (Xλ,Wλ) is over instance and witness pairs (x, w) such that x ∈ L, |x|= λ, and (x, w) ∈ R. • Hardness. For every polynomial-sized (quantum) circuit family A = {Aλ}λ∈N, Definition 4.6. (Unclonable Security for Hard Instances). A proof (Setup, P,V) satisfies unclonable security for a language L with corresponding relation RL if for every polynomial-sized quantum circuit family {Cλ}λ∈N, and for every hard distribution {Xλ,Wλ}λ∈N over RL, there exists a negligible function negl(·) such that for every λ ∈ N, We will now strengthen this definition to consider a variant where from any adversary A that on input a single proof of membership of x ∈ L outputs two proofs for x, we can extract a valid witness w for x with high probability. In fact, we can further generalize this definition to a setting where the adversary obtains an even larger number (say k − 1) input proofs on instances x1, . . . , xk−1, and outputs k or more proofs. Then we require the extraction of an NP witness corresponding to any proofs that are duplicated (i.e. two or more proofs w.r.t. the same instance xi ∈ {x1, . . . , xk−1}). We write this definition below. ((k − 1)-to-k-Unclonable Extractable NIZK). Let security parameter λ ∈ N and NP relation R with corresponding language L be given. Let Π = (Setup, P,V) be given such that Setup, P and V are poly(λ)-size quantum algorithms. We have that for any (x, w) ∈ R, (crs,td) is the output of Setup on input 1 λ , P receives an instance and witness pair (x, w) along with crs as input and outputs π, and V receives an instance x, crs, and proof π as input and outputs a value in {0, 1}. Definition 4.7 Π is a non-interactive (k−1)-to-k-unclonable zero-knowledge quantum protocol for language L if the following holds: • Π is a quantum non-interactive zero-knowledge protocol for language L (Definition 3.5). • (k−1)-to-k-Unclonable with Extraction: There exists an oracle-aided polynomial-size quantum circuit E such that for every polynomial-size quantum circuit A, for every tuple of k − 1 instance-witness pairs (x1, ω1), . . . ,(xk−1, ωk−1) ∈ R, for every x where we define – I ⊆ [k − 1] such that |I|≥ 1, xi = x for all i ∈ I, and xι 6= x for all ι 6∈ I, and – J ⊆ [k] such that |J |≥ max{2, |I|}, xj = x for all j ∈ J , and xι 6= x for ι 6∈ J , such that there is a polynomial p(·) where then there is also a polynomial (·) such that q . Let Π = (Setup, P,V) be a 1-to-2-unclonable with extraction, non-interactive zero-knowledge quantum protocol (Definition 4.7). Then, Π satisfies Definition 4.6. Lemma 4.8 For a proof of Lemma 4.8, we refer to Appendix A. 4.3 Unclonable NIZK Implies Public-Key Quantum Money Mini-Scheme Figure 2: Public-Key Quantum Money Mini-Scheme from an Unclonable Non-Interactive Quantum Protocol . Let (X ,W) Theorem 4.9 be a hard distribution over a language L ∈ NP. Let Π = (Setup, P,V) satisfy Definition 4.6. Then (Setup, P,V) implies a public-key quantum money scheme mini-scheme (Definition 3.13) as described in Figure 2. . Perfect Correctness. This follows directly from the perfect completeness of Π. Unforgeability. Let p(·) be a polynomial and A be a quantum polynomial-time adversary such that for an infinite number of λ ∈ N +, Proof 4.4 Construction and Analysis of Unclonable NIZK from Public-Key Quantum Money . Let k(·) be a polynomial. Let NP relation R with corresponding language L be given. Theorem 4.10 Let (NoteGen,Ver) be a public-key quantum money mini-scheme (Definition 3.13) and Com be a post-quantum commitment scheme (Definition 3.1). Let Π = (Setup, P,V) be a non-interactive postquantum simulation-extractable, adaptive multi-theorem computational zero-knowledge protocol for NP (Definition 4.1). ( ) Setup, P,V as defined in Figure 3 will be a non-interactive quantum simulation-extractable, adaptive multi-theorem computationally zero-knowledge, and (k − 1)-to-k-unclonable with extraction protocol for L in the common reference string model (Definition 4.7). . Completeness follows from perfect correctness of the public key quantum money scheme, and perfect completeness of Π. Proof. Perfect Completeness . Let Π.Sim = (Π.Sim0, Π.Sim1) be the adaptive multi-theorem computationally zero-knowledge simulator of Π. We define Sim0 with oracle access to Π.Sim0 as follows: Adaptive Multi-Theorem Computational Zero-Knowledge However, we make the following claim which is in direct contradiction with Equation (3). Scenario One Given the event in Equation (5) holds, then the reduction will, with advantage 1/q(λ) for some polynomial q(·), succeed at breaking the hiding of Com, thus reaching a contradiction. Since Equation (3) directly contradicts Claim 4.11 which we have proven, then we have reached a contradiction. Therefore, the protocol must be simulation extractable. Let Π.Sim = (Π.Sim0, Π.Sim1) be the adaptive multi-theorem computationally zero-knowledge simulator of Π. Let Π.Ext be the simulation-extraction extractor of Π with respect to Π.Sim. Let Sim = (Sim0, Sim1) be the simulator, with oracle access to Π.Sim, as defined in the proof that Figure 3 is adaptive multi-theorem computational zero-knowledge. Let Ext be the extractor, based on Sim, as defined in the proof that Figure 3 is simulation-extractable. We define E with oracle access to Sim, Ext, and some A as follows: Unclonable Extractability. Scenario One Say that A generates two accepting proofs which have the same serial number as an honestly generated proof. By applying a union bound to Equation (7), we have that this event could happen with at least 1/2p(λ) probability. Symbolically, Scenario Two Alternatively, say that A does not generate two accepting proofs which have the same serial number as an honestly generated proof. By the pigeon-hole principle, this means that A generates an accepting proof with a serial number which is not amongst the ones it received. By applying a union bound to Equation (7), we have that this event could happen with at least 1/2p(λ) probability. In summary, we have that Through an averaging argument, we can fix index j ∈ J which gives us the same event with an advantage of 1/(2kp(λ)). We will now switch to a hybrid where we provide A with simulated proofs at indices I. . There exists a polynomial (·) such that Claim 4.12 q Given that the event in Equation (13) holds, then B contradicts Claim 4.11. Thus, all that remains to be proven is Claim 4.12. Proof of Claim 4.12. We proceed by contradiction. Let negl(·) be a negligible function such that By Equation (10) and Equation (13), there exists a polynomial q ∗ (·) such that By using the advantage of A in this game, we can show a reduction that breaks the multi-theorem zero-knowledge of Figure 3. We will now outline this reduction. Given that A is able to change its output dependent on which of the two worlds in Equation (14) that it is in, then the reduction will be able to distinguish between receiving honest proofs or simulated proofs. With advantage 1/q∗ (λ), the reduction will succeed at breaking the adaptive multi-theorem computational zero-knowledge of our protocol, thus reaching a contradiction. By completing the proofs of our claim, we have concluding the proof of our theorem statement. . Assuming the polynomial quantum hardness of LWE, injective one-way functions exist, and post-quantum iO exists, there exists a non-interactive adaptive knowledge sound, adaptive computationally zero-knowledge, and (k−1)-to-k-unclonable with extraction protocol for NP in the common reference string model (Definition 4.7). Corollary 4.13 . This follows from Theorem 3.2, Corollary 4.4, Theorem 3.14, and Theorem 4.10. Proof We have thus shown that Figure 3 is an unclonable NIZK PoK in the CRS model as defined according to our proposed unclonability definition, Definition 4.7. In the upcoming sections, we will consider unclonable proof systems in the QROM.

Unclonable Non-Interactive Zero-Knowledge in the CRS Model

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

5 Ways to Measure Privacy Risks in Text Data

Unclonable Non-Interactive Zero-Knowledge: Abstract and Introduction

Unclonable Non-Interactive Zero Knowledge in the Quantum Random Oracle Model

Unclonable Non-Interactive Zero-Knowledge: Preliminaries

Unclonable Non-Interactive Zero-Knowledge: References

Unclonable Non-Interactive Zero-Knowledge: Technical Overview

5 Ways to Measure Privacy Risks in Text Data

Unclonable Non-Interactive Zero-Knowledge: Abstract and Introduction

Unclonable Non-Interactive Zero Knowledge in the Quantum Random Oracle Model

Unclonable Non-Interactive Zero-Knowledge: Preliminaries

Unclonable Non-Interactive Zero-Knowledge: References

Unclonable Non-Interactive Zero-Knowledge: Technical Overview

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps