Cut Down the Tree to Achieve Constant Complexity in Divisible E-Cash

David Pointcheval; Olivier Sanders; Jacques Traoré

Paper 2015/972

Cut Down the Tree to Achieve Constant Complexity in Divisible E-Cash

David Pointcheval, Olivier Sanders, and Jacques Traoré

Abstract

Divisible e-cash, proposed in 1991 by Okamoto and Ohta, addresses a practical concern of electronic money, the problem of paying the exact amount. Users of such systems can indeed withdraw coins of a large value $N$ and then divide it into many pieces of any desired values $V \leq N$ . Such a primitive therefore allows to avoid the use of several denominations or change issues. Since its introduction, many constructions have been proposed but all of them make use of the same framework: they associate each coin with a binary tree, which implies, at least, a logarithmic complexity for the spendings. In this paper, we propose the first divisible e-cash system without such a tree structure, and so without its inherent downsides. Our construction is the first one to achieve constant-time spendings while offering a quite easy management of the coins. It compares favorably with the state-of-the-art, while being provably secure in the standard model.

Note: Anonymity now relies on a slightly weaker assumption.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: A minor revision of an IACR publication in PKC 2017
Keywords: Divisible E-Cash Anonymity Bilinear Groups
Contact author(s): oliviersanders @ live fr
History: 2016-12-22: last of 2 revisions; 2015-10-09: received; See all versions
Short URL: https://ia.cr/2015/972
License: CC BY

BibTeX

@misc{cryptoeprint:2015/972,
      author = {David Pointcheval and Olivier Sanders and Jacques Traoré},
      title = {Cut Down the Tree to Achieve Constant Complexity in Divisible E-Cash},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/972},
      year = {2015},
      url = {https://eprint.iacr.org/2015/972}
}