[HN Gopher] Zero knowlege proof of compositeness
___________________________________________________________________
Zero knowlege proof of compositeness
Author : ColinWright
Score : 68 points
Date : 2025-11-29 17:53 UTC (5 hours ago)
(HTM) web link (www.johndcook.com)
(TXT) w3m dump (www.johndcook.com)
| tooltower wrote:
| 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.
| ColinWright wrote:
| My understanding is that there is a difference between the
| concept of a Zero-Knowledge Proof (ZKP), and then the
| applications that such a thing is possible.
|
| In the example given, I can prove that N is composite without
| revealing anything (well, _almost_ anything) about the factors.
| But in practice we want to use a ZKP to show that I have
| specific knowledge without revealing the knowledge itself.
|
| For example:
|
| You can give me a graph, and I can claim that I can three-
| colour it. You may doubt this, but there is a process by which
| I can ... to any desired level of confidence ... demonstrate
| that I have a colouring, without revealing what the colouring
| is. I colour the vertices RGB, map those colours randomly to
| ABC, and cover all the vertices. You choose any edge, and I
| reveal the "colours" (from ABC) of the endpoints. If I really
| can colour the graph then I will always be able to reveal two
| different colours. If I _can 't_ colour the graph then as we do
| this more and more, eventually I will fail.
|
| So you are right, but the message of the post is, I think,
| still useful and relevant.
| mathgradthrow wrote:
| can you explain this a little better?
| ColinWright wrote:
| I can certainly explain it more, a question of "better" is
| debatable!
|
| Here's the process:
|
| (A) You give me a graph to 3-colour;
|
| (B) I claim I can 3-colour it;
|
| (C) You demand that I prove it;
|
| (D) I colour it with colours ABC and cover the vertices;
|
| (E) You point at an edge;
|
| (F) I reveal the colours of the vertices at the ends of the
| edge;
|
| (G) If I have coloured the graph then the colours revealed
| will always be different;
|
| (H) We repeat this process with a permutation of the
| colours between each trial;
|
| (I) If I'm lying then eventually you'll pick an edge where
| either the vertices are not coloured, or the have the same
| colour.
|
| (J) This process reveals nothing about the colouring, but
| proves (to some level of confidence) that I'm telling the
| truth.
|
| So ... what's unclear?
|
| Instructions on how to email me are in my profile if you
| prefer ...
| kadoban wrote:
| How do I know/prove that you're not just saying any
| random two colors for whichever edge I choose?
| ColinWright wrote:
| The version I'm describing has it physically sitting in
| front of you at the time, so you can see that the colours
| haven't been changed "on the fly" after you pick an edge.
| In this version:
|
| (A) I colour it;
|
| (B) I cover the vertices so you can't see any of them,
| but I can no longer change them;
|
| (C) You choose the edge, and I reveal the endpoints.
|
| Converting this to a digital version requires further
| work ... my intent here was to explain the underlying
| idea that I can prove (to some degree of confidence) that
| I have a colouring without revealing anything about it.
|
| So just off the top of my head, for example, I can, for
| each vertex, create a completely random string that
| starts with "R", "G", or "B" depending on the colour of
| the vertex. Then I hash each of those, and send you all
| of them. You choose an edge and send me back the two
| hashes for the endpoints, and I provide the associated
| random strings so you can check that the hashes match.
| fragmede wrote:
| The key insight is that Colin can show you a red-green-blue
| coloring of the graph, and flip the whole graph secretly,
| so it's blue-red-green instead when you look at an
| individual section, but really the graph is yellow-pink-
| orange colored. Even after showing you all the
| intersections of the graph individually in the red green
| blue coloring to satisfy that he can 3-color it, you still
| have no idea what is yellow pink or orange on his copy of
| the graph.
| schoen wrote:
| We also don't technically have proofs for some of the
| computational hardness assumptions that popular "real" ZK proof
| constructions rely on!
|
| This might feel different because those assumptions were chosen
| in part because people had studied them and they certainly
| _seem_ to be right, whereas perhaps here nobody has really
| studied this particular random number theory topic one way or
| the other.
|
| But in some sense, there isn't a proof that regular ZK proof
| methods are actually completely zero-knowledge (against a
| computationally bounded adversary).
| madars wrote:
| That's a very good question. It all depends on how you pick the
| witness b: there is a procedure that definitely is _not_ zero-
| knowledge: say, if prover uses his knowledge of factorization
| to construct an explicit b that betrays that factorization.
|
| For example, if n = p1*p2*...*pk is square-free and not a
| Carmichael number, then by Korselt's criterion there exists a
| pi such that pi-1 does not divide n-1 (this also implies that
| pi>2). Use the Chinese Remainder Theorem to produce b such that
| b=1 (mod pj) for all j!=i, and b (mod pi) is a generator of
| (Z/piZ)^*. Then b is a Fermat witness: gcd(b, n) = 1 (because b
| is non-zero modulo every prime factor) and b^(n-1) != 1 (mod n)
| because b^(n-1) != 1 (mod pi) (as pi-1 does not divide n-1).
|
| However, b "betrays" the prime factorization of n, since
| gcd(b-1, n)>1 (by construction b-1 is divisible by all pj with
| j!=i, but not divisible by pi>2), and thus gcd(b-1, n) is a
| non-trivial factor of n. (I assumed square-free above but if
| pi^ei (ei>=2) divides n, then b=1+pi^(ei-1) (mod pi^ei), b=1
| (mod pj^ej) (j!=i) also would have worked.)
|
| On the other hand, it is also known that for non-Carmichael
| numbers at least half of the bases b with gcd(b, n) = 1 are
| Fermat witnesses. So if you pick b uniformly at random, the
| verifier does not gain any new information from seeing b: they
| could have sampled such a witness themselves by running the
| same random test. Put another way, the Fermat test itself is an
| OK ingredient, but a prover who chooses b in a factorization-
| dependent way can absolutely leak the factors - the final
| protocol won't be ZK.
| phkahler wrote:
| On a related note, I've often wondered what each congruence in
| the quadratic seive reveals. Once you have enough of them you
| can factor the number, but what does a partial set of
| congruences reveal?
|
| Its a matrix problem, so each row could be reducing the degrees
| of freedom of something. But what? And in what space?
| petermcneeley wrote:
| 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.
| jstanley wrote:
| > 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
| phkahler wrote:
| >> 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.
|
| One of us is confused. You can't copy a digital signature in a
| useful way. Without the message it doesnt mean anything. With
| the message its proof that the message was signed by someone
| with the private key.
|
| To meet your second two (arbitrary) requirements, have the
| signer encrypt the signed message with your public key before
| sending it to you.
| pastel8739 wrote:
| I think it's the original quote that is unclear:
|
| > a digital signature proves your possession of a private key
| without revealing that key.
|
| Signatures do not themselves do this; but they can be used to
| construct a protocol that does (e.g. the provee provides a
| random challenge that the prover must sign). But still this
| is not AFAIU a zero-knowledge proof as the signature is
| itself "knowledge".
| drdeca wrote:
| I think a definition of the security of a signature scheme
| is that a computationally limited attacker should not have
| a non-negligibly better than chance guess of the secret
| key.
|
| I think some of the "ZKP" techniques are supposed to only
| be "ZK" for a computationally limited observer? Though I
| may be mistaken, and maybe non-interactive ZKP schemes are
| only assuming that the prover has limited computational
| resources, not that the observer/attacker hoping to get
| information from them does?
| jstanley wrote:
| They're not my arbitrary requirements, see
| https://en.wikipedia.org/wiki/Zero-knowledge_proof
|
| Specifically:
|
| > In light of the fact that one should be able to generate a
| proof of some statement only when in possession of certain
| secret information connected to the statement, the verifier,
| even after having become convinced of the statement's truth
| by means of a zero-knowledge proof, should nonetheless remain
| unable to prove the statement to further third parties.
| pastel8739 wrote:
| I think even aside from that (which can be solved with
| challenge-response) digital signatures are typically not ZKPs
| because the signature itself constitutes information that must
| be transferred during the proof.
| jeremysalwen wrote:
| 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.
| andreareina wrote:
| My conclusion from watching a lot of Penn and Teller is that
| when you're invited to examine the deck it probably _is_ normal
| and often the trick will involve a force.
___________________________________________________________________
(page generated 2025-11-29 23:00 UTC)