IPSJ Transactions on Mathematical Modeling and Its Applications

Vol. 3

No. 3

107–116 (Oct. 2010)

Regular Paper

Towards Modeling Stored-value Electronic Money Systems
Shunsuke Inenaga,†1 Kenichiro Oyama†1and Hiroto Yasuura†1
This paper presents mathematical and general models of electronic money
systems. The goal of the paper is to propose a ﬁrst framework in which various kinds of e-money systems can be uniformly represented and their security
properties can be evaluated and compared. We introduce two kinds of e-money
system models; a note-type e-money system model and a balance-type e-money
system model. We show that any balance-type e-money system with eﬃcient
data transmission cannot be simulated by any note-type e-money system. Thisimplies that balance-type e-money systems are strictly faster in data communication. Then, we show that a forged monetary value can be detected in somenote-type e-money systems, while it cannot be detected in any balance-type emoney systems with eﬃcient data communication. This implies that note-type
e-money systems seem to be more secure.

1. Introduction
Electronic money (e-money) is a new kind of money that is stored and spent
only electronically. In particular, stored-value e-money systems have been successful and widely used in countries such as Japan, Hong-Kong, and Singapore,due to their convenience. In these systems, an electronic monetary value is stored
on a device that is controlled by a user, such as a smart card and a mobile phone.
Stored-value e-money systems are often used as an eﬃcient replacement of cash
payments with coins and notes, because users do not have to look for coins andnotes in their wallet and merchants do not have to store many coins and notes
for changes. Also, since most stored-value e-money systems employ contact-lesssmart cards as users’ devises, payments can very quickly be done simply by facing
a smart card to a card reader.
Two types of stored-value e-money systems are popular today; One is a note†1 Graduate School of Information Science and Electrical Engineering, Kyushu University

107

type e-money system in which digital notes are stored within each user’s devise(e.g., a smart card). Since note-type e-money systems are electronic simulationof today’s physical cash systems, the value of each digital note is ﬁxed. The ﬁrst
note-type e-money was proposed by Chaum 1) (called electronic cash or e-cash
therein), and it has extensively been studied since (e.g., see Refs. 2)–6)). An
example of a real-world note-type e-money system is a British e-money systemcalled mondex 7) . The other is a balance-type e-money system in which an accumulated value representing the balance of money is stored within each user’s
devise. Prepaid e-money systems that have widely been used in Japan, HongKong, and Singapore are kinds of balance-type e-money system.
Most e-money systems currently used in the real world are of the latter type,balance-type e-money systems 8) . This is because balance-type e-money systems
tend to be much more “lightweight” than note-type ones. Indeed, this paper willshow that what distinguishes note-type and balance-type e-money systems is thedata size communicated between users for money value exchanges. That is, wewill prove that the lower bound of data size for a value transfer in any note-type
e-money system is strictly larger than that in any balance-type e-money system.
Security and privacy properties of stored-value e-money systems have been wellstudied 9) , and there have been some attempts to analyze diﬀerent kinds of storedvalue e-money systems from security and privacy viewpoints 10),11) . However, theexisting researches have not provided any general framework in which various emoney systems can be compared in a uniform way, or any analysis of security andprivacy in a uniﬁed manner. Motivated by this background, this paper presents
a ﬁrst mathematical and general model for stored-value e-money systems. All
the existing stored-value e-money systems well ﬁt into our model, and hence we
can compare their security properties within a uniﬁed framework.
In this paper, we analyze security properties of e-money systems with oﬀline payments 5) , where neither a trusted third party or the bank is involved inany e-money transfer between users. That is, the users’ devises are assumed
to be capable of peer-to-peer communications (e.g., infrared ray communication
between two mobile phones, or a contact-less smart card and a card reader).
In particular, this paper focuses on the detectability of forged monetary values.
This is a rather important security issue of e-money, as it is easy to duplicate

c 2010 Information Processing Society of Japan

108

Towards Modeling Stored-value Electronic Money Systems

