Fair E-cash : Be Compact, Spend Faster

S. Canard, C. Delerablée, A. Gouget, E. Hufschmitt, F. Laguillaumie, H.
Sibert, J. Traoré & D. Vergnaud

We present the first fair e-cash system with a compact wallet that enables
users to spend efficiently k coins while only sending to the merchant
O(lambda log (k))) bits, where lambda is a security parameter. The best
previously known schemes require to transmit data of size at least linear in
the number of spent coins. This result is achieved thanks to a new way to use
the Batch RSA technique and a tree-based representation of the wallet.
Moreover, we give a variant of our scheme with a less compact wallet but
where the computational complexity of the spend operation does not depend on
the number of spent coins, instead of being linear at best in existing
systems.