<p>The answer is yes, check the following paper:</p>

<p>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
<a href="http://eprint.iacr.org/2013/507" rel="nofollow">http://eprint.iacr.org/2013/507</a>
(also published at Crypto 2013)</p>

CC BY-SA 3.0
2013-09-18T05:36:09.743Z
2013-09-18T05:36:09.743Z
cryptocat
<p>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:</p>

<p>www.usenix.org/event/sec10/tech/full_papers/Meiklejohn.pdf</p>

<p>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.</p>

<p>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.</p>

<zero-knowledge><implementation><np-complete>
Are there any implementations for zero-knowledge proofs of NP-complete problems?
Itai Bar-Natan
# Are there any implementations for zero-knowledge proofs of NP-complete problems?

(Asked by: username_0 on 2013-09-16)

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.

**Tags:** zero-knowledge, implementation, np-complete


---

## 1 answers

### Answer by username_1 on 2013-09-18. Score: 3 | Accepted answer

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)


---