or alter electronic data. We analyze the detectability of forged values in notetype and balance-type e-money systems, based on the proposed general e-money
models. As a result, we will show that some note-type e-money systems havedetectability of forged values, while no balance-type e-money systems with aneﬃcient communication complexity have the detectability.
The rest of the paper is organized as follows. In Section 2, we introduce a
general money system model which consists of three kinds of elements: holders, mediums, and values. Examples of holders are wallets for cash systems
and smart cards for e-money systems. Mediums can be seen as (digital andphysical) coins and notes. Values represent monetary values (e.g., 1 dollar, 2dollars, etc.) of mediums. Sections 3 and 4 extend the general money model to anote-type e-money system model and to a balance-type e-money system model,
respectively. In Section 5, we introduce lightweight protocols for e-money transfer between holders. The concept of lightweight protocols diﬀerentiates note-type
and balance-type e-money systems in terms of communication data eﬃciency. In
Section 6, we show detectability (resp. undetectability) of forged values in notetype e-money systems (resp. balance-type e-money systems). Finally in Section 7
we conclude and state our future work.
A preliminary version of this paper is in Ref. 12).
2. Money System ModelIn this section, we present our general money system model and some operations on the proposed model. A money system is formalized as follows.
Definition 1 A money system is a quintuple (V , M , H , vf, hf) such that
• V = {0, 1, 2, . . . , n} is a ﬁnite set of non-negative integer values,• M is a ﬁnite set of mediums,• H is a ﬁnite set of holders,• vf : M → V is called a value function, and• hf : M → H is called a holder function.
A medium m is an abstract model of anything that represents a monetary value
v. A coin and a note are examples of a medium. A holder is an abstract modelof anything or anyone that stores a medium. A wallet and a smart card are
examples of a holder, and a user himself can also be regarded as a holder.

IPSJ Transactions on Mathematical Modeling and Its Applications

Vol. 3No. 3

Fig. 1 The money system model. The arrows from M to H represent the hf function, while
those from M to V do the vf function.

For any m ∈ M , if h = hf(m) ∈ H , then we say that holder h has medium m.
For any m ∈ M , if v = vf(m) ∈ V , then we say that medium m carries value v.
For any h ∈ H , if v = hf(m)=h vf(m) ∈ V , then we say that holder h has total
value v.
Figure 1 shows the money system model of Deﬁnition 1.
Example. Assume that holder Alice has a 1 dollar coin c. Then hf(c) = Aliceand vf(c) = 1.
In the following subsections, we introduce operations by a holder or by a pairof holders, which will extend the above static model to a dynamic one. Each
operation makes some alteration to the mapping vf from M to V and/or to themapping hf from M to H . To distinguish the mappings before and after anoperation, we introduce the notion of time unit t. We denote by vft and hft
the mappings vf and hf at time t, respectively. After an operation has been
conducted, the resulting mappings are denoted by vft+1 and hft+1 , respectively.
That is, a single operation increases the time unit by one.
2.1 Money Transfer
A most basic operation in the money system model is to transfer some amount107–116 (Oct. 2010)

c 2010 Information Processing Society of Japan

109

Towards Modeling Stored-value Electronic Money Systems

of money (value) from a holder to another holder, which is formalized as follows.
Definition 2 A transfer of value v ∈ V from holder h ∈ H to holder h ∈ H(h = h ) at time t is an operation such thatvft (m) ≥ v,
(1)
hft (m)=h

vft+1 (m) =hft+1 (m)=hvft (m) − v,

(2)vft (m) + v,

(3)vft (m).

(4)

hft (m)=h

hft+1 (m)=h

vft+1 (m) =hft (m)=h

and for any holder h = h, h ,vft+1 (m) =hft+1 (m)=hhft (m)=h

Equation (1) implies that a transfer of value v can be conducted only if the total
values that holder h has is at least v. Eq. (2) implies that the total values that
holder h has decreases by v, and Eq. (3) does that the total values that holderh has increases by v. Eq. (4) says that the total values that any other holder hhas does not change due to the transfer.
Example. Assume that Alice has a total of 10 dollars and Bob has a total of 5 dollars at time t. Now Alice is giving 4 dollars to Bob. Then hft (m)=Alice vft (m) =


t
t+1
10,
(m) = 10 − 4 = 6, andhft (m)=Bob vf (m) = 5,
hft+1 (m)=Alice vft+1(m) = 5 + 4 = 9.
hft+1 (m)=Bob vf
Remark. The money model of Deﬁnition 1 lacks the bank, an important entityof money systems. However, we can regard the bank as a special kind of holder
in our model. A withdrawal of money is then regarded as a value transfer fromthe bank to a holder, and a deposit of money is the other way round.
2.2 Money Forgery
Next, we deﬁne an operation that relates to an attack to the system. Let
fvf : M → V be a function called a forged value function. We assume thatfvft (m) ≥ vft (m) for any medium m ∈ M and at any time t.
Definition 3 A forgery of value fv > 0 by holder h ∈ H at time t is an operationsuch thatIPSJ Transactions on Mathematical Modeling and Its Applications

