Abstract
We present an efficient off-line divisible e-cash scheme which is 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 truly anonymous, our result puts it a step further and we show that truly anonymous divisible e-cash can be practical.
This work is supported by ARC Linkage Project LP0667899 and ARC Discovery Grant DP0877123.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Ateniese, G., Camenisch, J., de Medeiros, B.: Untraceable rfid tags via insubvertible encryption. In: ACM Conference on Computer and Communications Security, pp. 92–101 (2005)
Au, M.H., Susilo, W., Mu, Y.: Practical anonymous divisible e-cash from bounded accumulators. Cryptology ePrint Archive, Report, 2007/459 (2007), http://eprint.iacr.org/
Au, M.H., Susilo, W., Mu, Y.: Practical compact e-cash. In: Pieprzyk, J., Ghodosi, H., Dawson, E. (eds.) ACISP 2007. LNCS, vol. 4586, pp. 431–445. Springer, Heidelberg (2007)
Au, M.H., Wu, Q., Susilo, W., Mu, Y.: Compact e-cash from bounded accumulator. In: Abe, M. (ed.) CT-RSA 2007. LNCS, vol. 4377, pp. 178–195. Springer, Heidelberg (2006)
Bari, N., Pfitzmann, B.: Collision-free accumulators and fail-stop signature schemes without trees. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 480–494. Springer, Heidelberg (1997)
Bellare, M., Rogaway, P.: Random oracles are practical: A paradigm for designing efficient protocols. In: ACM Conference on Computer and Communications Security, pp. 62–73 (1993)
Benaloh, J.C., de Mare, M.: One-way accumulators: A decentralized alternative to digital sinatures (extended abstract). In: EUROCRYPT, pp. 274–285 (1993)
Boneh, D., Boyen, X.: Short signatures without random oracles. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 56–73. Springer, Heidelberg (2004)
Camenisch, J., Hohenberger, S., Lysyanskaya, A.: Compact e-cash. In: Cramer, R.J.F. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 302–321. Springer, Heidelberg (2005)
Camenisch, J., Lysyanskaya, A.: A Signature Scheme with Efficient Protocols. In: Cimato, S., Galdi, C., Persiano, G. (eds.) SCN 2002. LNCS, vol. 2576, pp. 268–289. Springer, Heidelberg (2003)
Camenisch, J., Stadler, M.: Efficient group signature schemes for large groups (extended abstract). In: CRYPTO, pp. 410–424 (1997)
Canard, S., Gouget, A.: Divisible e-cash systems can be truly anonymous. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 482–497. Springer, Heidelberg (2007)
Canard, S., Traoré, J.: On fair e-cash systems based on group signature schemes. In: Safavi-Naini, R., Seberry, J. (eds.) ACISP 2003. LNCS, vol. 2727, pp. 237–248. Springer, Heidelberg (2003)
Chan, A.H., Frankel, Y., Tsiounis, Y.: Easy come - easy go divisible cash. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 561–575. Springer, Heidelberg (1998)
Chaum, D.: Blind Signatures for Untraceable Payments. In: McCurley, K.S., Ziegler, C.D. (eds.) Advances in Cryptology 1981 - 1997. LNCS, vol. 1440, pp. 199–203. Springer, Heidelberg (1999)
D’Amiano, S., Crescenzo, G.D.: Methodology for digital money based on general cryptographic tools. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 156–170. Springer, Heidelberg (1995)
Eng, T., Okamoto, T.: Single-term divisible electronic coins. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 306–319. Springer, Heidelberg (1995)
Fiat, A., Shamir, A.: How to prove yourself: Practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987)
Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof-systems (extended abstract). In: STOC, pp. 291–304 (1985)
Goldwasser, S., Micali, S., Rivest, R.L.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput. 17(2), 281–308 (1988)
Nakanishi, T., Sugiyama, Y.: Unlinkable divisible electronic cash. In: Okamoto, E., Pieprzyk, J.P., Seberry, J. (eds.) ISW 2000. LNCS, vol. 1975, pp. 121–134. Springer, Heidelberg (2000)
Nguyen, L.: Accumulators from Bilinear Pairings and Applications. In: Menezes, A. (ed.) CT-RSA 2005. LNCS, vol. 3376, pp. 275–292. Springer, Heidelberg (2005)
Okamoto, T.: An efficient divisible electronic cash scheme. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 438–451. Springer, Heidelberg (1995)
Okamoto, T., Ohta, K.: Universal electronic cash. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 324–337. Springer, Heidelberg (1992)
Pailles, J.C.: New protocols for electronic money. In: ASIACRYPT, pp. 263–274 (1992)
Schnorr, C.-P.: Efficient signature generation by smart cards. J. Cryptology 4(3), 161–174 (1991)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Au, M.H., Susilo, W., Mu, Y. (2008). Practical Anonymous Divisible E-Cash from Bounded Accumulators. In: Tsudik, G. (eds) Financial Cryptography and Data Security. FC 2008. Lecture Notes in Computer Science, vol 5143. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85230-8_26
Download citation
DOI: https://doi.org/10.1007/978-3-540-85230-8_26
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85229-2
Online ISBN: 978-3-540-85230-8
eBook Packages: Computer ScienceComputer Science (R0)