Concurrent Zero-Knowledge

July 28, 2008
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.

Advertisements

Endorsed E-Cash

July 28, 2008
Endorsed E-Cash

Endorsed E-Cash

E-Cash is supposed to be the digital equivalent of real cash.  The idea is that Alice can withdraw money from the bank and spend it anonymously.  Later, when the bank looks at its database of deposits and withdrawals, it shouldn’t be able to link any deposit with any withdrawal.

Of course there is a problem with this scenario.  Suppose Alice withdraws a digital dollar and then spends it twenty-gadzillion times.  Since Alice stores the digital dollar on her computer, nothing stops her from making those twenty-gadzillion copies.

The standard solution is to embed Alice’s identity into every e-dollar she withdraws.  If she spends the same e-dollar more than once, the bank can look at the two deposits and determine Alice’s identity.  For example, suppose we associate a straight line with each e-dollar.  The y-intercept is Alice’s identity.  The slope is chosen at random during withdrawal.  If Alice spends the e-dollar once, she reveals one point on the line.  That’s not enough to learn anything about Alice’s identity.  (Try it at home: point your finger on any random spot on the monitor and count the number of straight lines between your finger and the left hand side of the screen).  If Alice spends the e-dollar a second time, the bank can “connect the dots” and follow the line to the y-intercept.

The standard objection is that even if Alice is identified after the fact, Alice fly to the Bahamas long before the bank catches up.  The potential damage is just not worth the on-line privacy goodness.

These practical obligations did not deter me from writing my Ph.D. thesis on e-cash.  One of my favorite results was showing how to do secure fair exchange of e-cash.  When Alice sends Bob her e-dollars (ok, now that we’re getting technical, I should call them by their official latin name, e-coin, which is easy to remember, because it is like e-coli, only it corrupts you soul and not your stomach), she wants to make sure she gets some sort of receipt back in return.  Bob doesn’t want to send a receipt until he gets paid.  The solution is to do alot of math in algebraic groups of prime order.

Things get even more interesting when Alice needs to pay more than one e-coin.  Now we do a cool trick and hide all the e-coins in a polynomial of degree N.  Then Alice gives Bob N points on the polynomial.  Just as in the straight line example, Bob doesn’t learn anything about the e-coins because he only has N points.  He needs N+1 points to interpolate (english: compute) the polynomial.  Then Alice and Bob run the Asokan, Shoup and Waidner fair exchange algorithm for the magic N+1th point.  Alice gets a receipt.  Bob gets N+1 points.  He interpolates, and voila! out comes the pot of e-cash.

You can read more about Endorsed E-Cash in my IEEE Security and Privacy 2007 publication.