I only have a (very) introductory knowledge about the Hardness of Approximation and PCP theorem, and I am wondering if it has any specific implications (or can somehow be studied) with Zero Knowledge Proofs?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
PCPs are very often used to construct ZKPs, especially for NP-complete languages. The idea is simple: you commit to every bit of PCP separately, and then the prover makes random queries to the PCP. Given the query and committed bit, you prove in ZK that the bits in concrete locations would make the prover to accept. Since the number of queries is small, the proof is relatively efficient.
The main problem tends to be the computational complexity: generating a PCP for an arbitrary NP language is efficient only in theory, and thus people look for more efficient solution.
A recent related paper, that does something in between is by Bitansky and others (TCC 2013) where they study "linear PCPs" and their relation to ZK. Since linear PCPs (see their paper) are less stringent than general PCPs, they can be constructed more efficiently.
-
$\begingroup$ For more information, see for example Kilian's classical paper from 1994, and there's a lot of followups (culminating with those "linear PCPs" papers, for example) $\endgroup$ Oct 1, 2013 at 22:32
-
$\begingroup$ were you taking about the paper Igor Shinkar suggested? $\endgroup$– SubhayanOct 2, 2013 at 15:31
-
$\begingroup$ No, this paper: "A note on efficient zero-knowledge proofs and arguments" (Kilian, 1991) $\endgroup$ Oct 3, 2013 at 23:52
$\begingroup$
$\endgroup$
There is a classical paper of Feige and Killian Zero Knowledge and the Chromatic Number that uses the ideas from Zero Knowledge Proofs in order to construct PCPs with certain "ZKP-type" properties. Using these properties they prove that it is NP-hard to color a $N^{0.01}$-colorable graph with $N^{0.99}$-colors.
It should be noted that their result does not rely on any commitment schemes, or any other cryptographic assumptions. The only assumption they make is $NP \not\subseteq ZPP$, that is, their PCP-reduction is randomized, and not deterministic.
