Comments

Terry Cloth • December 15, 2014 9:09 PM

Seconded. I’d always taken ZKP on trust, not even being able to handwave my way through it. Now I can manage that much. 🙂

Winter • December 16, 2014 2:36 AM

I am eagerly awaiting the second installment.

What I did not really understand is whether a challenge to hash, say, a password with a random number is an example of a ZKP? The text seems to imply it, but I could interpret it otherwise.

hugh • December 16, 2014 8:47 AM

I’ve only read the google hats bit so far but there appears to be such a glaring hole that I must be missing something. Help me out please folks.
What if for each iteration google just makes up an answer at random that satisfies the test? e.g. for any two hats they choose two different random colours. The fact they are different colours satisfies the test conditions, and because they are choosing a different colour scheme each time I cannot expect the same node to be the same colour each time.

I’m guessing it a problem with my understanding or the analogy not the underlying theory. Any ideas please?

MrC • December 16, 2014 9:07 AM

Excellent article. Even my feeble mind could follow it. I, too, am looking forward to the follow-up.

@ Hugh:

I’m not sure what you’re asking. Are you asking (a) “why not use as many different colors as there are nodes?” or (b) “why not wait to make up the answer after hearing which two nodes you need to reveal?”

The answer to (a) is that you are restricted to 3 colors total, and those colors are known to the verifier.

The answer to (b) is that you’re required to commit to the entire answer before the two nodes are picked. However, the consequences of what would happen if you somehow could break that constraint are what make the proof work. I suggest you keep reading.

Matt • December 16, 2014 10:50 AM

@Hugh:

You would find a scheme that forces Google to commit to a total coloring of the graph before you challenge it. As an example Google would send you the complete colored graph, but each node color is encrypted with a different key-pair.
When you choose your two hats, Google sends you the private keys for those nodes and you decrypt just those 2 colors.

Ben K • December 16, 2014 8:43 PM

@Winter

“What I did not really understand is whether a challenge to hash, say, a password with a random number is an example of a ZKP? The text seems to imply it, but I could interpret it otherwise.”

It is not, because the challenger would need to know the password in order to check that the hash is correct. It is possible to prove knowledge of a password in a zero-knowledge way; for example, you can use a modification of the Schnorr protocol:

Common Input: g^(secret); the prover will prove knowledge of “secret”

Step 1: Verifier chooses random group element C and commits to it

Step 2: Prover chooses random group element R and sends g^R to Verifier

Step 3: Verifier opens the commitment to C

Step 4: Prover sends g^(R + C * secret)

The verifier can then check that (g^(secret))^C * g^R = g^(R + C*secret). Step 1 may seem extraneous, but it is actually necessary to prove that this protocol is zero-knowledge.

Interesting fact: this protocol is closely related to the Schnorr signature system, which is similar to DSA.

Zith • December 18, 2014 2:47 PM

Could someone help me with one part? I’m not following the logic that being unable to distinguish a faked-zero-information result from an honest-complete-information result necessarily creates a symmetric zero-knowledgeness relationship. It seems to me that if the scheme is flawed, it might leak an arbitrary amount of information without regard to your ability to verify that the information is valid.

tin hat • December 19, 2014 7:16 AM

Thanks Bruce,

i recently (dec-19-2014) learned that my isp (germany dtag) doesn’t resolve “blog.cryptographyengineering.com” namely “217.237.151.51” and “217.237.149.205” but 8.8.8.8 does.

Ben K • December 21, 2014 8:57 AM

Zith —

Not being able to distinguish the real protocol from the simulation is not the whole story; what actually matters is that the simulator can be constructed. It matters if the verifier can distinguish the simulation from the real protocol only because the simulator has to interact with the verifier; the verifier might behave differently if it can distinguish a simulator from the real thing. So if the simulation is indistinguishable from the real protocol, the verifier will give answers to the simulator that look the same as the answer it would give in the real protocol.

If you can construct such a simulator, it means that you can create a transcript of the simulated protocol that looks just like the real protocol, but without having to actually have any interaction. What that means is that the real protocol does not give the verifier anything more than the verifier could get on its own: the verifier can always run the simulator to get a transcript that looks real. That means that the transcript has no value at all; it cannot even be used as evidence that the prover and verifier actually ran the protocol.

There is a lot of subtlety here, so don’t worry if it does not immediately “click.” Just spend some time thinking about it. Also take a look at “witness hiding” and “witness indistinguishable” proofs, and think about what makes them different from ZKP.

— Ben

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.