The main idea of electronic cash is that, even though the same party (a Bank) is responsible for giving out electronic coins, and for later accepting them for deposit, the withdrawal and the spending protocols are designed in such a way that it is impossible to identify when a particular coin was spent. I.e., the withdrawal protocol does not reveal any information to the Bank that would later enable it to trace how a coin was spent. Since a coin is represented by data, and it is easy to duplicate data, an electronic cash scheme requires a mechanism that prevents a user from spending the same coin twice (double-spending), for example by identifying double-spenders and tracing all transactions that they have carried out.
In this talk, I will present a scheme that allows a user to withdraw a wallet with W coins, such that the space required to store these coins, and the complexity of the withdrawal protocol, are proportional to logW, rather than to W. We achieve this without compromising the anonymity and unlinkability properties usually required of electronic cash schemes. We give a scheme that allows us to efficiently trace all coins that were spent by a double-spender.
The security of our construction relies on a mix of cryptographic assumptions about groups with bilinear maps, and is in the random oracle model.
This is joint work with Jan Camenisch (IBM Zurich) and Susan Hohenberger (MIT), to appear in Eurocrypt 2005.
Gates 4B (opposite 490) Tuesday 03/29/05 1630 hrs