Unclonable Non-Interactive Zero-Knowledge: Unclonable Signatures of Knowledge

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

6 Unclonable Signatures of Knowledge

6.1 Definition

Definition 6.1 (Unclonable Extractable SimExt-secure Signatures of Knowledge). Let NP relation R with corresponding language L be given such that they can be indexed by a security parameter λ ∈ N. Let a message space M be given such that it can be indexed by a security parameter λ ∈ N.

∈ N. Let a message space M be given such that it can be indexed by a security parameter λ ∈ N. (Setup, Sign, Verify) is an unclonable signature of knowledge of a witness with respect to L and M if it has the following properties:

• (Setup, Sign,Verify) is a quantum Sim-Ext signature of knowledge (Definition 3.16).

• (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, every {mι ∈ Mλ}ι∈[k−1], for every (x, m) where we define

such that there is a polynomial p(·) where

then there is also a polynomial q(·) such that

6.2 Construction

Theorem 6.2. Let Π = (Setup, P,V) be a non-interactive simulation-extractable, adaptive multi-theorem computational zero-knowledge, unclonable-extractable protocol for NP (Definition 4.7).

(Setup, Sign, Verify) in Figure 6 is an unclonable-extractable SimExt-secure signature of knowledge (Definition 6.1).

Proof of Theorem 6.2. Correctness follows naturally. It remains to prove simulateability, extractability, and unclonable extractability

Simulateable. 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 λ.

(1) Send 1 λ to Π.Sim0. Receive (crs,td) from Π.Sim0.

(2) Output crs and td.

We define Sim1 with oracle access to Π.Sim1 as follows:

Input: crs, td, x, m.

(1) Define xΠ = (x, m). Send (crs,td, xΠ) to Π.Sim1. Receive π from Π.Sim1.

(2) Output σ = π.

Let a polynomial p(·) and an oracle-aided polynomial-size quantum circuit A be given such that

We define a reduction to the multi-theorem zero-knowledge property of Π as follows:

Reduction: to zero-knowledge of Π given oracle access to A.

(1) Receive (real or simulated) crs from the challenger.

(2) Send crs to A.

(3) On query (x, w, m) from A: send xΠ = (x, m) to the challenger, receives (real or simulated) π from the challenger, send σ = π to A.

(4) Output the result of A.

The view of A matches that of our protocol in Figure 6 or Sim0 and Sim1. As such, this reduction should have the same advantage at breaking the adaptive multi-theorem computational zero-knowledge property of Π. We reach a contradiction, hence our protocol must be simulateable.

Extractable. Let Π.Sim = (Π.Sim0, Π.Sim1) be the adaptive multi-theorem computationally zero-knowledge simulator of Π. Let Π.Ext be the simulation extractable extractor of Π defined relative to Π.Sim. Let Sim = (Sim0, Sim1) be the simulator given by the simulation property which uses Π.Sim. We define Ext with oracle access to Π.Ext as follows:

Input: crs, td, x, m, σ = π.

(1) Define xΠ = (x, m).

(2) Send (crs, td, xΠ, π) to Π.Ext. Receive wΠ = w from Π.Ext.

(3) Output w.

Let a polynomial p(·) and an oracle-aided polynomial-size quantum circuit A be given such that

where Q is the list of queries from A to Sim1. If Verify accepts the output of A, then Π.V must accept (crs, xΠ, π). If (x, m) 6∈ Q, then since xΠ contains x, m, xΠ must not be in the queries asked to Π.Sim1. Since (x, w) 6∈ R, then xΠ 6∈ LΠ by the definition of LΠ. As such, it must necessarily be the case that (xΠ, wΠ) 6∈ RΠ. Hence, we have that

where QΠ is the list of queries, originating from A, that Sim1 makes to Π.Sim1. We define a reduction to the simulation extraction property of Π as follows:

Reduction: to simulation extraction of Π given oracle access to A.

(1) Receive crs from the challenger.

(2) Send crs to A.

(3) On query (x, w, m) from A: send xΠ = (x, m) to the challenger, receives π from the challenger, send σ = π to A.

(4) Receive (x, m, σ = π) from A. Define xΠ = (x, m).

(5) Output (xΠ, π).

The view of A matches that of Sim0 and Sim1. As such, this reduction should have the same advantage at breaking the extraction property of Π. We reach a contradiction, hence our protocol must be extractable.

Unclonable Extractability. Let Π.Sim be the adaptive multi-theorem computationally zero-knowledge simulator of Π. Let Π.Ext be the simulation extractable extractor of Π defined relative to Π.Sim. Let Π.E be the unclonable extractor of Π. We define E with oracle-access to Π.E, Π.Sim, Π.Ext, and some A as follows:

extract a valid witness. Formally, that is that both

Scenario One

We will show that we will directly contradict the unclonability of the NIZK protocol Π. We define a reduction to the unclonability of Π as follows:

The view of A matches either the real or the simulated game. Additionally, the challenger may run the honest extractor. As such, this reduction should have the same advantage at breaking the unclonability property of Π. This reaches a contradiction.

Scenario Two

We now switch to a hybrid where the proofs in the signatures are simulated.

Claim 6.3. There exists a polynomial p ′ (·) such that

where QΠ is the list of queries that are made to Π.Sim1.

We define a reduction to the simulation extraction property of Π as follows:

The view of A matches that in Equation (31). As such, this reduction should have the same advantage at breaking the extraction property of Π. We reach a contradiction. As such, it only remains to prove Claim 6.3.

Proof of Claim 6.3. Assume for the sake of contradiction that the claim is false. This means there is an inverse polynomial gap between the game in Claim 6.3 and Equation (30). We define a reduction to the multi-theorem zero-knowledge property of Π as follows:

The view of A matches that of our protocol in Figure 6 or Sim0 and Sim1. As such, this reduction should have the same advantage at breaking the adaptive multi-theorem computational zero-knowledge property of Π. We reach a contradiction.

We reach a contradiction in both scenarios, hence our protocol must be unclonable.

Corollary 6.4. Assuming the polynomial quantum hardness of LWE, injective one-way functions exist, post-quantum iO exists, there exists an unclonable SimExt-secure signature of knowledge (Definition 6.1).

Proof. This follows from Corollary 4.13 and Theorem 6.2.

6.3 Revocable Anonymous Credentials

In this section, we will see how to use unclonable signatures of knowledge to construct an anonymous credentials scheme which has a natural revocation property.

Definition 6.5 (Revocable Anonymous Credentials). (IssuerKeyGen, Issue,VerifyCred, Revoke, Prove, VerRevoke) is a revocable anonymous credentials scheme with respect to some set of accesses {Sλ}λ∈N if it has the following syntax and properties.

Syntax. The input 1 λ is left out when it is clear from context.

• (nym,sk) ← IssuerKeyGen(1λ ): The probabilistic polynomial-time algorithm IssuerKeyGen is run by the issuer of the credentials. It takes input 1 λ ; and outputs a pseudonym nym with a secret key sk.

• cred ← Issue(1λ , nym,sk, access): The polynomial-time quantum algorithm Issue is run by the issuer of the credentials. It takes input the issuer’s keys nym and sk as well as the requested access access ∈ Sλ; and outputs a quantum credential cred along with a classical identifier id.

• VerifyCred(1λ , nym, access, cred) ∈ {0, 1}: The polynomial-time quantum algorithm VerifyCred is run by a verifier of the user’s credentials. It takes input the issuer’s pseudonym nym, the requested access access ∈ Sλ, and a credential cred; and outputs 1 iff cred is a valid credential for access access with respect to nym.

• revnotice ← Revoke(1λ , nym,sk, access): The polynomial-time quantum algorithm Revoke is run by the issuer of the credentials. It takes input the issuer’s keys nym and sk, and the access access being revoked; and outputs a notice of revocation revnotice.

• π ← Prove(1λ , nym,revnotice, cred): The polynomial-time quantum algorithm Prove is run by the user of the credentials. It takes input the issuer’s pseudonym nym, and a revocation notice revnotice, and the credential to be revoked cred which is identified by revnotice; and outputs a proof of revocation π.

• Ver Revoke(1λ , nym, sk, access, revnotice, π) ∈ {0, 1}: The polynomial-time quantum algorithm VerRevoke is run by the issuer of the credentials. It takes input the issuer’s keys nym and sk, the access access being revoked, the revocation notice revnotice, and a proof of revocation π; and outputs 1 iff π is a valid proof that the user’s access to the credential identified by id has been revoked.

Properties.

• Correctness: For every sufficiently large λ ∈ N, and every access ∈ Sλ,

• Revocation: For every polynomial-size quantum circuit A, there exists a negligible function negl(·) such that for sufficiently large λ ∈ N, and every access ∈ Mλ

REMARK 6.1. Unlike previous literature, the users that get issued credentials do not have their own identity. We also define algorithms for a three-message revocation process as opposed to the polynomial-message revocation process defined in the literature.

We now introduce a construction based on unclonable signatures of knowledge.

Theorem 6.6. Let (X ,W) be a hard-distribution of instance and witness pairs for some NP relation. Let {Sλ}λ∈N be some set of accesses. Let (Setup, Sign, Verify) be an unclonable-extractable SimExt-secure signature of knowledge for message space {Sλ}λ∈N (Definition 6.1).

(IssuerKeyGen, Issue,VerifyCred, Revoke, Prove, VerRevoke) defined in Figure 7 is a revocable anonymous credentials scheme (Definition 6.5).

Proof Sketch. The correctness of this revocable anonymous credentials scheme follows from the correctness of the unclonable signature of knowledge scheme.

We will now sketch the proof of revocation. Say that there exists an adversary A, access access, and polynomial p(·) such that, with probability at least 1/p(λ): (1) π passes the revocation check, and (2) cred′ passes the credential check. This means that both π and cred′ are valid signatures with respect to the same crs, x, and access that the signature cred was issued under. This satisfies the “if”

condition of the unclonability property of the unclonable signature of knowledge. As such, there exists a polynomial q(·) such that the unclonable signature of knowledge’s extractor can produce a witness w for x with probability at least 1/q(λ). However, this contradicts the hardness of the distribution (X ,W). Hence, our protocol must have the revocation property.

Corollary 6.7. Assuming the polynomial quantum hardness of LWE, injective one-way functions exist, post-quantum iO exists, and the hardness of NP, there exists a revocable anonymous credentials scheme (Definition 6.5).

Proof. This follows from Corollary 6.4 and Theorem 6.6.