This paper is available on arxiv under CC 4.0 license.
Authors:
(1) Ruta Jawale;
(2) Dakshita Khurana.
Unclonable Non-Interactive Zero-Knowledge in the CRS Model
Unclonable NIZK in the Quantum Ramdon Oracle Model
Unclonable Signatures of Knowledge
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.
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.
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).
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.
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.