Non-Interactive ZK Proofs for All of NP | Massachusetts Institute of Technology - Edubirdie

University:
Massachusetts Institute of Technology
Course:
6.876J | Advanced Topics in Cryptography
Academic year:

2023
Views:

142

Pages:

9
Author:

not1a304tv

6.876/18.426: Advanced Cryptography March 12, 2003 Lecture 10: Non-Interactive ZK Proofs for all of NP 1 Recap Last lecture we defined the notion of a non-interactive proof system (NIPS), and constructed a non-interactve zero-knowledge (NIZK) proof system for a "special" language of pairs: L=((n,y): ne 2PPAYE QNROJ+1). Today, we'll see how to use the proof system constructed for this "special" language L as a stepping stone in building a computational NIZK proof system for any NP language. 2 (Bounded) NIZK Proof Systems Revisited Recall that we say that (P,V) is a (perfect) NIZK proof system for language L if the following conditions hold: 1. Completeness: Vze L, Vwe Wz, Pro (0,1); - P(1,0,0): V(κ.σ. π) = "YES")>1-negl (10) 2. (Strong) Soundness: VP', Pro+ (0,1); (2), π) ε Ρ'(σ): V(2',σ,π') = "YES") < negl (0) Note that here, z and n are polynomially related whenever P' is PPT. However, technically, we should enforce this property even for unbounded P'. 3. ZKness: SPPT, VI E L.Va, S(z,a) = VIEW (2,4). Remarks Recall that o denotes a common random reference string, which is in open view of both parties, and is fixed outside of their control (e.g. the Rand reference table). Note throughout we may think of P as being PPT, since he receives a witness we W as input, where W. denotes the set of all witnesses for the theorem L. Alternatively, we may think of P as being of unbounded power as usual, who then can compute a witness from the common input. The statement of soundness above is the strengthened form from last lecture. That is we assume that the malicious prover P' possesses an algorithm which, when given a particular reference string o, will generate a pair (','), such that' is P's attempt at a "proof" Here and following we omit the understood modulus n and just write J+1=(y()=1) for the set of all remainders mod n with Jacobi symbol +1). (with respect to a) of the false theorem L; Le, after seeing the malicious prover P gets to choose the particular false theorem ' whose validity he will try to convince V of. "Bounded" NIPS We will say that a proof system (P, V) satisfying the above statements of (1) Complete- ness and (2) Soundness is a bounded NIPS (non-interactive proof system) for language L. This highlights the fact that the length of any theorem which we may prove in such a system is bounded above by a (polynomial) function of the length of the reference string σ. Or, the other way around, if we want to prove a theorem of a certain length, this will require access to a sufficiently long reference string o. For example, in last lecture in the proof system for the special language L, in order to prove (n,y) EL we assumed that the given was long enough so that we could subdivide it into many sections each of length n. 3 Applications of NIZK on the horizon The power of the ZK protocols we've seen previously depended on interaction and random- ness (unpredictability of the verifier's coin flips). In contrast, the concept of a NIZK proof is very attractive: the verifier V never talks, and hence we don't need to refer at all to a malicious V' in the definition of ZKness. Herein lies a great advantage of NIZK proof systems. Indeed, the VIEW referred to in the ZKness definition above is given without machine parameters, since the VIEW of a NIZK proof essentially contains: (σ,πα (1)), where (2) is a proof of the common input theorem z, given with respect to the ơ, the externally fixed, publicly viewable reference string. This freedom will prove to be extremely useful in constructing secure multi-party computation protocols, something to be seen later in the course. 4 Observations on NIZK for L and beyond Up to now we have just seen a single example of a NIZK proof system, the one from last lecture for the language of pairs: L={(ny):n2PPAYE QNROJ] In this lecture we will see how to generalize from a NIZK proof system for the special language L to one for any NP language. 4.1 Limitations of NIZK for L and beyond 1. Boundedness: 72 must be short relative to σ 2. This L is just one "special" language. 3. The quantification of a gives less than ideal strength to the definition. Let's examine the above limitations one by one.

Related Documents

Non-Interactive ZK Proofs for All of NP

Non-Interactive ZK Proofs for All of NP - Page 1

Non-Interactive ZK Proofs for All of NP - Page 2

Non-Interactive ZK Proofs for All of NP - Page 3

Non-Interactive ZK Proofs for All of NP - Page 4

Non-Interactive ZK Proofs for All of NP - Page 5

Non-Interactive ZK Proofs for All of NP - Page 6

Non-Interactive ZK Proofs for All of NP - Page 7

Non-Interactive ZK Proofs for All of NP - Page 8

Non-Interactive ZK Proofs for All of NP - Page 9

of 9

Recommended Documents

Lunchtime and Chosen Ciphertext Security

Lunchtime and Chosen Ciphertext Security

Massachusetts Institute of Technology 6.876J | Advanced Topics in Cryptography

Lecture Note

Secure Multi-Party Computation in the HBC Model

Secure Multi-Party Computation in the HBC Model

Massachusetts Institute of Technology 6.876J | Advanced Topics in Cryptography

Lecture Note

NIZK and the Lunchtime Attack

NIZK and the Lunchtime Attack

Massachusetts Institute of Technology 6.876J | Advanced Topics in Cryptography

Lecture Note