Unclonable Non-Interactive Zero-Knowledge in the CRS Model

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

Definition 4.1 (Post-Quantum (Quantum) Simulation-Extractable NIZK for NP in CRS Model). Let NP relation R with corresponding language L be given such that they can be indexed by a security parameter λ ∈ N.

Π = (Setup, P, V) 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.

• Π is a post-quantum (quantum) non-interactive simulation sound, adaptive multi-theorem computational zero-knowledge argument for NP in the CRS model (Definition 3.7).

• Simulation Extractability. Let Sim = (Sim0, Sim1) 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 negl(·) such that for every oracle-aided polynomials-ize quantum circuit A and every λ ∈ N,

where Q is the list of queries from A to Sim1.

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).

Theorem 4.2 (Post-Quantum Simulation-Extractable NIZK for NP in the CRS Model). Let NP relation R with corresponding language L be given.

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).

Proof. Perfect Completeness. Completeness follows from the perfect completeness of Π.

Adaptively Multi-theorem Computationally Zero-Knowledge. Let Π.Sim = (Π.Sim0, Π.Sim1) be the adaptive multi-theorem computationally zero-knowledge simulator of Π. We define Sim0 with oracle access to Π.Sim0 as follows:

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 q(·) 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 i (where we switch the ciphertext in the ith proof from encrypting a witness to encrypting 0) where A first distinguishes between the two ciphertexts with advantage 1/(p ′ (λ)q(λ)). That is,

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.

Proof. This follows from Corollary 3.9 and Theorem 4.2.

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.

Definition 4.7 ((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}.

Π 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 q(·) such that

Lemma 4.8. 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.

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

Theorem 4.9. Let (X ,W) 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.

Proof. 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 +,

4.4 Construction and Analysis of Unclonable NIZK from Public-Key Quantum Money

Theorem 4.10. Let k(·) be a polynomial. Let NP relation R with corresponding language L be given.

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).

Proof. Perfect Completeness. Completeness follows from perfect correctness of the public key quantum money scheme, and perfect completeness of Π.

Adaptive Multi-Theorem Computational Zero-Knowledge. Let Π.Sim = (Π.Sim0, Π.Sim1) be the adaptive multi-theorem computationally zero-knowledge simulator of Π. We define Sim0 with oracle access to Π.Sim0 as follows:

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.

Unclonable Extractability. 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:

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.

Claim 4.12. There exists a polynomial q(·) such that

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.

Corollary 4.13. 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).

Proof. This follows from Theorem 3.2, Corollary 4.4, Theorem 3.14, and Theorem 4.10.

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.