FRESH

Hacker News

Home

Zero knowlege proof of compositeness

113 points by ColinWright

by tooltower

5 subcomments

Are we sure that the base reveals nothing about the factors if n is composite? I have never seen a proof of that.
Usually, zero knowledge proofs also require a prover who knows the answer (the factors in this case). This is just a primality test that can be performed locally.

by jeremysalwen

1 subcomments

To be honest I feel like I have seen much better expositions of zero knowledge proofs. The playing cards example is nice in some ways, but people are often exposed to trickery regarding playing cards. The recipient of the proof needs to verify that the deck of cards is a normal deck of cards, that no cards have been swapped out or altered, etc. These are all precisely the things that magicians are regularly able to fool people about. So really you have to make an additional assumption of "no funny business", which distracts from the mathematical core of what you are trying to demonstrate.
Likewise, the example of compositeness is a bit off because even though there is knowledge about the composite number that the proof does not reveal, that knowledge is in fact not known the to person constructing the proof either! The proof is not really zero knowledge either, since it gives the reader knowledge of a specific witness to its compositeness.
Even the wikipedia example of going into the cave (which used to be featured more prominently in the article) I think is terrible. Why wouldn't you just walk a loop to prove you know the way through the secret door? Also, it's clearly not zero knowledge, as it reveals some information about how quickly they can pass through the gate.
In general I think avoiding physical examples is necessary, since reality is complicated, and in the real world some information always leaks.
I think the best example for teaching about ZKPs is the graph isomorphism problem: Given two large graphs, you can prove that you know a isomorphism between two graphs by generating a new randomly labeled graph that is isomorphic to both of them and showing it to the provee, who can then ask you to demonstrate that this new graph is isomorphic to either graph A or graph B. Since you don't know ahead of time which one they will ask for, the only way you could consistently pass this test is if you actually do have a graph that was isomorphic to both A and B simultaneously. But since you only reveal one of the isomorphisms, it really is zero knowledge.

by petermcneeley

0 subcomment

A much smaller simpler example would have been useful for us mere mortals.
Ok 6 is not a prime. 5=b is not a multiple of 6
5^(6-1) = 3125 mod 6 = 5 which is not 1. Therefore 6 cannot be prime.

by jstanley

3 subcomments

> A zero knowledge proof (ZKP) answers a question without revealing anything more than answer. For example, a digital signature proves your possession of a private key without revealing that key.
I don't think a digital signature is a Zero-Knowledge Proof because someone else could copy and paste the signature and then it would look like they know the key, and because other third parties could check whether the signature was valid or not.
To be a true Zero-Knowledge Proof it needs to:
* show that you know the thing without revealing the thing
* not allow other people to copy your answer
* not allow anyone other than your intended counterparty to even verify the answer

by spir

0 subcomment

If you like zero knowledge proofs, check out https://ethproofs.org/blocks