Paper 2007/459

Practical Anonymous Divisible E-Cash From Bounded Accumulators

Man Ho Au, Willy Susilo, and Yi Mu

Abstract

We present an efficient off-line divisible e-cash scheme which is \emph{truly anonymous} without a trusted third party. This is the second scheme in the literature which achieves full unlinkability and anonymity, after the seminal work proposed by Canard and Gouget. The main trick of our scheme is the use of a bounded accumulator in combination with the classical binary tree approach. The aims of this paper are twofold. Firstly, we analyze Canard and Gouget's seminal work on the efficient off-line divisible e-cash. We point out some subtleties on the parameters generation of their scheme. Moreover, spending a coin of small value requires computation of several hundreds of multi-based exponentiations, which is very costly. In short, although this seminal work provides a new approach of achieving a truly anonymous divisible e-cash, unfortunately it is rather impractical. Secondly, we present our scheme that uses a novel approach of incorporating a bounded accumulator. In terms of time and space complexities, our scheme is $50$ to $100$ times more efficient than Canard and Gouget's work in the spend protocol at the cost of an $10$ to $500$ (the large range is due to whether pre-processing is taken into account and the probabilistic nature of our withdrawal protocol) times less efficient withdrawal protocol. We believe this trade-off between the withdrawal protocol and the spend protocol is reasonable as the former protocol is to be executed much less frequent than the latter. Nonetheless, while their scheme provides an affirmative answer to whether divisible e-cash can be \emph{truly anonymous}, our result puts it a step further and we show that truly anonymous divisible e-cash can be \emph{practical}.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. This is the full version of the paper that is going to appear in FC 2008
Keywords
e-cashelectronic commerce and paymentbounded accumulators
Contact author(s)
mhaa456 @ uow edu au
History
2007-12-10: received
Short URL
https://ia.cr/2007/459
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/459,
      author = {Man Ho Au and Willy Susilo and Yi Mu},
      title = {Practical Anonymous Divisible E-Cash From Bounded Accumulators},
      howpublished = {Cryptology ePrint Archive, Paper 2007/459},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/459}},
      url = {https://eprint.iacr.org/2007/459}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.