See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/225973349

An Online, Transferable E-Cash Payment System

Conference Paper · January 2000

DOI: 10.1007/3-540-44495-5_9

CITATIONS READS

20 10,565

2 authors:

Sai Anand C. E. Veni Madhavan

ETH Zurich Indian Institute of Science
15 PUBLICATIONS   94 CITATIONS    84 PUBLICATIONS   992 CITATIONS   

SEE PROFILE SEE PROFILE

Some of the authors of this publication are also working on these related projects:

Analysis and Design of Image Encryption Algorithms View project

All content following this page was uploaded by Sai Anand on 19 June 2015.

The user has requested enhancement of the downloaded file.

 An Online, Transferable E-Cash Payment
System

R. Sai Anand
and C.E. Veni Madhavan

Department of Computer Science & Automation

Indian Institute of Science
Bangalore, India
{anand,cevm}@csa.iisc.ernet.in

Abstract. Most electronic cash (e-cash) based payment systems that

have been proposed do not possess the property of transferability. Trans-
ferability in an e-cash based system means that when a payee receives an
electronic coin in a transaction he may spend it without depositing the
coin first and getting a new coin issued from a bank. Usually electronic
coins that are transferred in a transaction have a lifetime of the trans-
action itself. In this paper, we propose a payment system where coins
can be transferred over multiple hands, spread over various transactions,
similar to physical cash. Detection or prevention of double spending of
coins is a critical issue in online e-cash payment systems. In our system
the verification is distributed across multiple entities as opposed to the
case of a coin-issuing entity or a central bank alone being responsible
for the verification. A resolution mechanism for handling disputes is also
presented. The proposed system provides guarantees of anonymity, fair-
ness and transferability.

Key words: E-cash, Transferability, Fairness, Anonymity, Double Spend-

ing.

A Introduction
With the exponential increase in the number of users on the Internet and the
market place shifting to the Internet, the role of an electronic payment system is
crucial. Anonymity, transferability, fungibility (breaking large denominations to
smaller ones) are some of the properties of paper cash, which an electronic pay-
ment system should possess. From security considerations, cryptographic primi-
tives are used in electronic payment systems. If a payment system is to succeed
on the Internet then the computational efforts in using these primitives need to
be optimized.
In this work, we consider electronic payment systems in which the payment
instrument is e-cash. Such systems are classified into two types, viz, online and
offline. Online e-payment systems are those in which the transfer of electronic
money between the payer and payee takes place in the presence of a third party,
usually a bank, that guarantees the authenticity of the coins being transferred. In


Presently at IBM India Research Lab, New Delhi, India

B. Roy and E. Okamoto (Eds.): INDOCRYPT 2000, LNCS 1977, pp. 93–103, 2000.


c Springer-Verlag Berlin Heidelberg 2000
94 R. Sai Anand and C.E. Veni Madhavan

