Unclonable Non-Interactive Zero-Knowledge: Technical Overview

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

2 Technical Overview

In this section, we give a high-level overview of our construction and the techniques underlying our main results.

2.1 Unclonable Extractable NIZKs in the CRS Model

Our construction assumes the existence of public-key encryption, classical bit commitments where honestly generated commitment strings are perfectly binding, along with

• Public-key quantum money mini-scheme (which is known assuming post-quantum iO [Zha19b]). At a high level, public-key quantum money mini-scheme consists of two algorithms: Gen and Ver. Gen on input a security parameter, outputs a quantum banknote |$i along with a classical serial number s. Ver is public, takes a quantum money banknote, and outputs either a classical serial number s, or ⊥ indicating that its input is an invalid banknote. The security guarantee is that no efficient adversary given an honest banknote |$i can output two notes |$1i and |$2i that both pass the verification and have serial numbers equal to that of |$i.

• Post-quantum NIZKs for NP, which are known assuming the post-quantum hardness of LWE. These satisfy (besides completeness) (1) soundness, i.e., no efficient prover can generate accepting proofs for false NP statements, and (2) zero-knowledge, i.e., the verifier obtains no information from an honestly generated proof beyond what it could have generated on its own given the NP statement itself.

Construction. Given these primitives, the algorithms (Setup, Prove,Verify) of the unclonable extractable NIZK are as follows.

SETUP(1λ ): The setup algorithm samples a public key pk, the common reference string crs of a classical (post-quantum) NIZK for NP, along with a perfectly binding, computationally hiding classical commitment to 0 λ with uniform randomness t, i.e. c = Com(0λ ;t). It outputs (pk, crs, c).

PROVE: Given the CRS (pk, crs, c), instance x and witness w, output (|$, s, ct, π) where

• The state |$ ← Gen is generated as a quantum banknote with associated serial number s.

• The ciphertext ct = Encpk(w; u) is an encryption of the witness w with randomness u.

• The proof string π is a (post-quantum) NIZK for the following statement using witness (w, u):

EITHER (∃w, u : ct = Encpk(w; u) ∧ RL(x, w) = 1) OR (∃r : c = Com(s; r)),

where we recall that pk and c were a part of the CRS output by the Setup algorithm.

VERIFY: Given CRS (pk, crs, c), instance x and proof (|$, s, ct, π), check that (1) Ver(|$) outputs s and (2) π is an accepting NIZK proof of the statement above.

Analysis. Completeness, soundness/proof of knowledge and ZK for this construction follow relatively easily, so we focus on unclonable extractability in this overview. Recall that unclonable extractability requires that no adversary, given an honestly generated proof for x ∈ L, can split this into two accepting proofs for x ∈ L (as long as it is hard to find a witness for x). Towards a contradiction, suppose an adversary splits a proof into 2 accepting proofs (|$1i, s1, ct1, π1), (|$2i, s2, ct2, π2). Then,

• If s1 = s2 = s, the adversary given one bank note with serial number s generated two valid banknotes |$i 1 and |$i 2 that both have the same serial number s. This contradicts the security of quantum money.

• Otherwise, there is a bit b such that sb 6= s. Then, consider an indistinguishable hybrid where the adversary obtains a simulated proof generated without witness w as follows: (1) sample quantum banknote |$ with serial number s, (2) sample public key pk along with secret key sk, (3) generate c = Com(s;t), ct = Encpk(0; u), (4) generate proof π using witness t (since c = Com(s;t)) instead of using witness w. Send common reference string (pk, crs, c) and proof (|$i, s, ct, π) to the adversary. Now, the proof that the adversary generates with sb 6= s must contain ctb = Encpk(w; u), since c being generated as a commitment to s 6= sb along with the perfect binding property implies that (6∃ r : c = Com(sb; r)). That is, given instance x, the adversary can be used to compute a witness w for x by decrypting ciphertext ctb, thereby contradicting unclonable extractability.

Having constructed unclonable extractable arguments in the CRS model, in the next section, we analyze a construction of unclonable extractable arguments in the QROM.

