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.pdfI'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.
Are there any implementations for zero-knowledge proofs of NP-complete problems?
zero knowledge;implementation;np complete
The answer is yes, check the following paper:SNARKs for C: Verifying Program Executions Succinctly and in Zero KnowledgeEli Ben-Sasson and Alessandro Chiesa and Daniel Genkin and Eran Tromer and Madars Virzahttp://eprint.iacr.org/2013/507(also published at Crypto 2013)