contrast, in offline systems the transaction occurs between the two parties, payer
and payee, alone. The money transferred is verified when the payee deposits the
coins with a bank. Transferability of coins is a missing feature in most of the
systems that have been proposed so far, whether online or offline. The lifetime
of a coin is the lifetime of the transaction it is involved in, in such payment
schemes. This is in contrast to paper cash where the money retains its value
over several transactions and merely changes hand. An obvious advantage of
transferable cash is that a coin-issuing authority need not issue new coins for
every transaction that takes place.
A disadvantage, that has often been pointed out, of online systems is the
unfavourable load that would be placed on the central bank or coin-issuing au-
thority that would check the authenticity of the coin. This is certainly a bot-
tleneck since each coin in a transaction needs to be verified by a central server.
In the proposed scheme, we do away with a central verifying server and balance
the load across several entities. We also require a dispute resolving mechanism in
place for the electronic payment system. Given the fact that the payer and payee
do not even know each others’ real identities as they transact over the Internet,
the payment system should be able to give guarantees to both the parties in
the transaction. We outline such a dispute resolution protocol as a part of our
proposed payment system.
We briefly review some of the existing e-cash based payment systems. For
brevity, we choose the principal systems [3,6]. Certain other related and inter-
esting systems are [2,5,7,8,10,11].
David Chaum’s Ecash[6] is a fully anonymous, secure online electronic cash
system. It implements anonymity using blind signature techniques. The Ecash
system consists of three main entities:
– Banks who issue coins, validate existing coins and exchange real money for
Ecash.
– Buyers who have accounts with a bank, from which they can withdraw and
deposit Ecash coins.
– Merchants who can accept Ecash coins in payment for information, or hard
goods. Merchants can also run a pay-out service where they can pay a client
Ecash coins.
To withdraw a coin, the user generates a coin(message), m, consisting of a ran-
dom serial number, r, multiplied by a blinding factor, b, and the denomination.
This message, m, is signed by the user using his private key and sent to the
bank after encrypting the message using the bank’s public key. The bank signs
the blinded coin and debits the user’s account. The user unblinds the coin by
dividing by an appropriate blinding factor. Thus, the bank cannot link the Ecash
to the user.
While spending, the coins are securely transferred to the merchant. The mer-
chant verifies the coins by sending them to the bank. After ascertaining that the
coins are not double spent, the bank credits the merchant’s account and the coin
is destroyed. If the coin is double spent the bank sends an appropriate message
to abort the transaction.
 An Online, Transferable E-Cash Payment System 95

The advantage of Ecash is that it is fully anonymous and secure as it uses

public key cryptography. The downside is that the database of spent coins gets
bigger and new coins have to be issued for every transaction.
Stefan Brands proposed an offline e-cash payment system[3]. In this scheme,
three participants are involved : the computer at the bank, computer of an
Internet service provider and the machine of the user. The user’s machine is
interfaced with a tamper resistant device. The tamper resistant device increases
the counter at withdrawal time by the amount that is withdrawn and decreases
the counter when a payment is made. To make a payment from the user to the
Internet service provider and for the latter to verify that the payment is genuine,
a secret key is installed in the device. When a specified amount is transferred
this key is used to sign the amount. The service provider can now use the bank’s
public key to verify the authenticity of the electronic money so transferred. The
user does not know the secret key and hence cannot produce the signature.
After the digital signature is verified, the service provider accepts and provides
the requested service to the user.
The advantage of this system is that transactions do not require the presence
of a third party for verification. Thus offline operation provides lesser commu-
nication overheads. However, if the device is broken by anybody, a change of
device for every user of the system will be necessary.
Our system, combines the feature of anonymity provided by E-cash with the
feature of transferability. This obviates the withdrawal and deposit protocols for
each transaction, as in the case of [6]. For handling disputes during a transac-
tion, we propose a resolution protocol. In an online system, a single entity is
responsible for verification of coins. In the system that we propose, this load is
balanced across several verifying authorities.
This paper is organized as follows. In Sect. 2 we describe the e-payment setup
and describe the basic coin exchange, coin-withdrawal, coin deposit and dispute
resolution protocols. In Sect. 3 we describe the features - anonymity, fairness,
transferability - of our proposed payment system and how it achieves these. In
Sect. 4 we discuss some optimizations and extensions to the proposed scheme.

B The e-Payment System

In this section, we present our online payment system. Apart from ensuring
security and anonymity, the system will also incorporate the feature of transfer-
ability.

B.1 Setup and Notations

There are three parties involved in the basic coin exchange mechanism: the
Payer, designated as the Customer (C), the Payee, called a Merchant (M) and a
Verifying Authority (VA). In a transaction the coins are transferred from C to
M and the coins are verified by the VA. The VA’s job is two-fold: First, he has
to verify that the coin has not been spent previously and next, he needs to affix
96 R. Sai Anand and C.E. Veni Madhavan

his signature along with requisite information on the coin to allow the merchant
M to spend the coin later.
Before describing the protocol, we set up notations for the rest of the paper.
A signature on a message, MESG, by an entity X will be denoted as SX (MESG).
H(.) denotes a strong collision resistant one-way hash function. A symmetric key
between two entities X and Y will be denoted by KXY .
In our system the coin, COIN, is a bit string consisting of three parts. The
format of the coin is shown in Fig. 1 below.

