Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Interactive zero knowledge 3-colorability demonstration

web.mit.edu

Post reply on HN
Print view View original

11–20 of 25 posts

Re: Interactive zero knowledge 3-colorability demonstration

#11

Post by wakamoleguy »

bmc7505 wrote: post #9

One thing I do not understand and would like to learn more about is zero-knowledge proofs is that their soundness seems to rest on the data-generating mechanism. Suppose you had an adversary Alice who claims to possess a constructive proof that graph-isomorphism [1] is in P. Secretly, she has proven that graph-isomorphism is NP-complete, but only for a vanishingly small family of graphs, and almost all random graphs…

One difference seems to be in the size of the domain. In the interactive example, you know the possible edges to begin with, and selecting them is straightforward. The confidence is calculated based on that. For graph isomorphism, you would have little confidence that you can pull from the full set of graphs, and so you would have a hard time building confidence.

If there is a way around that, I'm genuinely curious as well.

Re: Interactive zero knowledge 3-colorability demonstration

#12

Post by gs17 »

jakear wrote: post #7
gs17 wrote: post #4

Earlier quoted context omitted.

The part not shown well here is that before your choice, you would receive a "commitment" for each vertex color in the graph for each iteration. The commitment allows the prover to provide a coloring that can't be changed after the round starts, but also where only the values for the chosen edge will have their commitment "opened". If each round gets you an edge with different colors for each vertex, you can be confi…

What form could such a commitment take over the wire?

There's a bunch of committment schemes: https://en.wikipedia.org/wiki/Commitment_scheme , but a simple (although I'm not sure it's ideal) one would be to hash a random value concatenated with the message, transmit the hash as your commitment to that message, and to reveal it send the random value and message so the verifier can confirm the hash comes out the same.

Re: Interactive zero knowledge 3-colorability demonstration

#14

Post by whatshisface »

gs17 wrote: post #12
jakear wrote: post #7

Earlier quoted context omitted.

What form could such a commitment take over the wire?

There's a bunch of committment schemes: https://en.wikipedia.org/wiki/Commitment_scheme , but a simple (although I'm not sure it's ideal) one would be to hash a random value concatenated with the message, transmit the hash as your commitment to that message, and to reveal it send the random value and message so the verifier can confirm the hash comes out the same.

But would your example commitment work in this case when the verifier never receives the "message" of the graph that's being committed to?

Re: Interactive zero knowledge 3-colorability demonstration

#15

Post by gs17 »

whatshisface wrote: post #14
gs17 wrote: post #12

Earlier quoted context omitted.

There's a bunch of committment schemes: https://en.wikipedia.org/wiki/Commitment_scheme , but a simple (although I'm not sure it's ideal) one would be to hash a random value concatenated with the message, transmit the hash as your commitment to that message, and to reveal it send the random value and message so the verifier can confirm the hash comes out the same.

But would your example commitment work in this case when the verifier never receives the "message" of the graph that's being committed to?

The "message" would have to be each vertex's color, separately, rather than the entire graph's coloring at once. Then when the verifier requests the edge for this round, the prover reveals those the commitments for the two vertices on that edge and only those two.

Since the prover doesn't know which edge will be selected and has to commit one color to each vertex, inspecting one random edge per round is enough. They either committed to a 3-coloring and any edge is valid, or they didn't and there's at least one edge we could pick to reject them. The rest of the graph doesn't need to be revealed for us to either gain confidence that they have a coloring or know for certain they do not.

Re: Interactive zero knowledge 3-colorability demonstration

#16

Post by neolefty »

gs17 wrote: post #15
whatshisface wrote: post #14

Earlier quoted context omitted.

But would your example commitment work in this case when the verifier never receives the "message" of the graph that's being committed to?

