Unclonable Non-Interactive Zero-Knowledge: Preliminaries
by EScholar: Electronic Academic Papers for ScholarsNovember 24th, 2023
Too Long; Didn't Read
A non-interactive ZK (NIZK) proof enables verification of NP statements without revealing secrets about them. However, an adversary that obtains a NIZK proof may be able to clone this proof and distribute arbitrarily many copies of it to various entities: this is inevitable for any proof that takes the form of a classical string. In this paper, we ask whether it is possible to rely on quantum information in order to build NIZK proof systems that are impossible to clone. We define and construct unclonable non-interactive zero-knowledge proofs (of knowledge) for NP. Besides satisfying the zero-knowledge and proof of knowledge properties, these proofs additionally satisfy unclonability. Very roughly, this ensures that no adversary can split an honestly generated proof of membership of an instance x in an NP language L and distribute copies to multiple entities that all obtain accepting proofs of membership of x in L. Our result has applications to unclonable signatures of knowledge, which we define and construct in this work; these non-interactively prevent replay attacks.
This paper is available on arxiv under CC 4.0 license.
Authors:
(1) Ruta Jawale;
(2) Dakshita Khurana.
Table of Links
Unclonable Non-Interactive Zero-Knowledge in the CRS Model
Unclonable NIZK in the Quantum Ramdon Oracle Model
Unclonable Signatures of Knowledge
3 Preliminaries
3.1 Post-Quantum Commitments and Encryption
Definition 3.1 (Post-Quantum Commitments). Com is a post-quantum commitment scheme if it has the following syntax and properties.
Syntax.
• c ← Com(m; r): The polynomial-time algorithm Com on input a message m and randomness r ∈ {0, 1} r(λ) outputs commitment a c.
Properties.
Theorem 3.2 (Post-Quantum Commitment). [LS19] Assuming the polynomial quantum hardness of LWE, there exists a non-interactive commitment with perfect binding and computational hiding (Definition 3.1).
Definition 3.3 (Post-Quantum Public-Key Encryption). (Gen, Enc, Dec) is a post-quantum publickey encryption scheme if it has the following syntax and properties.
Syntax.
• (pk,sk) ← Gen(1λ ): The polynomial-time algorithm Gen on input security parameter 1 λ outputs a public key pk and a secret key sk.
• c ← Enc(pk, m; r): The polynomial-time algorithm Enc on input a public key pk, message m and randomness r ∈ {0, 1} r(λ) outputs a ciphertext c.
• m ← Dec(sk, c): The polynomial-time algorithm Dec on input a secret key sk and a ciphertext c outputs a message m.
Properties.
3.2 Sigma protocols
Definition 3.4 (Post-Quantum Sigma Protocol for NP). [LZ19] Let NP relation R with corresponding language L be given such that they can be indexed by a security parameter λ ∈ N.
Π = (P = (P.Com, P.Prove),V = (V.Ch,V.Ver)) is a post-quantum sigma protocol if it has the following syntax and properties.
Syntax. The input 1 λ is left out when it is clear from context.
• (α,st) ← P.Com(1λ , x, w): The probabilistic polynomial-size circuit P.Com on input an instance and witness pair (x, w) ∈ Lλ outputs a commitment α and an internal prover state st.
• β ← V.Ch(1λ , x, α): The probabilistic polynomial-size circuit V.Ch on input an instance x outputs a uniformly random challenge β.
• γ ← P.Prove(1λ , x, w,st, β): The probabilistic polynomial-size circuit P. Prove on input an instance and witness pair (x, w) ∈ Lλ, an internal prover state st, and a challenge β outputs the partial opening (to α as indicated by β) γ.
• V. Ver(1λ , x, α, β, γ) ∈ {0, 1}: The probabilistic polynomial-size circuit V.Ver on input an instance x, a commitment α, a challenge β, and a partial opening γ outputs 1 iff γ is a valid opening to α at locations indicated by β.
Properties.
• Perfect Completeness. For every λ ∈ N and every (x, w) ∈ Rλ,
• Computational Honest-Verifier Zero-Knowledge with Quantum Simulator. There exists a quantum polynomial-size circuit Sim and a negligible function negl(·) such that for every polynomial-size quantum circuit D, every sufficiently large λ ∈ N, and every (x, w) ∈ Rλ,
• Unpredictable Commitment. There exists a negligible function negl(·) such that for every sufficiently large λ ∈ N and every (x, w) ∈ Rλ,
We note that the unpredictable commitment property in the definition above may appear to be an unusual requirement, but this property is w.l.o.g. for post quantum sigma protocols as shown in [LZ19]. In particular, any sigma protocol which does not have unpredictable commitments, can be modified into one that does: the prover can append a random string r to the end of their commitment message α, and the verifier can ignore this appended string r when they perform their checks.
3.3 NIZKs in the CRS model
We consider the common reference string model.
Definition 3.5 (Post-Quantum (Quantum) NIZK for NP in the 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 non-interactive post-quantum (quantum) zero-knowledge argument for NP in the CRS model if it has the following syntax and properties.
Syntax. The input 1 λ is left out when it is clear from context.
• crs ← Setup(1λ ): The probabilistic polynomial-size circuit Setup on input 1 λ outputs a common reference string crs.
• π ← P(1λ , crs, x, w): The probabilistic (quantum) polynomial-size circuit P on input a common reference string crs and instance and witness pair (x, w) ∈ Rλ, outputs a proof π.
• V(1λ , crs, x, π) ∈ {0, 1}: The probabilistic (quantum) polynomial-size circuit V on input a common reference string crs, an instance x, and a proof π outputs 1 iff π is a valid proof for x.
Properties.
• Perfect Completeness. For every λ ∈ N and every (x, w) ∈ Rλ,
• Adaptive Computational Soundness. There exists a negligible function negl(·) such that for every polynomial-size quantum circuit A and every sufficiently large λ ∈ N,
• Adaptive Computational Zero-Knowledge. There exists a probabilistic (quantum) polynomial-size circuit Sim = (Sim0, Sim1) and a negligible function negl(·) such that for every polynomial-size quantum circuit A, every polynomial-size quantum circuit D, and every sufficiently large λ ∈ N,
Theorem 3.6 (Post-Quantum NIZK argument for NP in the CRS Model). [PS19] Assuming the polynomial quantum hardness of LWE, there exists a non-interactive adaptively computationally sound, adaptively computationally zero-knowledge argument for NP in the common reference string model (Definition 3.5).
Definition 3.7 (Post-Quantum (Quantum) Simulation-Sound 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-sound, adaptive multi-theorem computational zero-knowledge protocol for NP in the CRS model if it has the following syntax and properties.
• Π is a post-quantum (quantum) non-interactive zero-knowledge argument for NP in the CRS model (Definition 3.5).
• Adaptive Multi-Theorem Computational Zero-Knowledge. [FLS90] There exists a probabilistic (quantum) polynomial-size circuit Sim = (Sim0, Sim1) 1 and a negligible function negl(·) such that for every polynomial-size quantum circuit A, every polynomial-size quantum circuit D, and every sufficiently large λ ∈ N,
• Simulation Soundness. [Sah99, SCO+01] Let Sim = (Sim0, Sim1) be the simulator given by the adaptive multi-theorem computational zero-knowledge property. There exists a negligible function negl(·) such that for every oracle-aided polynomial-size quantum circuit A and every sufficiently large λ ∈ N,
where Q is the list of queries from A to Sim1.
REMARK 3.1. In Definition 3.7, adaptive multi-theorem computational zero-knowledge implies adaptive computational zero-knowledge.
REMARK 3.2. As defined in Definition 3.7, a simulation-sound zero-knowledge protocol has adaptive computational soundness (Definition 3.5).
Theorem 3.8 (Simulation Sound Compiler). [SCO+01] Given one-way functions and a single-theorem NIZK proof system for NP, then there exists a non-interactive simulation sound, adaptively multi-theorem computationally zero-knowledge proof for NP in the common reference string model (Definition 3.7).
Corollary 3.9 (Post-Quantum Simulation Sound NIZK for NP). Assuming the polynomial quantum hardness of LWE, there exists a post-quantum non-interactive simulation sound, adaptively multi-theorem computationally zero-knowledge proof for NP in the common reference string model (Definition 3.7).
Proof. This follows from Theorem 3.6 and Theorem 3.8.
3.4 NIZKs in the QRO model
We now consider the quantum random oracle model. For sake of completeness, we briefly outline a definition for a quantum random oracle.
Definition 3.10. A quantum random oracle O is a random function which support quantum queries and allows for the following accesses:
• Query Access. On input a message, O outputs a uniformly random value. This is the usual access provided. When quantum access may be invoked, we denote the oracle as |O.
• Programmability Access. Given programmability access, O can be set to output a specified value on a specified input. An arbitrary number of distinct points can be programmed.
• Extractability Access. Given extractability access, specific queries to |O can be read.
Definition 3.11 ((Quantum) Post-Quantum NIZKPoK for NP in QROM). [LZ19] Let O be a random oracle. Let NP relation R with corresponding language L be given such that they can be indexed by a security parameter λ ∈ N.
Π = (P,V) is a (quantum) non-interactive zero-knowledge proof of knowledge protocol with respect to a random oracle if it has the following syntax and properties.
Syntax. The input 1 λ is left out when it is clear from context.
Properties.
• Perfect Completeness. For every λ ∈ N and every (x, w) ∈ Rλ,
• Zero-Knowledge with Quantum Simulator. There exists a quantum polynomial-size circuit Sim which ignores its second input and a negligible function negl(·) such that for every oracle-aided polynomial-size quantum circuit D which is limited to making queries (x, ω) ∈ Rλ on input 1 λ , and every sufficiently large λ ∈ N,
• Proof of Knowledge with Quantum Extractor. There exists an oracle-aided quantum polynomial-size circuit extractor Ext that simulates a random oracle |OExti, a constant c, a polynomial p(·), and negligible functions negl0 (·), negl1 (·) such that for every polynomial-size quantum circuit A and every x with associated λ ∈ N satisfying
Theorem 3.12 (NIZKPoK in QROM [Unr17, LZ19]). Let Π be a post-quantum sigma protocol (Definition 3.4). The Fiat-Shamir heuristic applied to Π yields a classical post-quantum NIZKPoK in the QROM (Definition 3.11).
3.5 Quantum Money
Definition 3.13 (Public Key Quantum Money Mini-Scheme). [AC13, Zha19b] (Gen,Ver) is a public key quantum money scheme if it has the following syntax and properties.
Syntax.
Properties.
Theorem 3.14 (Quantum Money from Subspace Hiding Obfuscation [AC13, Zha19b]). If injective one-way functions and post-quantum iO exist, then public-key quantum money exists (Definition 3.13).
Definition 3.15 (Public Key Quantum Money Mini-Scheme in QROM). (Gen, Ver) is a public key quantum money scheme with respect to a quantum random oracle O if it has the following syntax and properties.
Syntax.
Properties
The unpredicable serial number property is w.l.o.g., just as above.
3.6 Quantum Signature of Knowledge
Definition 3.16 (Quantum SimExt-secure Signature [CL06]). 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.
(Setup, Sign, Verify) is a SimExt-secure quantum signature of knowledge of a witness with respect to L and M if it has the following syntax and properties. Syntax. The input 1 λ is left out when it is clear from context.
• (crs, td) ← Setup(1λ ): The probabilistic polynomial-time algorithm Setup on input 1 λ outputs a common reference string crs and a trapdoor td.
• σ ← Sign(1λ , crs, x, w, m): The polynomial-time quantum algorithm Sign on input a common reference string crs, an instance and witness pair (x, w) ∈ Rλ, and a message m ∈ Mλ, outputs a signature σ.
• Verify(1λ , crs, x, m, σ) ∈ {0, 1}: The polynomial-time quantum algorithm Verify on input a common reference string crs, an instance x, a message m ∈ Mλ, and a signature σ, outputs 1 iff σ is a valid signature of m with respect to crs, Rλ, and x.
Properties.
L O A D I N G
. . . comments & more!
. . . comments & more!