Vol. 3No. 3(5)fvft+1 (m) = vft (m) + fv andvft+1 (m) = vft (m)(6)
with some medium m ∈ M such that hft (m) = hft+1 (m) = h.
Equations (5) and (6) imply that although the value measured by the forgedvalue function fvf of medium m increases by fv from time t to time t + 1, theactual value by the value function vf does not change from time t to time t + 1.
The above value fv is called a forged value.
Example. Assume that Alice has a smart card s with the balance of 1 dollar
at time t, and now she is illegally adding a forged value of 9 dollars into hersmart card. Then fvft+1 (ms ) = vft (ms ) + fv = 1 + 9 = 10, where ms denotes a
medium associated with the smart card s.
2.3 Forged Money Transfer
Next we deﬁne an operation of transferring a forged value from a holder toanother holder.
Definition 4 A transfer of forged value fv ∈ V from holder h ∈ H to holderh ∈ H (h = h ) at time t is an operation such that
fvft (m) ≥vft (m) + fv ,(7)
hft (m)=h

hft (m)=h
t+1

fvf

(m) =

hft+1 (m)=hfvft (m) − fv ,(8)

fvft (m) + fv ,(9)

fvft (m).

(10)

hft (m)=h

hft+1 (m)=h

fvft+1 (m) =hft (m)=h

and for any holder h = h, h ,fvft+1 (m) =hft+1 (m)=hhft (m)=h

Equation (7) implies that a transfer of forged value fv can be conducted only if
the total forged values that holder h has is at least fv . Eq. (8) implies that the
total forged values that holder h has decreases by fv , and Eq. (9) does that the
total forged values that holder h has increases by fv . Eq. (10) says that the total
forged values that any other holder h has does not change due to the transfer.
Example. Assume that holder Alice has a fake 10 dollar note b, and is giving b to

107–116 (Oct. 2010)

c 2010 Information Processing Society of Japan

110

Towards Modeling Stored-value Electronic Money Systems


Bob. Since fvft (b) = 10, we get hft (m)=Alice fvft (m) − hft (m)=Alice vft (m) ≥fvft (b) − hft (b) = 10, hft+1 (m)=Alice fvft+1 (m) = hft (m)=Alice fvft (m) − 10,
and hft+1 (m)=Bob fvft+1 (m) = hft (m)=Bob fvft (m) + 10.
2.4 (Un)detectability of Forged Money
We deﬁne the detectability of a forged value, as follows.
Definition 5 A forged value fv ∈ V w.r.t. medium m ∈ M is said to be detectable at time t if fvft (m)−vft (m) = fv is computable (under some conditions),
and is said to be undetectable otherwise.
In this paper, we deal with the following problem that concerns the security ofmoney systems.
Problem 1 (Detectability of transferred forged value) Assume that forged value fv > 0 is transferred from any holder h ∈ H to any holder h ∈ H (h =h ) at time t. Is forged value fv detectable at time t + α with α ≥ 1?
In Sections 3 and 4 we will introduce two kinds of e-money systems based on
the money model of Deﬁnition 1. Section 5 will discuss the signiﬁcant diﬀerence
between those systems. Then in Section 6 we will discuss Problem 1 for the twokinds of e-money systems.

Fig. 2 Before transferring value v from h to h on a note-type e-money system at time t.
There exists medium m such that vft (m) = v and hft (m) = h.

3. Note-Type E-Money System ModelIn this section, we propose a note-type e-money system model that is an electronic simulation of today’s note-based cash system. This type of e-money system
has been in practical use 13) and has widely been studied 1)–6) .
Definition 6 An note-type e-money system is a money system of Deﬁnition 1
with the following restriction: For any medium m ∈ M and at any time t,
vft+1 (m) = vft (m).
(11)
That is, in a note-type e-money system model, the value that each medium carries
is ﬁxed (i.e., invariant with time), as is the case with the physical cash system.
Definition 7 A transfer of value v ∈ V from holder h to holder h (h = h ) ina note-type e-money system is an operation such that for some Q ⊆ M ,hft (m) = h for any m ∈ Q,vft (m) = v,m∈Q

IPSJ Transactions on Mathematical Modeling and Its Applications

Vol. 3No. 3

