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

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

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

CC BY-SA 3.0
2013-10-01T22:32:12.967Z
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)
cryptocat
CC BY-SA 3.0
2013-10-02T15:31:48.860Z
were you taking about the paper Igor Shinkar suggested?
Subhayan
CC BY-SA 3.0
2013-10-03T23:52:09.947Z
No, this paper: "A note on efficient zero-knowledge proofs and arguments" (Kilian, 1991)
cryptocat
CC BY-SA 3.0
2013-10-01T17:11:41.507Z
2013-10-01T17:11:41.507Z
cryptocat
<p>There is a classical paper of Feige and Killian <a href="http://www.wisdom.weizmann.ac.il/~feige/Approx/coloring.ps" rel="nofollow">Zero Knowledge and the Chromatic Number</a> 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.</p>

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

CC BY-SA 3.0
2013-10-02T15:01:52.817Z
2013-10-02T15:01:52.817Z
Igor Shinkar
<p>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?</p>

CC BY-SA 4.0
2024-12-28T14:02:23.393Z
There is a wonderful result this year (2024) to show that they can construct perfect zero-knowledge probabilistically checkable proofs for every language
in #P. https://dl.acm.org/doi/10.1145/3618260.3649698
Zunchen Huang
<pcp><zero-knowledge><intuition>
How are PCPs and ZKPs related?
Subhayan
# How are PCPs and ZKPs related?

(Asked by: username_0 on 2013-10-01)

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?

**Tags:** pcp, zero-knowledge, intuition
> **Comments:**
> **username_1**: There is a wonderful result this year (2024) to show that they can construct perfect zero-knowledge probabilistically checkable proofs for every language in #P. https://dl.acm.org/doi/10.1145/3618260.3649698  

---

## 2 answers

### Answer by username_2 on 2013-10-01. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_2**: 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)  
> **username_0**: were you taking about the paper Igor Shinkar suggested?  
> **username_2**: No, this paper: "A note on efficient zero-knowledge proofs and arguments" (Kilian, 1991)  

---

### Answer by username_3 on 2013-10-02. Score: 1

There is a classical paper of Feige and Killian [Zero Knowledge and the Chromatic Number](http://www.wisdom.weizmann.ac.il/~feige/Approx/coloring.ps) 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.


---