The "message" would have to be each vertex's color, separately, rather than the entire graph's coloring at once. Then when the verifier requests the edge for this round, the prover reveals those the commitments for the two vertices on that edge and only those two. Since the prover doesn't know which edge will be selected and has to commit one color to each vertex, inspecting one random edge per round is enough. They…

Interesting! Thanks especially for the link to the Wikipedia page.

So in the demo, the black (uncolored) shape _kind of_ represents the commitment. Although as you pointed out, it doesn't explain how it is verified! Instead of a black shape, it would be a shape made out of hash values that are meaningless until the random number for any one of them is revealed. And the protocol is to only reveal one of them each time?

Re: Interactive zero knowledge 3-colorability demonstration

#17

Post by gs17 »

neolefty wrote: post #16
gs17 wrote: post #15

Earlier quoted context omitted.

The "message" would have to be each vertex's color, separately, rather than the entire graph's coloring at once. Then when the verifier requests the edge for this round, the prover reveals those the commitments for the two vertices on that edge and only those two. Since the prover doesn't know which edge will be selected and has to commit one color to each vertex, inspecting one random edge per round is enough. They…

Interesting! Thanks especially for the link to the Wikipedia page. So in the demo, the black (uncolored) shape _kind of_ represents the commitment. Although as you pointed out, it doesn't explain how it is verified! Instead of a black shape, it would be a shape made out of hash values that are meaningless until the random number for any one of them is revealed. And the protocol is to only reveal one of them each time…

Exactly, the only difference is that two commitments would be revealed, since each vertex color is committed, if we let them commit to edges instead it would be much easier to lie!

Re: Interactive zero knowledge 3-colorability demonstration

#18

Post by justicz »

bmc7505 wrote: post #9

One thing I do not understand and would like to learn more about is zero-knowledge proofs is that their soundness seems to rest on the data-generating mechanism. Suppose you had an adversary Alice who claims to possess a constructive proof that graph-isomorphism [1] is in P. Secretly, she has proven that graph-isomorphism is NP-complete, but only for a vanishingly small family of graphs, and almost all random graphs…

That’s a great question. One idea would be for Alice to generate a machine-checkable proof of her claim (e.g. in Coq or something). Instead of playing the typical game where she distinguishes graphs, we just do a secure two-party computation to check the proof, where Alice’s public input is the claim, and her private input is the proof.

Re: Interactive zero knowledge 3-colorability demonstration

#19

Post by procedurecall »

bmc7505 wrote: post #9

One thing I do not understand and would like to learn more about is zero-knowledge proofs is that their soundness seems to rest on the data-generating mechanism. Suppose you had an adversary Alice who claims to possess a constructive proof that graph-isomorphism [1] is in P. Secretly, she has proven that graph-isomorphism is NP-complete, but only for a vanishingly small family of graphs, and almost all random graphs…

You may be interested in Mahaney's Theorem (https://en.m.wikipedia.org/wiki/Mahaney%27s_theorem), which 'answers' a special case of this: If by vanishingly small you mean polynomial size, and you also assume Alice has an algorithm that can distinguish the two subclasses of graph isomorphism, then P=NP if Alice has these facts. By 'distinguish', I specifically mean that Alice has a polynomial time algorithm that will tell you, for an input of graph isomorphism, is it part of a subclass of graph isomorphism which is NP-complete, and which has polynomial size.

Re: Interactive zero knowledge 3-colorability demonstration

#20

Post by xiphias2 »

wakamoleguy wrote: post #8

With the second graph, Turbo mode often gets up to 60% or 70% confidence before detecting an issue. That seems odd, since I'd expect most edges in a graph to be colorable and only a few to have issues, so I'd "expect" most graphs to look fine up to that level. Is this an issue with the confidence equation and prior, or is it just expected that nobody would stop until they hit 99%+ confidence? In other words, perhaps…

It's about 1-1/e (63%) as there's always 1 edge with problem, and always 1/E probability that it is revealed in on average E rounds. (1-1/E)^E -> 1/e
Post reply on HN