Fig. 3 After transferring value v from h to h on a note-type e-money system at time t + 1.
Now vft+1 (m) = v and hft+1 (m) = h . Also hft+1 (m ) = hft (m ) for any m = m.

hft+1 (m) = h for any m ∈ Q,
and for any m ∈/ Q, hft+1 (m ) = hft (m ).
See Fig. 2 and Fig. 3 that illustrate a transfer of value v from h to h in anote-type e-money system model.
The following proposition shows that a money transfer of a note-type e-money
system deﬁned above is a money transfer of a money system model.
Proposition 1 A transfer of value v ∈ V in a note-type e-money system of

107–116 (Oct. 2010)

c 2010 Information Processing Society of Japan

111

Towards Modeling Stored-value Electronic Money Systems

Deﬁnition 7 satisﬁes the conditions of Deﬁnition 2.


t
t+1
Proof.
(m)m∈Q vf (m) = v satisﬁes Condition (1). By Eq. (11),m∈Q vf= v after a transfer of value v. Moreover, since hft (m) = h, hft+1 (m) = h for anym ∈ Q, and hft+1 (m ) = hft (m ) for any m ∈/ Q, we get hft+1 (m)=h vft+1 (m)=



t
t+1
(m) = hft (m)=h vft (m) + v, and forhft (m)=h vf (m) − v, 
hft+1 (m)=h vf

t+1
t
(m) =
any holder h = h, h ,hft+1 (m)=h vf
hft (m)=h vf (m). Hence
Conditions (2), (3), and (4) hold.

Now we deﬁne a forged value transfer in a note-type e-money system as follows:
Definition 8 A transfer of forged value fv ∈ V from holder h to holder h(h = h ) in a note-type e-money system is an operation such that for someR ⊆ M,
hft (m) = h for any m ∈ R,
fvft (m) =vft (m) + fv ,
m∈R
t+1



m∈R

for any m ∈ R,
hf (m) = h
t+1
fvf (m) =vft+1 (m) + fv ,

m∈R

m∈R

and for any m ∈/ R, hft+1 (m ) = hft (m ).
Proposition 2 A transfer of forged value fv ∈ V in a note-type e-money system
of Deﬁnition 8 satisﬁes the conditions of Deﬁnition 4.

Proof. Since hft (m) = h for any m ∈ R and m∈R fvft (m) = m∈R vft (m) +fv , Condition (7) is satisﬁed. Since hft+1 (m) = h = h for any m ∈ R, we havethat{p ∈ M | hft+1 (p) = h} = {q ∈ M | hft (q) = h} − R and{p ∈ M | hft+1 (p ) = h } = {q  ∈ M | hft (q  ) = h } ∪ R.
Therefore Conditions (8) and (9) hold. Condition (10) holds since hft+1 (m ) =hft (m ) for any m ∈/ R.
4. Balance-Type E-Money System Model
Here, we propose a balance-type e-money system model in which an accumulated value that represents the balance of money is stored in each holder. Thatis, a ﬁxed single medium is associated with each holder, and the value that is

IPSJ Transactions on Mathematical Modeling and Its Applications

Vol. 3No. 3

Fig. 4 Before transferring value v from h to h on a balance-type e-money system at time t.
Here we have vft (mh ) ≥ v.

carried by the medium varies with time. A number of balance-type e-money
systems have been proposed and are in practical use8) .
Definition 9 A balance-type e-money system is a money system of Deﬁnition 1
with the following restriction: At any time t, hft is a bijection and for any m ∈ M
hft (m) = hft+1 (m).
Namely, in the balance-type e-money system model, there is a one-to-one relation between a holder and a medium, and the relation is invariant over time.
For any holder h ∈ H , let mh denote a unique medium that h has, namely
hft (mh ) = h.
A transfer of value in a balance-type e-money system is deﬁned as follows:
Definition 10 A transfer of value v ∈ V from holder h ∈ H to holder h ∈ H(h = h ) in a balance-type e-money system is an operation such thatvft (mh ) ≥ v,
vft+1 (mh ) = vft (mh ) − v,
vft+1 (mh ) = vft (mh ) + v,
and for any m ∈ M such that m = mh and m = mh , vft+1 (m ) = vft (m ).
See Fig. 4 and Fig. 5 that illustrate a transfer of value v from holder h toanother holder h in the balance-type e-money system model.
The following proposition shows that a money transfer of the balance-type
e-money system deﬁned above is a money transfer of a money system model.

107–116 (Oct. 2010)

c 2010 Information Processing Society of Japan