{ SB (SNO, DENM, EXPD, TS ), SV A0 (VA1 , TS0 , H(SNO, TS)), VA0 }

Fig. 1. Coin Format

The first part has the fields, serial number (SNO), denomination of the coin
(DENM), expiry date of the coin (EXPD) and the timestamp of issue (TS).
This part is signed by the bank using its private key. The second part consists
of the name of the next verifying authority (VA1 ), a timestamp (TS0 ) at which
verification is done and the hash of serial number (SNO) and timestamp of issue
(TS) which are fields of the first part. The second part is then signed by the
present verifying authority (VA0 ). At issue stage, the present verifying authority
is the bank B itself. Also, the timestamp (TS0 ) at issue stage is the timestamp
of issue, TS. The third part of the coin is the name of the present verifying
authority (VA0 ). The first part of the coin remains unchanged throughout the
lifetime of the coin, i. e. till its expiry date.

B.2 Coin Exchange Protocol

The basic coin exchange protocol is explained below. Figure 2 shows the mes-
sages exchanged between C, M and VAi , the current verifying authority of the
coin. We now detail the steps.

Step 1: The customer C requests for goods from merchant M.

Step 2: M sends a signed message containing the transaction number (TID),

the description (DESC) of the goods, price (PRICE) and a time stamp (TS).

Step 3: C sends an encrypted message, signed using the public key of VAi
at which the coins are to be verified. This message consists of COIN and a hash
of the TID, DESC, PRICE and TS. Along with the encrypted message, the name
of VAi is also sent unencrypted so that M knows where he needs to send the
coin for verification.

Step 4: M sends to VAi two items. (i) The encrypted message received from
C in Step 3 and (ii) A composite message consisting of the name of the next
 An Online, Transferable E-Cash Payment System 97

verifying authority, VAi+1 , the above hash of the TID, DESC, PRICE and TS
and a symmetric key KMV . VAi+1 is the name of the next verifying authority,
to which M would like to send the coin for verification, when M spends it. KMV
is generated by M for one session of coin exchange protocol. This is used for
sending the signed coin back to M. This composite message is encrypted with
the public key of VAi .

Step 5: VAi decrypts the encrypted message and verifies that the coins have
not been spent previously after consulting his database and signs the coin.

Step 1:
Request(GOODS)
C M

Step 2: S (TID, DESC, PRICE, TS)

M
C M

Step 3: E (COIN, PRICE, H(TID, DESC, PRICE, TS)) , VA

VA i
i
C M

Step 4: E (COIN, PRICE, H(TID, DESC, PRICE, TS))

VA
i
VA M
i E (VA , PRICE, H(TID, DESC, PRICE, TS), K )
VA i+1 MV
Step 5: i
Verifies COIN sends OK / REJECT
VA M
i Sends signed COIN on OK encrypted with K
MV
Step 6:
Receipt for GOODS or REJECT
C M

Fig. 2. Basic Coin Exchange Protocol

The verification of the COIN is done as follows: Firstly, VAi verifies from
the second part that he is indeed the current valid verifying authority. Next,
VAi checks if the SNO appearing on the COIN is listed in his database. If not,
then the COIN is authentic and proceeds to sign the COIN. If the COIN is
listed in his database, he checks the timestamp appearing on the second part
of the COIN. If this timestamp is greater than the time stamp in the database
corresponding to the SNO of the COIN, then the COIN is authentic. If both of
the above conditions are violated then the COIN is treated as double spent and
a REJECT signal is conveyed to M. The entries that need to be made in the
verifying authority’s database when a COIN is found to be authentic are: (a)
98 R. Sai Anand and C.E. Veni Madhavan

