zero knowledge

Let's say I need to prove to you that I know some piece of information (example: the password to a computer account, the location of your kidnapped parents) - but I don't want to reveal the information to you. A zero-knowledge proof of knowledge will allow me to do that. The phrase "zero-knowledge" arises from the fact that I can prove I know some information while providing you with no knowledge about the actual content of the information in question.

Zero-knowledge proofs are typically statistical in nature: you ask me a series of questions whose answers depend my knowing the information in question; if I can answer them all correctly, the chance that I don't know the information in question becomes negligible. Conversely, if I don't know the information, my chance of answering all the questions correctly is negligible.

Zero-knowledge proofs are covered in some detail in Bruce Schneier's excellent book, Applied Cryptography.

I expect that Zero Knowledge Systems got their name from this idea.

A zero knowledge protocol is a process by which several parties can compute a function, without any party learning more than it should. Surprisingly, such true zero knowledge protocols are known (in the sense that we can prove this property of them). Among their many uses (mostly in cryptography, but sometimes also in distributed computing) are the secret sharing protocols, which generalise the "Captain and First Mate must each insert key to launch NUCLEAR MISSILES" scene from submarine movies to information.

The scenario

Several parties are distrustful of each other. Each party i has some information X_i. Some details of X_i may or may not be known to other parties. Party i has no wish to divulge any further information about X_i to any of the other parties.

Alice and Bob each have 2 numbers. Alice knows that Bob's numbers were drawn uniformly and independently from a geometric distribution with mean 1 and rate 0.5. Bob knows that Alice's first number is smaller than her second number, and that both follow the same geometric distribution.

The parties wish to compute some (known) function Y=f(X₁,X₂,...,X_n). Being distrustful, each party i wants to give the least possible information about X_i to the other parties. Probabilists might be pleased to have confirmed their guess that "information" here is in the usual the entropic sense.

Some information

How much is "the least possible" amount of information? Well, let's introduce some numbers: H(A|B) is "the amount of information gained by knowing A, if one already knows B". If you don't know how to define H(A|B), don't worry. The H(A|B) formalism follows all intuitive rules of how information "should behave", so any logical deduction you feel you can make for it is probably true. Specifically, if H(A|B)=0, then if you know B and I tell you A, you learn nothing new: A is a function of B (almost always).

Even without a zero knowledge protocol, if we just went around and told every party i the value Y=f(X₁,...,X_n), then they'd gain H(Y|X_i) information. A protocol is zero knowledge if, after participating and computing Y, party i gains only H(Y|X_i) information. Thus, participating in a zero knowledge protocol for computing Y gives you, as party i, no more information that you'd anyway have if you were told Y. In particular, you know nothing about my value X_j more than what you should know: H(X_j|X_i,Y). If I'm willing to have the value of Y revealed to the others (and learn it for myself), then I should be willing to participate in a zero knowledge proof for its computation.

Alice and Bob want to compute Y, a random variable which is the sum of one of Alice's two numbers (each chosen with equal probability, and known to Alice) and one of Bob's two numbers (the same, for Bob). As soon as Alice knows Y, she knows one of Bob's two numbers: it's Y, minus the number she chose. Since Bob's two numbers are independently chosen, she learns nothing of the other number. As soon as Bob knows Y, he knows one of Alice's two numbers: it's Y, minus the number he chose. And Bob knows that the two numbers aren't equal, so he knows one value which Alice's other number cannot have.

Security

Zero knowledge protocols are not necessarily secure: security depends on many factors, not just not revealing any information. For instance, if a party cheats during the protocol (doesn't follow the rule), they might learn something. Additional steps must be taken -- beyond guaranteeing a zero knowledge protocol -- to ensure "security". In particular, a precise definition of just what properties are desired is a good idea.

To compute their function Y, Alice and Bob could use the following zero knowledge protocol. Alice chooses one of her numbers, and tells it to Bob. Bob chooses one of his numbers, adds it to the number he got from Alice, and tells the sum to Alice. Each now knows the sum Y. Bob knows one of Alice's numbers -- but he'd anyway know it, as soon as he knows Y. So Bob learns nothing beyond what he'd know from Y. Likewise, Alice knows Y, and can immediately derive one of Bob's numbers. This too is permissible.

The protocol does nothing to prevent or even detect cheating. Alice could lie. By claiming her number is 17, Bob would tell her one of his numbers plus 17. Alice could then subtract 17 and get Bob's number. She could even use this information to compute Y correctly. Meanwhile, poor Bob has learned nothing: he doesn't know either of Alice's numbers, he doesn't even know Y.

Likewise, Bob could also cheat.

The zero knowledge guarantee doesn't necessarily apply if the protocol is not followed. But it does guarantee that if all parties follow protocol, none learn more than they'd anyway know.

See an example of a more interesting zero knowledge protocol: zero knowledge computation of the average salary.