8
$\begingroup$

When I read about zero knowledge proof, I keep encountering the term NP-statement. I am aware of complexity classes but I am a little unclear on how it ties up to NP-statement.

I came across the following here: C++ library for zkSNARKs

A computation can be expressed as an NP statement, in forms such as the following:

  • "The C program foo, when executed, returns exit code 0 if given the input bar and some additional input qux."

  • "The Boolean circuit foo is satisfiable by some input qux."

  • "The arithmetic circuit foo accepts the partial assignment bar, when extended into some full assignment qux."

  • "The set of constraints foo is satisfiable by the partial assignment bar, when extended into some full assignment qux."

A prover who knows the witness for the NP statement (i.e., a satisfying input/assignment) can produce a short proof attesting to the truth of the NP statement.

Can any body show how an NP problem can be described in the form of an NP statement with an example?

$\endgroup$
2
$\begingroup$

Formally, zero-knowledge proof (ZKP) is constructed on top of NP problems. In ZKP, a prover intends to prove to a verifier that he knows the solution (witness) of some published NP-problem, without revealing this solution.

NP statement is actually a description of the NP problem.

So, roughly speaking, NP statement is what you want to prove/verify in ZKP.

$\endgroup$
  • $\begingroup$ Can you elaborate more by giving an example of the line "NP statement is actually a description of the NP problem."? Can you describe an NP Problem and its related NP statement? That would be the perfect answer to this question $\endgroup$ – tatepairing Dec 5 '18 at 22:29
  • 1
    $\begingroup$ @tatepairing sure. The most popular NP-complete problem is SAT (en.wikipedia.org/wiki/…): given a boolean formula, answer whether it's "satisfiable" or not. Satisfiable means that there's some set of variable values which turn the formula into True. So, NP-statement here is a description of boolean formula (in some format, for example "(x1 ^ x2) ∨ x3". The corresponding witness is some set of values x1, x2, x4 which turns the formula into True. You can find a witness for this specific formula as a simple exercise. $\endgroup$ – Mikhail Koipish Dec 6 '18 at 10:34
  • $\begingroup$ To provide a proof that the formula is satisfiable, you can just show the witness. But this usually means revealing of a secret, which is inappropriate. So the magic of ZKP allows providing of proof without revealing the witness. $\endgroup$ – Mikhail Koipish Dec 6 '18 at 10:46
  • $\begingroup$ Thank you that is helpful. Can you also point to a textbook where there is more detail about NP statements specifically? Also, what is your view on what Ruben De Smet's assertion that NP statement is an instance of NP problem? $\endgroup$ – tatepairing Dec 7 '18 at 23:19
  • 1
    $\begingroup$ @tatepairing I'm not sure what exactly you don't understand, but worth to note that "NP-statement" is not a some specific term, it's just a short for "a statement of NP-problem" (like a formulation of a problem, or a description). Of course not of a class of problems (like SAT for all functions), but for a specific instance (SAT for a certain boolean formula). $\endgroup$ – Mikhail Koipish Dec 8 '18 at 12:19
4
$\begingroup$

Intuitively, an NP problem is one that if you have a solution it is computationally easy to verify it, but it is not known if it is also computationally easy to find. Of course there exist formal definitions, based on deterministic and non deterministic Turing machines. Any standard complexity textbook will have these definitions.

Their connection with zero knowledge proofs comes from the 1987, Goldreich, Micali and Wigderson paper that proves that all NP problems have zero knowledge proofs (assuming secure bit commitment). An excellent tutorial on how this is done can be found in Matthew Green's blog. All this were written for classical zero knowledge systems, but they apply to zkSnarks as well.

$\endgroup$
1
$\begingroup$

A decision problem is an NP problem when it runs in polynomial time on a non-deterministic Turing machine. It is a big class of problems, that contains most problems that you are used to: boolean satisfaction (NP-complete $\subset$ NP), and also the "easier" problems (polynomial time on a deterministic Turing machine): "is this list sorted?". Intuitively, NP contains problems that run in exponential time or faster.

When we say that an NP-statement can be proven in zero-knowledge (what indeed Goldreich et al. proved), it means that any NP problem instance can be proven to be true in zero-knowledge. For example, that a specific list is sorted has a proof protocol in zero-knowledge.

$\endgroup$
  • $\begingroup$ An NP statement is an instance of an NP problem? Can you point me to some text book or blog where I can read more details about what an NP statement is? $\endgroup$ – tatepairing Dec 7 '18 at 23:15
  • 1
    $\begingroup$ I think it's mostly a question of understanding complexity theory. A statement in NP is some problem instance that can be proven in non-deterministic polynomial time. I don't have any blog or text book in mind that will explain it any better than just that. $\endgroup$ – Ruben De Smet Dec 8 '18 at 10:20
0
$\begingroup$

NP statements are those that, in this context, cannot be easily generated without knowing some secret (a proving key for zk-SNARK circuits). They are easily verifiable, however. In the case of zk-SNARKs, only demonstrate knowledge of a secret without revealing any information without a decryption key. When a paper mentions a language NP, they are referring to statements that satisfy the above properties. zk-SNARKs are an example of NP statements, so are cryptographic signatures and CRHF outputs.

NP is short for Non-deterministic Polynomial. P is short for Polynomial. Often, these refer to time complexity, less often for space (disk/RAM usage) complexity. NP is called NP because they can be solved with NP Turing machines, which can be thought of as infinite computers running every possible solution of a problem at the same time, and arriving at the solution in a polynomial amount of time. This is clearly impossible with current technology. Complexity classes tend to overlap as well, with some NP problems being part of BQP, such as RSA semiprime factorization, elliptic curve and regular discrete logarithm problems. These are breakable with sufficiently powerful quantum computers under polynomial time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.