2.2 Unclonable Extractable NIZK in the QROM

We now turn our attention to the QRO setting in which we demonstrate a protocol which is provably unclonable. Our construction assumes the existence of public-key quantum money mini-scheme and a post-quantum sigma protocol for NP. A sigma protocol (P,V) is an interactive three-message honest-verifier protocol: the prover sends a commitment message, the verifier sends a uniformly random challenge, and the prover replies by opening its commitment at the locations specified by the random challenge.

Construction. The algorithms (PROVE, VERIFY) of the unclonable extractable NIZK in the QROM are as follows.

PROVE: Given an instance x and witness w, output (|$, s, α, β, γ) where

• The quantum banknote |$ is generated alongside associated serial number s.

• P is run to compute the sigma protocol’s commitment message as α given (x, w) as input.

• The random oracle is queried on input (α, s, x) in order to obtain a challenge β.

• P is run, given as input (x, w, α, β) and its previous internal state, to compute the sigma protocol’s commitment openings as γ.

2.3 Unclonable NIZKs imply Quantum Money Mini-Scheme

Finally, we discuss why unclonable NIZKs satisfying even the weaker definition of unclonable security (i.e., w.r.t. hard distributions) imply public-key quantum money mini-scheme. Given an unclonable NIZK, we build a public-key quantum money mini-scheme as follows.

Construction. Let(X ,W) be a hard distribution over a language L ∈ NP. Let Π = (Setup, Prove,Verify) be an unclonable NIZK protocol for L.

2.4 Unclonable Signatures of Knowledge

Informally, a signature of knowledge has the following property: if an adversary, given a signature of a message m with respect to an instance x, can produce two signatures for m which verify with respect to the same instance x, then the adversary must know (and our extractor will be able to extract) a witness for x.

We obtain unclonable signatures of knowledge assuming the existence of an unclonable extractable simulation-extractable NIZK for NP. Simulation-extractability states that an adversary which is provided any number of simulated proofs for instance and witness pairs of their choosing, cannot produce an accepting proof π for an instance x which they have not queried before and where extraction fails to find an accepting witness w. Our unclonable extractable NIZK for NP in the CRS model can, with some extra work, be upgraded to simulation-extractable.

We informally describe the construction of signatures of knowledge from such a NIZK below.

Construction. Let (Setup, P,V) be non-interactive simulation-extractable, adaptive multi-theorem computational zero-knowledge, unclonable-extractable protocol for NP. Let R be the NP relation corresponding to L.

SETUP: The setup algorithm samples a common reference string crs of an unclonable-extractable simulation-extractable NIZK for NP. It outputs crs.

SIGN: Given the CRS crs, instance x, witness w, and message m, output signature π where

• The proof string π is an unclonable-extractable simulation-extractable NIZK with tag m using witness w of the following statement:

(∃w : (x, w) ∈ R).

VERIFY: Given CRS crs, instance x, message m, and signature π, check that π is an accepting NIZK proof with tag m of the statement above.

Analysis. The simulatability (extractability) property follows from the zero-knowledge (resp. simulation-extractability) properties of the NIZK. Suppose an adversary A given a signature σ was able to forge two signatures σ1 = π1 and σ2 = π2, and, yet, our extractor was to fail to extract a witness w from A. Then,

• Either both proofs π1 and π2 are accepting proofs for membership of the same instance w.r.t. crs. However, this contradicts the unclonability of the NIZK.

• Otherwise there exists a proof πi (where i ∈ {1, 2}) for an instance which A has not previously seen a proof for. We can switch to a hybrid where our signatures contain simulated proofs for the NIZK. But now, we have that the verifier accepts a proof for an instance which A has not seen a simulated proof for and, yet, we cannot extract a witness from A. This contradicts the simulation extractability of the NIZK.

Roadmap. In Section ??, we define and construct unclonable NIZKs in the CRS model, and in Section 5, in the QROM. Along the way, we also show that unclonable NIZKs imply quantum money (in the CRS and QRO model respectively). Later, we show how to define and construct unclonable signatures of knowledge from unclonable NIZKs in the CRS model.