Cryptology ePrint Archive: Report 2005/411

More Compact E-Cash with Efficient Coin Tracing

Victor K. Wei

Abstract: In 1982, Chaum \cite{Chaum82} pioneered the anonymous e-cash which finds many applications in e-commerce. In 1993, Brands \cite{Brands93apr,Brands93,Brands93tm} and Ferguson \cite Ferguson93c,Ferguson93} published on single-term offline anonymous e-cash which were the first practical e-cash. Their constructions used blind signatures and were inefficient to implement multi-spendable e-cash. In 1995, Camenisch, Hohenberger, and Lysyanskaya \cite{CaHoLy05} gave the first compact $2^\ell$-spendable e-cash, using zero-knowledge-proof techniques. They left an open problem of the simultaneous attainment of $O(1)$-unit wallet size and efficient coin tracing. The latter property is needed to revoke {\em bad} coins from over-spenders. In this paper, we solve \cite{CaHoLy05}'s open problem, and thus enable the first practical compact e-cash. We use a new technique whose security reduces to a new intractability Assumption: the {\em Decisional Harmonic-Relationed Diffie-Hellman (DHRDH) Assumption}.

Category / Keywords: cryptographic protocols / e-cash

Date: received 17 Nov 2005

Contact author: kwwei at ie cuhk edu hk

Available format(s): PDF | BibTeX Citation

Version: 20051121:075200 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]