UTCS Colloquium: ACT Special Seminar

Spea

ker Name/Affiliation: Anna Lysyanskaya/Brown University

Date/Time:
Friday March 30 2007 11:00 a.m.

Location: ACES 3.408

Ho

st: Adam Klivans

Talk Title: Compact Ecash and Applications

Talk Abstract:
The main idea of electronic cash is that even though th

e
same party (a Bank) is responsible for giving out electronic coins <

br>and for later accepting them for deposit the withdrawal and the
spe

nding protocols are designed in such a way that it is impossible
to ide

ntify when a particular coin was spent. I.e. the withdrawal
protocol d

oes not reveal any information to the Bank that would
later enable it t

o 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 mech

anism that prevents
a user from spending the same coin twice (double-sp

ending)
for example by identifying double-spenders and tracing all
transactions that they have carried out.

In this talk I will first
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 <

br>properties usually required of electronic cash schemes. We
give a sc

heme 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 c

ryptographic assumptions about groups with
bilinear maps and is in the
random oracle model.

I will then show how to use the same methodolo

gy to achieve
balance between accountability and privacy in other appli

cations.
In particular we consider a setting where the amount of anon

ymous
transactions with a particular merchant may be limited (e.g. so a

s
to prevent money laundering). Finally I will show that this methodo

logy
solves the problem of uncloneable group identification.

Bas

ed on joint papers with Jan Camenisch Susan Hohenberger
Markulf Kohlw

eiss and Mira Meyerovich.