Technical Report MSC-1998-01

TR#:MSC-1998-01
Class:MSC
Title: Cryptographic Methods for Implementing Anonymous Electronic Cash
Authors: Amichai Shulman
Supervisors: Eli Biham
PDFMSC-1998-01.pdf
Abstract: In the recent years, the concept of electronic cash (e-cash) is drawing a lot of attention. Anonymous electronic cash increases the privacy of the users by keeping the users' identity anonymous. Still, the bank should be able to reveal the true identity of users who pay more than once with the same coin (double spending).

Many studies have been done in the area of electronic cash, and in particular anonymous electronic cash. Studies are carried out both by individuals in the academy and by commercial organizations. The goal of these studies is to achieve electronic cash systems which can be implemented in practice on smartcards. The first cryptographic anonymous e-cash system was described by Chaum, Fiat and Naor as early as 1988. However, none of the cryptographic systems proposed since then can be implemented on commercial smartcards. The principal limitation of these methods is their extensive computational requirements and high demand for storage space.

This research is concerned with finding new methods for e-cash that can be implemented in practice. The focus of the work is on methods that allow for multiple denominations of coins and methods with divisible coins. The research describes three new methods as follows:

The first method extends a method proposed by Ferguson in 1993. The original method uses coins with a unique, fixed denomination. The identity of the owner of a coin is kept secret as long as the coin is used at most for one payment. If a coin is spent twice the bank can easily recover the identity of the user who owns it. Our extension incorporates the coin's value into its representation, and allows users to choose any favorite denomination. In addition, we propose a related protocol for simultaneous withdrawal of multiple coins, which reveals only the total amount of withdrawal to the bank and hides the individual denominations of the various coins.

The second method is a new method that uses digital bank notes. Each bank note has a fixed predefined denomination. The user can make any number of payments, of arbitrary amounts, using the same bank note as long as the total amount of the payments is less than the original value of the bank note. The suggested method is very efficient in terms of required computation time, storage space and communications. A number of bank notes can be stored at the same time in one smartcard. The time required for making a payment is about half a second. The method is based on computationally limited anonymity. This concept implies that the identity of users is not protected unconditionally even for honest users. Nevertheless, the cost of exposing the identity of a user is high enough to make it worthwhile only in the case of double spending.

The third and last method presents divisible coins. This is the first cryptographic system that supports full divisibility of coins. A user can divide a coin to any number of sub-coins whose denominations are not limited to a predefined set. The user can decide on the division at any given moment after the withdrawal of the coin, and in particular at the time of payment. Each sub-coins can be further divided at a later time. In addition to the unique feature of full divisibility, the system is very efficient in terms of the required storage space. In fact, the storage space required for holding a divisible coin (including its divisions) is similar to the storage required for a single non-divisible coin in other systems.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1998/MSC/MSC-1998-01), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 1998
To the main CS technical reports page

Computer science department, Technion
admin