The SNO, if it is not already in the database and (b) the timestamp (TS) of
previous verification which appears in the second part.
If the COIN is verified as being authentic, the verifying authority, VAi , needs
to sign it. This signing is done by replacing the second part of the COIN. The
second part will now contain the new timestamp (TSi ) at which the COIN is
being verified, the next verifying authority’s name (VAi+1 ) and the hash value
that existed in the replaced part. Of course, he may also verify that the hash
value is correct by doing the hash computation. The third part of the COIN is
replaced by the name of the present verifying authority, VAi . Figure 3 shows the
coin being signed by VAi .

Coin being Verified by VAi :

{SB (SNO, DENM, EXPD, TS ), SV Ai−1 (VAi , T Si−1 , H(SNO, TS)), VAi−1 }

Coin after Signing by VAi :

{SB (SNO, DENM, EXPD, TS ), SV Ai (VAi+1 , T Si , H(SNO, TS)), VAi }

Fig. 3. Coin verification/signing at VAi

After verification and signing, VAi sends an OK signal and the signed COIN
back to M encrypting it with the key KMV sent by the merchant. If the coin is
not authentic a REJECT signal is sent to M.

Step 6: M on receipt of an OK signal sends a signed receipt for the goods

to C. Similarly, on receipt of a REJECT signal M informs C accordingly.
Thus, if the COIN is not double spent, then it can be used by the current
owner M for his next transaction.

B.3 Withdrawal/Deposit Protocols

These protocols are executed infrequently since the payment mechanism guar-
antees transferability of coins. This implies that the coin issuing authority need
not create new coins for every transaction as in e-payment mechanisms which do
not possess this transferability property. The deposit and withdrawal protocol
are now described below (Figs. 4 & 5).

Coin Withdrawal

Step 1: The user C sends a request for coins, indicating the amount, the change
required and his account number with the bank/coin issuing authority B.
 An Online, Transferable E-Cash Payment System 99

Step 2: B verifies the outstanding balance in the account and if the requested
amount is available in the account, issues the coins to the customer. The bank
is provided with a public key of C when the account is opened which is used to
encrypt the coins while sending them to C. It is possible to include the blind
signature mechanism to provide for anonymity of C as in [1,4,9].

Step 1:
E (AMT, SPEC, ACCTNO, VA )
B 1
C B

Step 2: E (COINS)
C
C B

Fig. 4. Coin Withdrawal Protocol

Coin Deposit

Step 1: The customer C, who wants to deposit the coins, packs the coins and
encrypts them using bank B’s public key. He provides the account number to
which the deposit is to be made.

Step 2: The bank B verifies the authenticity of the coins with the appropri-
ate verifying authority VAk . On confirmation from VAk , the bank credits the
amount to the account specified by C.

Step 1:
E (COINS, ACCTNO) , VA
B k
C B

Step 2:
Verify COINS
VA B
k

Step 3:

If OK from verifying authority , B credits account ACCTNO with appropriate amount

Fig. 5. Coin Deposit Protocol

100 R. Sai Anand and C.E. Veni Madhavan

B.4 Resolution Protocol

The e-payment mechanism proposed provides guarantees of fairness to both the
payer and payee. Thus, if coins are transferred from one entity to another in
a transaction and a dispute arises, neither party loses any money or goods. In
this subsection we detail the resolve protocol that has to be executed in case of
disputes. This protocol also handles aborted transactions due to system failures.
The payee in our system is guaranteed an authentic payment since the ver-
ifying authority authenticates the coins. When the payee receives an OK signal
from some VAi it also receives the properly time-stamped coins which he may use
later for future transactions. On a REJECT signal from VAi , the same may be
used by the payee to prove that the transaction was not completed and therefore,
refuse transfer of goods.
The second part of the guarantee is what happens if a payee refuses to transfer
goods even though valid coins have been handed over by the verifying authority.
In Step 2 of the basic coin exchange protocol, the merchant M returns a signed
message containing the description of goods (DESC), transaction ID (TID), the
price (PRICE) and the time stamp (TS) at which the transaction occurs. The
merchant cannot deny sending the message since it carries his signature. If the
customer C can prove that the coins he had sent to M were valid coins and were
authenticated by the verifying authority, then he can lay claim to the goods ne-
gotiated during the transaction. To this end, he executes the following resolution
protocol:

Resolution Protocol

Step 1: C sends a resolve request with the signed message obtained from mer-
chant M and a hash of the coins he had used in the transaction to the verifying
authority VAi at which the coin was sent.

Step 2: VAi on receipt of the request checks the signature of M and if found
valid checks if the coins spent were authenticated by it. If the claim of C is
found correct, VAi directs M to transfer the goods. If M does not accept then
the coins transferred to it are invalidated by sending an appropriate message
to VAi+1 . Also, the coins spent by C are restored to it so that C does not lose
money in the aborted transaction.

C Features
In this section we describe the main guarantees of our proposed system and how
it achieves them.

C.1 Anonymity
Anonymity is provided to both payer and payee as long as both interact truth-
fully. At no point during the transaction does the payee come to know about
 An Online, Transferable E-Cash Payment System 101

the payer’s identity. The payer merely transfers the encrypted version of coins
used during the transaction and the coins themselves do not contain the iden-
tity of the payer. Thus, neither the payee nor the verifying authority can break
the anonymity of the payer. In any case, a payee with honest intentions will be
satisfied if he gets paid for the goods being transferred and has no advantage
in getting to know the identity of the payer. Similarly, the verifying authority
is concerned about the validity of the coins being spent and the identity of the
payer is immaterial for this purpose.
However, the identity of the payee is known to the payer. Without this knowl-
edge the payer cannot transfer the coins to the payee. What the payee will be
interested in is whether he remains anonymous to the verifying authority. This
is guaranteed by the protocol since the merchant’s identity is never revealed in
the basic coin exchange protocol. If the merchant tries to abort the transaction
on receipt of valid coins from the verifying authority then the resolution protocol
initiated by the customer would reveal the identity of the payee to the verifying
authority. Thus, the merchant remains anonymous to the verifying authority as
long as he involves himself in the transaction in a fair manner.

C.2 Fairness

Our proposed system guarantees fairness to both the parties, the customer C
and the merchant M. By fairness we mean that irrespective of the final outcome
of a transaction, whether completed or aborted, none of the parties involved in a
transaction suffer a loss in terms of money or goods. The merchant M transfers
goods to C only on receipt of coins authenticated by the verifying authority. Thus
the e-payment mechanism guarantees that he does not have to deliver goods if
proper payment is not made. A resolution protocol initiated by a customer on
a “double spent” coin will be detected by the verifying authority. Also, the
merchant himself will hold a REJECT signal signed by the verifying authority
for the invalid transaction. This is proof enough for the merchant to not deliver
the goods. Hence, the payment mechanism ensures fairness to the merchant.
The Customer C is guaranteed fairness by the resolution protocol. If he has
indeed transferred valid coins, that are not double spent ones, then by initiating
the resolution protocol the erring merchant M can be made to deliver the goods.
A merchant will not dishonour a transaction since he will run the danger of being
blacklisted. This may adversely affect his future business prospects.

C.3 Transferability

A major and significant feature of our proposed mechanism is the transferability

of coins. Transferability of a coin is achieved by time stamping it at every trans-
action by a verifying authority. Transferability would imply that there would be
no need for the withdrawal and deposit protocols for every transaction. Also, for
achieving this feature there is no dependence on a unique trusted third party.
102 R. Sai Anand and C.E. Veni Madhavan

The load of verification of the coins is evenly spread across several verifying
authorities so that congestion does not become a bottleneck.

D Extensions/Optimizations
In this section we outline some extensions to the basic coin exchange protocol
to cover the situation where more than one coin is spent in a transaction. We
also discuss a hierarchy within the verifying authorities to optimize the coin
verification stage.

D.1 Payment with Multiple Coins