112

Towards Modeling Stored-value Electronic Money Systems

5. Lightweight Money Transfer Protocol

Fig. 5 After transferring value v from h to h on a balance-type e-money system at timet + 1. Now vft+1 (mh ) = vft (mh ) − v and vft+1 (mh ) = vft (mh ) + v.

Proposition 3 A transfer of value v ∈ V in a balance-type e-money system ofDeﬁnition 10 satisﬁes the conditions of Deﬁnition 2.
Proof. Since hft is a bijection and hft (mh ) = h for any holder h ∈ H , we havett
hft (m)=h vf (m) = vf (mh ) for any time t. Hence the proposition holds.
A transfer of forged value in a balance-type e-money system is deﬁned as follows:
Definition 11 A transfer of forged value fv ∈ V from holder h ∈ H to holderh ∈ H (h = h ) in a balance-type e-money system is an operation such thatfvft (mh ) ≥ vft (mh ) + v,
fvft+1 (mh ) = fvft (mh ) − v,
fvft+1 (mh ) = fvft (mh ) + v,
and for any m ∈ M − {mh , mh }, fvft+1 (m ) = fvft (m ).
Proposition 4 A transfer of forged value fv ∈ V in a balance-type e-money
system of Deﬁnition 11 satisﬁes the conditions of Deﬁnition 4.
Proof. Since hft (mh ) = h and {m ∈ M | hft (m) = h} = {mh } for any holder
h and time t, Conditions (7), (8), and (9) hold. Condition (10) holds since
vft+1 (m ) = vft (m ) and fvft+1 (m ) = fvft (m ) for any m ∈ M − {mh , mh }.


IPSJ Transactions on Mathematical Modeling and Its Applications

Vol. 3No. 3

In this section, we introduce lightweight protocols for transferring a value in thee-money systems of the previous sections. A lightweight protocol is a protocolthat transmits minimum amount of data for a value transfer between holders.
Definition 12 Any protocol for a transfer of a value from holder h to holder his said to be lightweight if it satisﬁes the following properties:(a) The protocol is “oﬀ-line”. That is, the communication is only between h andh and neither the bank or a trusted third party is involved in the protocol.
(b) The data transmitted from one holder to the other is at most log2 n + O(1)bits.
Lightweight protocols are basic, yet useful to construct practical e-money systems, as a value transfer between holders can quickly be accomplished. Also,
since the data communication is oﬀ-line and only between holders, anonymous
payments are possible with lightweight protocols.
It is not diﬃcult to see that there exist lightweight protocols for a balancetype e-money system, which satisfy the properties of Deﬁnition 12. For instance,
consider the following protocol in which a value v is transferred from holder h to
holder h in a balance-type e-money system.
( 1 ) Holder h sends integer v to holder h .
( 2 ) Holder h subtracts v from the value in medium mh .
( 3 ) Holder h adds v to the value in medium mh .
( 4 ) Holder h tells holder h that h has received v.
It is rather clear that the communication of the above protocol is only between
h and h . Also, as the value of v is at most n, we can transfer value v usinglog2 n bits.
Note that we can encrypt the value v by common-key or public-key encryption
algorithms without increasing its data size, hence lightweight protocol can protect
its communication contents from eavesdroppers.
It is also possible to extend the above protocol so that the two holders conductmutual authentication: We can index each holder hi using an id i for each holder.
Each id can be implemented with log2 |H | bits. Assuming that H is ﬁxed andthe length of credentials (e.g., passwords) is linear in log2 |H | or is constant, h107–116 (Oct. 2010)

c 2010 Information Processing Society of Japan

113

Towards Modeling Stored-value Electronic Money Systems

