Compact Ecash and Applications

Anna Lysyanskaya, Brown

The main idea of electronic cash (ecash) 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. Therefore, ecash is an example of balancing anonymity with accountability: a user remains anonymous until she violates a particular condition (spends a coin more than once).

In this talk, I will give several examples of balancing anonymity with accountability along these lines. First, I will first present a scheme that allows a user to withdraw a wallet, such that the user can spend N coins anonymously, but will get identified should she spend N+1 times. (The complexity of each operation here only has a logarithmic dependence on N.) Then I will show that this can be extended to, for example, allow a user to spend at most M coins anonymously with a particular merchant, or, as another example, spend at most L coins anonymously in one day.

Based on joint papers with Jan Camenisch, Susan Hohenberger, Markulf Kohlweiss, and Mira Meyerovich.

24 Aug (Friday) at 1630 hrs

Gates 4B (opposite 490)