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.

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_{1},X_{2},...,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_{1},...,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.

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.