and h can mutually authenticate each other while only constant-sized data arecommunicated between them. We remark that in most of real-world applications
the length of credentials is constant.
On the other hand, the following lemma shows that a value transfer in any
note-type e-money system cannot be implemented by a lightweight protocol.
Lemma 1 A value transfer in any note-type e-money system requires to transmit
1
data of size Ω(n 3 log n) from holder h to holder h .
Proof. Consider k distinct values 1 ≤ n1 < n2 < · · · < nk ≤ n. Let x be themaximum number of mediums that the holder h has for every value ni , where1 ≤ i ≤ k. Then there exist (x + 1)k combinations of mediums that the holder h
may have. Therefore at least log2 (x + 1)k = k log2 (x + 1) bits of informationis required to be transmitted from holder h to holder h .
Let n be the maximum value that can be transferred between holders. If
1
nk = n 3 , then11x(2kn 3 − k 2 + k)xk(2n 3 − k + 1)
=
≤ n.
2
2
1
1
Now consider the case (x(2kn 3 − k 2 + k))/2 = n. Choosing k = n 3 , we get
11
x = O(n 3 ). Hence k log2 (x + 1) = O(n 3 log n) bits of information is required
to be transmitted from h to h in this case.
We ﬁnally remark that the preconditions of a value transfer in a note-type
e-money system of Deﬁnition 7 are all satisﬁed in the above scenario.
Lemma 1 also means that a lightweight value transfer protocol is what distinguishes note-type e-money systems from balance-type e-money systems, that is,any balance-type e-money systems with a lightweight protocol cannot be simulated by any note-type e-money systems.
6. (Un)detectability of Forged Values
In this section we show whether a forged value is detectable or undetectablein e-money systems, after a forged value transfer of Deﬁnition 8 or Deﬁnition 11
has conducted.
Recall Problem 1 that deﬁnes the problem of detecting a forged value fv thathas been transferred from holder h to holder h . In the sequel, we consider thefollowing speciﬁc situation:

IPSJ Transactions on Mathematical Modeling and Its Applications

Vol. 3No. 3- At time t, holder h has value zero, that is,vft (m) =fvft (m) = 0.
hft (m)=hhft (m)=h

- A value v > fv is transferred from holder h to holder h at time t.
The ﬁrst assumption is to simplify the analysis. The second assumption is tomake the problem more interesting, diﬃcult, and realistic – a mixture of (legal)value and forged value is transferred from holder h to holder h , and the task is
to compute how much out of the mixed value has been forged.
Theorem 1 There exists a note-type e-money system in which the forged value
fv is detectable.
Proof. We here deal with the case where a single medium carrying value v istransfered from holder h to holder h . The cases where more than one medium
are transferred can be shown similarly.
Now consider the following note-type e-money system: Each medium mj is
assigned a unique index j, with 1 ≤ j ≤ |M |. Each holder has an array A of size
|M | such that A[j] stores the value of medium mj , that is, A[j] = vf(mj ). By
deﬁnition of a note-type e-money system, the value of each element A[j] is ﬁxed
for any time t. Assume that the value of a medium mj has been forged and it istransferred from h to h at time t. Let fv = fvft (mj )−vft (mj ) = v−vft (mj ) > 0.
Then fv is detectable since A[j] = vft+α (mj ) = vft (mj ) for α ≥ 1. Using apublic-key digital signature algorithm (e.g., see Ref. 14)), we can check whether
the index j of a medium mj has been illegally altered or not.
Let us now consider a duplicated medium dm from some medium m such thatvft (m) = v. Note fv = fvft (dm) − vft (dm) = v − 0 = v. This cannot be solved
simply by using the array A. However, it has been shown in the literature (e.g.,
see Ref. 4)) that it is possible to construct a note-type e-money system in which
every duplicated medium dm can be detected by the bank after dm is sent from h
to h . We remark that the bank is only contacted by holder h after a transaction
between the holders. Hence any value transfer between holders remains oﬀ-line.
Therefore the theorem holds.
As shown above, the forged value is detectable in some note-type e-money
system. On the contrary, the following theorem shows that the forged value is

107–116 (Oct. 2010)

c 2010 Information Processing Society of Japan

114

Towards Modeling Stored-value Electronic Money Systems

undetectable in any balance-type e-money system which uses a lightweight valuetransfer protocol.
Theorem 2 In any balance-type e-money system, the forged value fv is undetectable with a lightweight value transfer protocol of Deﬁnition 12.
Proof. Note that, by Lemma 1, we cannot apply Theorem 1 to any balanced-type
e-money system using a lightweight protocol.
Let r = v − fv and d be the function s.t. d(v, r) = v − r = fv . Then the problem
of detecting the forged value fv is identical to computing the value d(v, r).
We prove the theorem by showing that the one-way deterministic communication complexity 15) from h to h so that the value d(v, r) is computable is 2log2 nbits. Let us denote the communication complexity by C. Recall that the maximum possible value for v is n. Since the value v is already transfered from h toh , and h did not know the value v beforehand, the communication complexity
C is at least log2 n . Hence the question is how large is the extra data that need
to be additionally transmitted from h to h in order that d(v, r) is computable.
We regard computing d(v, r) as determining the cell (v, r) of an n × (n + 1)
matrix D such that D[i, j] = i − j for 1 ≤ i ≤ n and 0 ≤ j ≤ n. As was shown in
Ref. 15), the one-way communication complexity is log2 (drow (D)) bits, where
drow (D) denotes the number of distinct rows in D. Since D[i + 1, j] = D[i, j] + 1
for every 1 ≤ i ≤ n − 1, we have drow (D) = n. Therefore, C ≥ log2 n +log2 (drow (D)) = log2 n + log2 n = 2log2 n . On the other hand, it caneasily be seen that C ≤ 2log2 n . Hence C = 2log2 n .
By Deﬁnition 12, the data transmitted from h to h in any lightweight protocol
must be at most log2 n + O(1) bits. Hence we conclude that the forged value fv
is undetectable in any balance-type e-money systems that employ a lightweight
protocol.