When more than one coin is spent in a transaction it is not practical to encrypt
all the coins using a public key of the verifying authority. Instead, the customer
C generates a symmetric key, KCV , and encrypts this key and the hash value
as described in Step 3 of the basic coin exchange protocol using the public key
of the verifying authority. The coins are then encrypted using the symmetric
key, KCV , generated. This key could also be used to send the change back to
C if exact change cannot be tendered by C. Since, the verifying authority does
not know the identity of the customer the “change” coins will be sent via the
merchant who will piggyback these along with the signed receipt of the goods.

D.2 Fungibility
Fungibility (i.e. the feature of breaking a coin into coins of smaller denomina-
tions) can be achieved in the following manner. The user is provided with a
tamper resistant device which will take as input, from the user, the coin that is
to be split into smaller denominations. The exact change necessary is specified
by the user. The device has a secret key embedded within it that it uses to sign
the smaller denominations. The coins that are signed do not have the sanctity
of a coin signed by the bank. But, the verifying authority can ensure that the
change produced is from a genuine coin. The change produced by the device
contains all the information of the coin that is being “changed” and also the
details of the change itself. It should also contain a nonce so that the same coin
cannot be used to make a different set of change later. Finally, the change is
signed using the key installed within the device before returning it to the user.

D.3 Organization of Verifying Authority

In practice, most transactions would involve exchange of more than a single coin.
In this case, for improving the efficiency of the coin verification stage a distribu-
tion of the work across a hierarchy is necessary. For each denomination of coins a
different entity verifies coins of that denomination. During peak hours, depend-
ing on the load at each of these entities the verification could be distributed
evenly across them.
 An Online, Transferable E-Cash Payment System 103

E Conclusions

We have described an electronic payment system with the transferability prop-

erty. This eliminates the withdrawal and deposit protocols. Also, new coins need
not be issued for every transaction as in payment schemes without the transfer-
ability property. We have removed the unfavourable load that would be placed
on the authority that verifies coins by distributing the load across several en-
tities. The computations involved compare favourably with schemes of similar
nature. Fairness to both merchant and customer is ensured by the resolution
protocol. Thus, the system ensures that neither money nor goods are lost by
either party. This holds good for transactions that are completed normally or
aborted. The proposed system also provides security and anonymity guarantees
to the participants in a transaction.

References
1. Abe, M. , Fujisaki, E.: How to Date Blind Signatures. Advances in Cryptology -
ASIACRYPT ’96, LNCS, Volume 1163.
2. Anderson, R., Manifavas, C., Sutherland, C.: Netcard - a practical electronic cash
system. Fourth Cambridge Workshop on Security Protocols, LNCS, April 1996.
3. Brands, S.: Electronic Cash on the Internet. Proceedings of the Internet Society
1995 Symposium on Network and Distributed System Security, February 1995.
4. Chaum, D.: Blind Signatures for Untraceable Payments. Advances in Cryptology -
Crypto ’82 Proceedings, Plenum Press, 1983.
5. Chaum,D.: Security without Identification: Transaction Systems to Make Big
Brother Obsolete. Communications of the ACM v.28, n.10, October 1985.
6. Chaum, D., Fiat, A., Naor, M.: Untraceable Electronic Cash. Advances in Cryptol-
ogy - CRYPTO’88, LNCS, Volume 403, 1990.
7. Hauser, R., Steiner, M., Waidner, M.: MicroPayments based on iKP Technical re-
port. IBM Research Division, Zurich Research Laboratory, January, 1996.
8. Medvinsky, G., Neumann, B.C.: NetCash: A design for practical electronic currency
on the Internet. First ACM Conference on Computer and Communication Security,
November 1993.
9. Pointcheval, D., Stern, J.:Provably Secure Blind signature Schemes. Advances in
Cryptology - ASIACRYPT ’96, LNCS, Volume 1163. preprint, MIT.
10. Rivest, R.L.: Electronic Lottery Tickets as Micropayments.
11. Rivest, R.L., Shamir, A.: PayWord and Micromint - Two simple Micropayment
Schemes. preprint, MIT, May 1996.

View publication stats