<p>The default answer is that it is probably not very interesting for the reasons the researcher articulated to you.</p>
<p>An exception would be if there is some property of your protocol that is not satisfied by existing, standard constructions and that is interesting or useful.  For example, if your protocol is significantly more efficient than reducing to some other problem with a known ZKP, and you can argue that there is some important application or setting where that efficiency is needed, that might make your scheme interesting.  The burden then falls on you to articulate what that property is and make the case why it is interesting or useful.</p>
<p>But just having another way to do it that is different is unlikely to be interesting, unless there is something more.</p>

CC BY-SA 4.0
2024-09-19T08:14:18.570Z
2024-09-19T22:15:46.603Z
2024-09-19T22:15:46.603Z
D.W.
<p>I am a final-year PhD student in mathematics, though my research is not directly related to computer science. As a hobby, I have been reading Avi Wigderson's <a href="https://www.math.ias.edu/avi/book" rel="nofollow noreferrer">Mathematics and Computation</a>, where I encountered zero-knowledge proofs for the first time. Recently, I devised a zero-knowledge argument for a discrete geometry problem, proving that the protocol satisfies completeness, computational soundness, and zero-knowledge. The problem in question is NP-complete.</p>
<p>When discussing this with a computational geometry researcher, they suggested that constructing zero-knowledge proofs for NP-complete problems is not particularly meaningful, since any NP-complete problem can be reduced to Graph 3-colorability in polynomial time, and there already exists a zero-knowledge proof for that problem. However, my construction does not rely on reducing the problem to 3-colorability or any other known problem with an existing ZKP.</p>
<p>Is it true that developing zero-knowledge proofs for NP-complete problems is generally not a worthwhile pursuit? Should such efforts be dismissed given the existence of reductions to problems with established ZKPs, or is there value in exploring new constructions for specific problems?</p>

CC BY-SA 4.0
2024-09-19T06:47:13.963Z
(sometimes) efficiency is important and reductions can make the protocol inefficient.
Mohsen Ghorbani
CC BY-SA 4.0
2024-09-19T07:34:19.303Z
There is value in interesting new facts. The mere existence of a ZKP for an NP problem is something we already know, so to make it worthwhile, it would have to have some *additional* properties that make it interesting. This is ultimately a subjective judgement call.
Emil Jeřábek
CC BY-SA 4.0
2024-09-20T09:43:42.340Z
@EmilJeřábek Pardon my lack of familiarity with the subject, could you please name some of these additional properties or perhaps direct me towards an example of a ZKP exhibiting these properties?
rr314
CC BY-SA 4.0
2024-09-20T10:14:34.763Z
I am not particularly familiar with ZKP as such; my comment was a general principle. Efficiency and/or simplicity may be such properties, but as I wrote, it is a judgment call. What happens more commonly is that people develop a new protocol (or other kind of formal object) *because* they have a specific need that is not satisfied by existing tools, whereas what you have seems to be kind of a solution in want of a problem.
Emil Jeřábek
<cc.complexity-theory><cr.crypto-security><computational-geometry><interactive-proofs><zero-knowledge>
Finding zero-knowledge protocols for NP-complete problems
rr314
# Finding zero-knowledge protocols for NP-complete problems

(Asked by: username_0 on 2024-09-19)

I am a final-year PhD student in mathematics, though my research is not directly related to computer science. As a hobby, I have been reading Avi Wigderson's [Mathematics and Computation](https://www.math.ias.edu/avi/book), where I encountered zero-knowledge proofs for the first time. Recently, I devised a zero-knowledge argument for a discrete geometry problem, proving that the protocol satisfies completeness, computational soundness, and zero-knowledge. The problem in question is NP-complete.

When discussing this with a computational geometry researcher, they suggested that constructing zero-knowledge proofs for NP-complete problems is not particularly meaningful, since any NP-complete problem can be reduced to Graph 3-colorability in polynomial time, and there already exists a zero-knowledge proof for that problem. However, my construction does not rely on reducing the problem to 3-colorability or any other known problem with an existing ZKP.

Is it true that developing zero-knowledge proofs for NP-complete problems is generally not a worthwhile pursuit? Should such efforts be dismissed given the existence of reductions to problems with established ZKPs, or is there value in exploring new constructions for specific problems?

**Tags:** cc.complexity-theory, cr.crypto-security, computational-geometry, interactive-proofs, zero-knowledge

> **Comments:**
> **username_1**: (sometimes) efficiency is important and reductions can make the protocol inefficient.  
> **username_2**: There is value in interesting new facts. The mere existence of a ZKP for an NP problem is something we already know, so to make it worthwhile, it would have to have some *additional* properties that make it interesting. This is ultimately a subjective judgement call.  
> **username_0**: @EmilJeřábek Pardon my lack of familiarity with the subject, could you please name some of these additional properties or perhaps direct me towards an example of a ZKP exhibiting these properties?  
> **username_2**: I am not particularly familiar with ZKP as such; my comment was a general principle. Efficiency and/or simplicity may be such properties, but as I wrote, it is a judgment call. What happens more commonly is that people develop a new protocol (or other kind of formal object) *because* they have a specific need that is not satisfied by existing tools, whereas what you have seems to be kind of a solution in want of a problem.  

---

## 1 answers

### Answer by username_3 on 2024-09-19. Score: 2

The default answer is that it is probably not very interesting for the reasons the researcher articulated to you.

An exception would be if there is some property of your protocol that is not satisfied by existing, standard constructions and that is interesting or useful. For example, if your protocol is significantly more efficient than reducing to some other problem with a known ZKP, and you can argue that there is some important application or setting where that efficiency is needed, that might make your scheme interesting. The burden then falls on you to articulate what that property is and make the case why it is interesting or useful.

But just having another way to do it that is different is unlikely to be interesting, unless there is something more.


---

