4
$\begingroup$

It's been known for a long time that any claim in NP has a zero-knowledge proof for it. Has anybody actually implemented a zero-knowledge proof system for a NP-complete language? Using a search engine, the most relevant thing I could find is this:

www.usenix.org/event/sec10/tech/full_papers/Meiklejohn.pdf

I'm not exactly sure what the scope of ZKPDL, but it looks like it's a combination of many special-purpose zero-knowledge protocols, and that it is not intended to NP-complete. It might turn out to be NP-complete with clauses like "x in [0,1]" and "x*y=z" allowing a reduction from SAT to the languages described there. However, the reduction doesn't seem natural or efficient.

The reason I'm asking this is that I'm currently working on an implementation of a NP-complete zero-knowledge protocol and I want to know what the prior work is.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

The answer is yes, check the following paper:

SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge Eli Ben-Sasson and Alessandro Chiesa and Daniel Genkin and Eran Tromer and Madars Virza http://eprint.iacr.org/2013/507 (also published at Crypto 2013)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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