7. Conclusions and Future Work
This paper presented a general model of money systems and its extended versions to two kinds of e-money systems, note-type and balance-type e-money systems. Using the notion of a lightweight protocol, we showed that balance-type
e-money systems are more eﬃcient than note-type e-money systems in terms ofthe data size transmitted between holders. On the other hand, we showed thatIPSJ Transactions on Mathematical Modeling and Its Applications

Vol. 3No. 3

note-type e-money systems are more secure than balance-type e-money systems
from the view point of detectability of forged values.
The results of this work suggest the followings:( 1 ) In a balance-type e-money system, the upperbound n for a monetary valuetransfer has to be kept small. This is because once a large forged monetary
value is mixed with a legal value, it cannot be detected due to Theorem 2.
Also, it is suggested that a balance-type e-money system in the real world
should be limited to closed-loop payments, that is, once an electronic monetary value is used for purchase, it cannot be directly reused and has to bechanged to cash. This suggestion also comes from undetectability of forgedvalues shown in Theorem 2.
( 2 ) A note-type e-money system may become a “next-generation” secure emoney system. However, a drawback of this type of e-money system is thata merchant (a holder that receives money) needs to store enough “changes”
for arbitrary monetary value transfer, like today’s physical cash systems.
This obviously spoils a beneﬁt of electronic payments.
According to the above discussions, our future work is to model the following
type of e-money system: A divisible e-cash system 16),17) allows an electroniccoin to be divided into two coins having the same total amount of values as theoriginal coin. This allows us exact and eﬃcient payments without using changes.
Divisible e-cash systems can be seen as an intermediate between note-type emoney systems and balance-type e-money systems. A divisible e-cash system
can be described using our money model of Deﬁnition 1, as follows. Any medium
m having a value v ≥ 2 at time t can be divided into two mediums m1 andm2 having values v1 ≥ 1 and v2 ≥ 1, respectively, with v1 + v2 = v. That is,vft (m) = v and and vft+1 (m1 ) + vft+1 (m2 ) = v1 + v2 = v. The detectability offorged values in divisible e-cash systems needs to be examined using our model.
Yamasaki, et al. 18) proposed a general model of door access control that isbased on ﬁnite state machines. In their model, a door-key is regarded as a
medium that represents the right of a user to open a door, and various typesof door-keys such as physical keys, card keys, passwords, and biometrics well ﬁt
into the model. The inherent diﬀerence between door-access control and e-money
systems is whether each medium takes a Boolean value or a non-negative integer

107–116 (Oct. 2010)

c 2010 Information Processing Society of Japan

115

Towards Modeling Stored-value Electronic Money Systems

value. This implies that it should be possible to extend the model of Ref. 18) toe-money systems, and this may lead us to further insight of e-money systems.
Acknowledgments This work was in part supported by the Research Superstar Program of Kyushu University and by grant 08-01 from the Okawa Foundation for Information and Telecommunications.

16) Canard, S. and Gouget, A.: Divisible E-Cash Systems Can Be Truly Anonymous,
EUROCRYPT’07, LNCS, Vol.4515, pp.482–497, Springer (2007).
17) Okamoto, T.: An Eﬃcient Divisible Electronic Cash Scheme, CRYPTO’95, LNCS,
Vol.963, pp.438–451, Springer (1995).
18) Yamasaki, T., Inenaga, S., Ikeda, D. and Yasuura, H.: Modeling Costs of AccessControl with Various Key Management Systems, PDPTA’09, pp.676–682, CSREA
Press (2009).

