## Concurrent Zero-Knowledge

Concurrent Zero-Knowledge

Zero-Knowledge is one of the coolest and non-intuitive ideas in modern cryptography.  The idea is that Alice wants to prove that something is true without explaining why.  (Just like a woman, right?).  For example, she knows how to 3-color a particular graph.  She can paint each vertex on the graph red, green, or blue in such a way that no two adjacent vertices are the same color.  Now she wants to prove to Bob that it is possible to do it.  (For example, Bob is being lazy and doesn’t want to help out around the house by spending exponential time coloring vertices.  It’s a very common situation).  So Alice and Bob engage in a protocol in which Alice proves that yes, it is  possible to 3-color the graph.  BUT….Bob does not learn how Alice did it.

Ok, that sounds pretty pointless.  Most modern households don’t have graphs lying around just waiting to be 3-colored.  (Plus there is a very efficient 4-coloring algorithm for planar graphs, so if you’re willing to invest in a little more paint you can save yourself a lot of clock cycles).

But what if Alice wants to prove she knows her credit card number without actually sending it to FlyByNight.com?  Now Alice can safely purchase shoes on-line without worrying about an unscrupulous merchant stealing her credit card number.

Zero-Knowledge has been around since 1986 (sorry no link, this result is really old).

Oded Goldreich, Silvio Micali, Avi Wigderson: Proofs that Yield Nothing But their Validity and a Methodology of Cryptographic Protocol Design (Extended Abstract) FOCS 1986: 174-187.

The tricky thing about zero-knowledge is actually proving that a protocol is zero-knowledge.  Things get even worse with concurrent zero-knowledge, when Alice might have to prove things to several different people at the same time.  An unscrupulous adversary might take advantage of Alice and use the results of one protocol query to alter a second query.  Here the proofs get really convoluted as the cryptographer tries to rewind multiple simulators.  As they say, the pudding is in the proof.