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

David Pointcheval 1, 2 Olivier Sanders 3 Jacques Traoré 4
2 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
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≤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.
Type de document :
Communication dans un congrès
Serge Fehr. Public-Key Cryptography - PKC 2017 - 20th International Conference on Practice and Theory in Public-Key Cryptography, Mar 2017, Amsterdam, Netherlands. Springer, Lecture Notes in Computer Science, 10174 (Part I), pp.61-90, 〈10.1007/978-3-662-54365-8_4〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01471876
Contributeur : David Pointcheval <>
Soumis le : lundi 20 février 2017 - 12:53:38
Dernière modification le : mardi 17 avril 2018 - 11:26:46

Identifiants

Collections

Citation

David Pointcheval, Olivier Sanders, Jacques Traoré. Cut Down the Tree to Achieve Constant Complexity in Divisible E-Cash. Serge Fehr. Public-Key Cryptography - PKC 2017 - 20th International Conference on Practice and Theory in Public-Key Cryptography, Mar 2017, Amsterdam, Netherlands. Springer, Lecture Notes in Computer Science, 10174 (Part I), pp.61-90, 〈10.1007/978-3-662-54365-8_4〉. 〈hal-01471876〉

Partager

Métriques

Consultations de la notice

543