References
1) Chaum, D.: Blind Signatures for Untraceable Payments, CRYPTO’82, pp.199–203,
Plenum Press (1982).
2) Au, M.H., Susilo, W. and Mu, Y.: Practical Compact E-Cash, ACISP’07, LNCS,
Vol.4586, pp.431–445, Springer (2007).
3) Brands, S.: Untraceable Oﬀ-line Cash in Wallet with Observers, CRYPTO’93,
LNCS, Vol.773, pp.302–318, Springer (1993).
4) Camenisch, J., Hohenberger, S. and Lysyanskaya, A.: Compact E-Cash, EUROCRYPT’05, LNCS, Vol.3494, pp.302–321, Springer (2005).
5) Chaum, D., Fiat, A. and Naor, M.: Untraceable Electronic Cash, CRYPTO’88,
LNCS, Vol.403, pp.319–327, Springer (1988).
6) Gouget, A.: Recent Advances in Electronic Cash Design, CARDIS’08, LNCS,
Vol.5189, pp.290–293, Springer (2008).
7) Mondex. http://www.mondex.com/
8) Payment and Settlement Systems Department, Bank of Japan: Recent Developments in Electronic Money in Japan (2008). BOJ Reports & Research Papers (Oct.
2008).
9) Hanacek, P.: Security of Electronic Money, Proc. SOFSEM’98, LNCS, No.1521,
pp.107–121 (1998).
10) Miyazaki, S. and Sakurai, K.: Classiﬁcation of Oﬀ-line Electronic Money Systems
and Evaluation of the Security against Insider Attacks (in Japanese), Transactionsof Information Processing Society of Japan, Vol.40, No.3, pp.1294–1304 (1999).
11) Suzuki, M. and Hirokawa, K.: Security Analysis on Electronic Money Systems
Including Compromise of Cryptographic Algorithms and/or Devices (in Japanese),
IEICE Technical Report, ISEC, No.2008-69, pp.39–46 (2008).
12) Inenaga, S., Oyama, K. and Yasuura, H.: Towards Modeling Stored-Value Electronic Money Systems, CISIM’09, pp.902–907, IEEE Computer Society (2009).
13) Clemons, E.K., Croson, D.C. and Weber, B.W.: Reengineering Money: the Mondex
Stored Value Card and Beyond, International Journal of Electronic Commerce,
Vol.1, No.2, pp.5–31 (1996).
14) Schneier, B.: Applied Cryptography, Wiley (1996).
15) Yao, A.C.-C.: Some Complexity Questions Related to Distributed Computing,
STOC’79, pp.209–213, ACM (1979).

IPSJ Transactions on Mathematical Modeling and Its Applications

Vol. 3No. 3(Received January 8, 2010)(Revised May 11, 2010)(Accepted July 5, 2010)
Shunsuke Inenaga is an associate professor of Institute forAdvanced Study, Kyushu University, and is a research associate
professor of Graduate School of Information Science and Electrical Engineering, Kyushu University. He received his B.E. from
Kyushu Institute of Technology in 2000, and his M.S. and Ph.D.
in science from Kyushu University in 2002 and 2003, respectively.
He became a research associate professor of Kyushu University in
2006, and an associate professor of Institute for Advanced Study, Kyushu University in 2009. His current research interests include stringology, algorithms anddata structures, and design and modeling of social information infrastructure.
He is a member of IPSJ and EATCS.

107–116 (Oct. 2010)

Kenichiro Oyama received his B.E. and M.E. from Kyushu
University in 2005 and 2007, respectively. His research interest
includes modeling electronic money systems. He currently works
for Fusic CO., Ltd.

c 2010 Information Processing Society of Japan

116

Towards Modeling Stored-value Electronic Money Systems

Hiroto Yasuura is an executive vice president of Kyushu University. He is also a professor of Department of Computer Science
and Communication Engineering, Graduate School of Information
Science and Electrical Engineering, and a member of System LSI
Research Center in Kyushu University. Prof. Yasuura received his
B.E., M.E. and Ph.D. degrees in computer science from Kyoto
University, Kyoto, Japan, in 1976, 1978, and 1983 respectively.
He was an associate professor in Kyoto University and moved to Kyushu University in 1991. His current interests include embedded system design, hardware/software co-design, system design methodology and social infrastructure.
He is a fellow of IEICE and IPSJ.

IPSJ Transactions on Mathematical Modeling and Its Applications

Vol. 3

No. 3

107–116 (Oct. 2010)

c 2010 Information Processing Society of Japan