# Date Attachable Offline Electronic Cash Scheme

Authors: Chun-I Fan; Wei-Zhe Sun; Hoi-Tung Hau
Journal: The Scientific World Journal
 (2014)

---

## Abstract

Electronic cash (e-cash) is definitely one of the most popular research topics in the e-commerce field. It is very important that e-cash be able to hold the anonymity and accuracy in order to preserve the privacy and rights of customers. There are two types of e-cash in general, which are online e-cash and offline e-cash. Both systems have their own pros and cons and they can be used to construct various applications. In this paper, we pioneer to propose a provably secure and efficient offline e-cash scheme with date attachability based on the blind signature technique, where expiration date and deposit date can be embedded in an e-cash simultaneously. With the help of expiration date, the bank can manage the huge database much more easily against unlimited growth, and the deposit date cannot be forged so that users are able to calculate the amount of interests they can receive in the future correctly. Furthermore, we offer security analysis and formal proofs for all essential properties of offline e-cash, which are anonymity control, unforgeability, conditional-traceability, and no-swindling.


---

## Body

## 1. Introduction

Due to the rapid growth of the Internet and communication developments, electronic commerce has become much more popular and widely used than ever [1–8]. The mobile telecommunications have been developed from 2 G to 3.5 G. Furthermore, LTE Advanced, 4 G, and 5 G are being implemented to the market in recent years. With the convenience of mobile network, people can do shopping or electronic payments by using any devices with network capability instead of leaving home. As a result, electronic commerce has been emphasized nowadays. Electronic cash (e-cash) is definitely one of the most popular research topics among electronic commerce. E-cash and the traditional cash notes are very much alike except e-cash is digitized and used on Internet transactions; therefore, it is very important that e-cash be able to hold the accuracy, privacy, and all other security concerns.A typical e-cash system usually consists of payers (customers), payees (shops), and a bank. There are two types of e-cash in general which are online e-cash [9–13] and offline e-cash [14–27]. Online e-cash system involves participation of the bank during transactions (the payment stage). Banks are able to check whether customers have double-spent the e-cash(s) or not, and if yes, banks can terminate the transactions at once. Thus, the bank has to be online during every transaction and it may lead to a bottleneck of the system. On the other hand, while banks do not participate in the payment stage of offline e-cash systems, double-spending check is only held during the deposit stage. Yet, the bank is set to be offline, but the system design is usually much more complicated than the online type and it may lead to a longer transaction time. Since both systems have their own pros and cons, they are used under different circumstances.Extending online and offline e-cash systems, many e-cash schemes with other different features have been proposed over the years. For instance, e-cash can be stored compactly such that the space to store these e-cash is much reduced [15, 16], e-cash is generated by multiauthorities instead of one bank only [25], exact payments e-cash [13], recoverable e-cash which can be recovered when an e-cash is lost [26], and so on.Based on the majority of the existing approaches, we summarize that a secure e-cash system should satisfy the following requirements.(i)
Anonymity: no one, except the judge, can obtain any information of the e-cash owner’s identity from the contents of e-cash.
(ii)
Unlinkability: no one, except the judge, can link any e-cash payment contents.
(iii)
Unforgeability: no one, except the bank, can generate a legal e-cash.
(iv)
Double-Spending Control: banks should have the ability to check if the e-cash is double-spent or not. No e-cash is allowed to be spent twice or more in an e-cash system.
(v)
Conditional-Traceability: the system should be able to trace and revoke the anonymity of users who violate any of the security rules so that they will receive penalties.
(vi)
No-swindling: no one, except the real owner, can spend a valid offline e-cash successfully.In order to perform double-spending checks, banks have to store information of e-cash(s) in their database. Thus, the database of banks grows in direct proportion to the number of e-cash(s) withdrawn. Embedding an expiration date into each e-cash has been considered since it helps the banks to manage the database more easily. On the other hand, customers have to exchange their expired e-cash(s) with banks for new ones so as to keep the validity of the e-cash. Furthermore, customers will receive interest from banks after cash is deposited. In order to guarantee customers will receive the right amount of interest, it is necessary for customers to attach the deposit date to their e-cash(s) and the date cannot be modified by anyone else [11]. So far, there are a number of online e-cash schemes with an expiration date attachment [9, 11, 28]. However, there are very few offline approaches [21].In this paper, we are going to propose an efficient date attachable offline e-cash scheme and provide formal proofs on essential properties to it in the random oracle model. Considering the practical needs, we pioneer to embed two kinds of date, which are expiration data and deposit date, to the offline e-cash. Moreover, we will offer anE-cash renewal protocol in our scheme (Section 3.2.5). Users can exchange their unused expired e-cash for a new one with another valid expiration date more efficiently. Compared with other similar works, our scheme is efficient from the aspect of considering computation cost.The rest of this paper is organized as follows. In Section2, we briefly review techniques employed throughout our scheme. Our proposed scheme is described in Section 3 in detail. Security proofs and analysis are covered in Section 4. Features and performance comparisons are made in Section 5, and the conclusion is given in Section 6.


## 2. Preliminaries

In this section, we briefly review techniques used in our date attachable offline e-cash scheme.


### 2.1. Chaum’s Blind Signature Scheme

Blind signature was first introduced by Chaum [29]. It has been widely used in e-cash protocols since it has been proposed. A signer will not be able to view the content of the message while she/he is signing the message. Afterwards, a user can get a message with the signature of the signer by unblinding the signed message. The protocol is described as follows.(1)
Initialization:
The signer randomly chooses two distinct large primesp and q, then computes n
=
p
q and ϕ
(
n
)
=
(
p
-
1
)
(
q
-
1
). Afterwards, the signer selects two integers e and d at random such that e
d
≡
1
(mod ϕ
(
n
)
). Finally, the signer publishes the public parameters (
e
,
n
) and a one-way hash function H.
(2)
User→ Signer: α
The user chooses a messagem and a random integer r in Z
n
*, then blinds the message by computing α
=
r
e
H
(
m
)
mod
⁡
n and sends it to the signer.
(3)
Signer→ User: t
After receivingα, the signer signs it with her/his private key d and sends it back to the user. The signed message will be t
=
α
d
mod
⁡
n.
(4)
Unblinding:
After receivingt from the signer, the user unblinds it by computing s
=
r
-
1
t
mod
⁡
n. The signature-message pair is (
s
,
m
).
(5)
Verification:
The(
s
,
m
) can be verified by checking if s
e
≡
H
(
m
) (mod
⁡
n) is true or not.


### 2.2. Chameleon Hashing Based on Discrete Logarithm

Chameleon hashing was proposed by Krawczyk and Rabin [30]. The chameleon hash function is associated with a one-time public-private key pair; it is a collision resistant function except for users who own a trapdoor for finding collision. Any user who knows the public key can compute the hashing, and for those who do not know the private key (trapdoor), it is impossible for them to find any two inputs which lead to the same hashing output. On the contrary, any user who knows the trapdoor can find the collision of given inputs. The construction of the chameleon hashing based on discrete logarithm is described as follows.(1)
Setup:
(i)
p, q: two large primes such that p
=
k
q
+
1,
(ii)
g: an element order q in Z
p
*,
(iii)
x: private key in Z
q
*,
(iv)
y: public key, where y
=
g
x mod p.
(2)
The function: a message m
∈
Z
q
* is given and a random integer r
∈
Z
q
* is chosen. The hash is defined ascham-hash
y
(
m
,
r
)
=
g
m
y
r mod p.
(3)
Collision: for a user who knows x, she/he is able to find the collision of the hash for any given m, m
′ such thatcham-hash
y
(
m
,
r
)
=
cham-hash
y
(
m
′
,
r
′
). The user derives r
′ in the equation m
+
x
r
=
m
′
+
x
r
′ (mod q).


## 2.1. Chaum’s Blind Signature Scheme

Blind signature was first introduced by Chaum [29]. It has been widely used in e-cash protocols since it has been proposed. A signer will not be able to view the content of the message while she/he is signing the message. Afterwards, a user can get a message with the signature of the signer by unblinding the signed message. The protocol is described as follows.(1)
Initialization:
The signer randomly chooses two distinct large primesp and q, then computes n
=
p
q and ϕ
(
n
)
=
(
p
-
1
)
(
q
-
1
). Afterwards, the signer selects two integers e and d at random such that e
d
≡
1
(mod ϕ
(
n
)
). Finally, the signer publishes the public parameters (
e
,
n
) and a one-way hash function H.
(2)
User→ Signer: α
The user chooses a messagem and a random integer r in Z
n
*, then blinds the message by computing α
=
r
e
H
(
m
)
mod
⁡
n and sends it to the signer.
(3)
Signer→ User: t
After receivingα, the signer signs it with her/his private key d and sends it back to the user. The signed message will be t
=
α
d
mod
⁡
n.
(4)
Unblinding:
After receivingt from the signer, the user unblinds it by computing s
=
r
-
1
t
mod
⁡
n. The signature-message pair is (
s
,
m
).
(5)
Verification:
The(
s
,
m
) can be verified by checking if s
e
≡
H
(
m
) (mod
⁡
n) is true or not.


## 2.2. Chameleon Hashing Based on Discrete Logarithm

Chameleon hashing was proposed by Krawczyk and Rabin [30]. The chameleon hash function is associated with a one-time public-private key pair; it is a collision resistant function except for users who own a trapdoor for finding collision. Any user who knows the public key can compute the hashing, and for those who do not know the private key (trapdoor), it is impossible for them to find any two inputs which lead to the same hashing output. On the contrary, any user who knows the trapdoor can find the collision of given inputs. The construction of the chameleon hashing based on discrete logarithm is described as follows.(1)
Setup:
(i)
p, q: two large primes such that p
=
k
q
+
1,
(ii)
g: an element order q in Z
p
*,
(iii)
x: private key in Z
q
*,
(iv)
y: public key, where y
=
g
x mod p.
(2)
The function: a message m
∈
Z
q
* is given and a random integer r
∈
Z
q
* is chosen. The hash is defined ascham-hash
y
(
m
,
r
)
=
g
m
y
r mod p.
(3)
Collision: for a user who knows x, she/he is able to find the collision of the hash for any given m, m
′ such thatcham-hash
y
(
m
,
r
)
=
cham-hash
y
(
m
′
,
r
′
). The user derives r
′ in the equation m
+
x
r
=
m
′
+
x
r
′ (mod q).


## 3. The Proposed Date Attachable Offline Electronic Cash Scheme

In this section, we will introduce a new date attachable offline e-cash scheme. Considering the issues mentioned in Section1, we propose a secure offline e-cash scheme with two specific kinds of date attached to the e-cash, which are expiration date and deposit date.


### 3.1. Outline of the Proposed Scheme

Here we are going to briefly describe the procedures of our scheme. The proposed scheme contains four protocols,withdrawal protocol, payment protocol, deposit protocol, ande-cash renewal protocol. A user withdraws an e-cash with an expiration date attached to it from the bank. A trusted computing platform (i.e.,judge device) [31, 32], as stated in the proposed scheme, is installed in the bank to hold the identity information of all users and it will further help trace users when it is needed. It is impossible for anyone except the judge to obtain any information embedded in the device [33]. Nowadays, judge device can be implemented by the technique of Trusted Platform Module (TPM) [32, 34] in practice.Before an e-cash is deposited, the depositor attaches the deposit date on the e-cash and sends it to the bank during the deposit stage. When the bank receives an e-cash, it will perform double-spending checking to verify whether the e-cash is doubly spent or not. The bank can derive secret parameters of the user who does double-spending and let the judge revoke the anonymity of the user. Besides, when an unused e-cash is expired, a user will be able to exchange it for a new one with a new expiration date. In our scheme, for the efficiency concerns, some of the unused parameters of users can remain unchanged while exchanging for a new valid e-cash. In the following sections, we will describe our scheme in detail.


### 3.2. The Proposed Scheme

Firstly, we define some notations as follows.(1)
H
1
,
H
2
,
H
3: three one-way hash functions, H
1
,
H
2
,
H
3
:
{
0,1
}
*
→
{
0,1
}
n.
(2)
H
4
,
H
5: two one-way hash functions, H
4
,
H
5 : {
0,1
}
*
→
{
0,1
}
q.
(3)
E
~
x, D
~
x: a secure symmetric cryptosystem. Plaintext is both encrypted and decrypted with a symmetric key x.
(4)
E
^
p
k
,
D
^
s
k: a secure asymmetric cryptosystem. Plaintext is encrypted with a public key p
k and decrypted with the corresponding private key s
k.
(5)
(
p
k
j
,
s
k
j
): the public-private key pair of the judge.
(6)
(
e
b
,
d
b
): the public-private key pair of bank.
(7)
D
a
t
e: expiration date. It represents an effective spending date of a withdrawn e-cash. Any e-cash withdrawn in the same period will have the same expiration date, and vice versa.
(8)
I
D
c: the identity of user C.
(9)
l
k, l
r: the security parameters.
(10)
A judge device: a tamper-resistant device which is issued by the judge. It is installed into the system of the bank. It is impossible to intercept or modify any information stored in the device.


#### 3.2.1. Initialization

Initially, the bank randomly chooses two distinct large primes(
p
b
,
q
b
) and computes RSA parameters n
b
=
p
b
q
b. It selects an integer e
b at random such that GCD(
ϕ
(
n
b
)
,
e
b
)
=
1, where ϕ
(
n
b
)
=
(
p
b
-
1
)
(
q
b
-
1
) and 1
<
e
b
<
ϕ
(
n
b
). Then, it finds a d
b such that e
b
d
b
≡
1
(mod ϕ
(
n
b
)
). Secondly, it also chooses two other large primes p and q and two generators g
1 and g
2 of order q in Z
p
*. Then, the bank publishes (
n
b
,
e
b
,
p
,
q
,
g
1
,
g
2
,
p
k
j
,
H
1
,
H
2
,
H
3
,
H
4
,
H
5
,
E
~
,
D
~
,
E
^
,
D
^
). Meanwhile, the judge embeds (
n
b
,
e
b
,
p
,
q
,
g
1
,
g
2
,
p
k
j
,
s
k
j
,
H
1
,
H
2
,
H
3
,
H
4
,
H
5
,
E
~
,
D
~
,
E
^
,
D
^
) into a judge device and issues it to the bank.


#### 3.2.2. Withdrawal Protocol

Users run the withdrawal protocol with banks to get an e-cash, as shown in Figure1, yet banks have to obtain information of users’ identity, such as I
D
c or account numbers, before the withdrawal protocol is proceeded. Therefore, users should perform an authentication with banks beforehand. Users can execute the withdrawal protocol by any devices that have the ability to compute and connect to the network. For instance, users can use mobile phones or computers to perform the withdrawal protocol and store the withdrawn e-cash. The detailed steps of the protocol are as follows.(1)
Bank→ User: D
Firstly, the user prepares parameters for withdrawing an e-cash. The user chooses integersa, x
1, x
2, r
1, r
2, and r
3 in random, where a
∈
R
Z
n
b
* and x
1, x
2, r
1, r
2, r
3
∈
R
{
0,1
,
…
,
q
-
1
} and selects a string k
∈
R
{
0,1
}
l
k randomly. The user then computes (
y
1
,
w
1
,
y
2
,
w
2
), where y
i
=
g
i
x
i
mod
⁡
p and w
i
=
g
i
r
i
mod
⁡
p for i
=
{
1,2
}. Secondly, the bank computes parameters for expiration date. It randomly chooses a r in Z
n
*, prepares D
=
Date
∥
r for some expiration date D
a
t
e. The bank will send D to the user when she/he requests to withdraw an e-cash.
(2)
User→ Bank: (
α
,
ϵ
)
After receivingD, the user prepares ϵ
=
E
^
p
k
j
(
k
∥
ID
c
) and
(1)
α
=
[
a
e
b
H
1
2
(
m
∥
D
)
]
-
1
mod
⁡
n
b
,
wherem
=
(
y
1
∥
w
1
∥
y
2
∥
w
2
∥
r
3
). Finally, the user sends (
α
,
ϵ
) to the bank.
(3)
Bank→ Judge device: (
ϵ
,
μ
,
D
)
The bank setsμ
=
I
D
c, where I
D
c is the identity of user C, and inputs it together with ϵ and D to the judge device.
(4)
Judge device→ Bank: (
β
,
E
~
k
(
b
,
σ
,
r
j
)
)
The judge device decryptsϵ and checks if μ
=
I
D
c. If not, it returns “ID error” to the bank; or else, it picks a random integer b
∈
R
Z
n
b
* and a string r
j
∈
R
{
0,1
}
l
r
j randomly. Then it computes σ
=
E
^
p
k
j
(
μ
∥
r
j
) and
(2)
β
=
[
b
e
b
H
3
(
σ
∥
D
)
]
-
1
mod
⁡
n
b
.
Finally, it encrypts(
b
,
σ
,
r
j
) by using the symmetric key k and outputs it together with β to the bank.
(5)
Bank→ User: (
t
,
E
~
k
(
b
,
σ
,
r
j
)
)
After receiving(
β
,
E
~
k
(
b
,
σ
,
r
j
)
) from the judge device, it computes
(3)
t
=
(
α
β
H
2
(
D
)
)
d
b
mod
⁡
n
b
and sends(
t
,
E
~
k
(
b
,
σ
,
r
j
)
) to the user.
(6)
Verifications
After receiving(
t
,
E
~
k
(
b
,
σ
,
r
j
)
), the user firstly decrypts the ciphertext by using the symmetric key k in order to obtain (
b
,
σ
,
r
j
). Secondly, she/he checks if his/her ID is embedded correctly by computing if σ
=
E
^
p
k
j
(
I
D
c
∥
r
j
) is true or not. Thirdly, she/he computes
(4)
s
=
a
b
t
mod
⁡
n
b and verifiess by checking if
(5)
s
e
b
H
1
2
(
m
∥
D
)
H
3
(
σ
∥
D
)
=
H
2
(
D
)
(
mod
⁡
n
b
)
is true or not. Finally, when all verifications are done, the user gets the e-cash tuples(
s
,
m
,
σ
,
D
) and stores (
x
1
,
x
2
,
r
1
,
r
2
) for further payment usages.Figure 1
Withdrawal protocol.


#### 3.2.3. Payment Protocol

When a user has to spend the e-cash, she/he performs the protocol as shown in Figure2. The steps of the protocol are described as follows.(1)
User→ Shop: (
s
,
m
,
σ
,
D
,
x
2
,
r
2
)
The user sends(
s
,
m
,
σ
,
D
,
x
2
,
r
2
) to the shop, where D contains the expiration date of the e-cash.
(2)
Shop→ User: r
s
The shop first checksD to verify if the e-cash is still within the expiration date or not. If not, it terminates the transaction. Otherwise, it continues to verify s
e
b
H
1
2
(
m
∥
D
)
H
3
(
σ
∥
D
)
=
H
2
(
D
)
(
mod
⁡
n
b
). If it is not valid, the protocol is aborted; or else, it selects a string r
s
′
∈
R
{
0,1
}
l
r
j and sets a challenge r
s
=
(
I
D
s
∥
r
s
′
), where I
D
s is the identity of the shop. Finally, it sends r
s to the user.
(3)
User→ Shop: (
s
′
,
r
u
)
After receivingr
s from the shop, the user randomly selects a r
u
∈
R
Z
q
* and computes a response to the challenge
(6)
s
′
=
(
r
1
-
u
x
1
)
mod
⁡
q
,
whereu
=
H
4
(
r
u
∥
r
s
). Then, the user sends (
s
′
,
r
u
) to the shop.
(4)
Verifications
After receiving(
s
′
,
r
u
) from the user, the shop verifies if w
1
=
y
1
H
4
(
r
u
∥
r
s
)
g
s
′
(
mod
⁡
p
) is true or not. If it is true, the shop will accept the e-cash. On the other hand, if it is not, the shop will reject it. Since it is an offline e-cash, the shop does not have to deposit it to the bank immediately. It can store the e-cash and deposit it later together with other received e-cash(s).Figure 2
Payment protocol.


#### 3.2.4. Deposit Protocol

As Figure3 shows, shops attach the deposit date to their e-cash(s) and deposit them to banks in this protocol. Banks perform double-spending checks when they receive these e-cash(s). If any e-cash is double-spent, the bank will revoke the anonymity of the e-cash owner with the help of the judge. The steps are described in detail as follows.(1)
Shop→ Bank: (
s
,
m
,
σ
,
D
,
d
,
r
4
,
s
′
,
r
u
,
r
s
)
The shop computesr
4
=
r
2
-
x
2
H
5
(
d
), where d is the deposit date, and sends (
s
,
m
,
σ
,
D
,
d
,
r
4
,
s
′
,
r
u
,
r
s
) to the bank.
(2)
Verifications
Firstly, the bank checks the correctness of expiration dateD and deposit date d, respectively, and also checks if
(7)
w
2
=
y
2
H
5
(
d
)
g
2
r
4
mod
⁡
p
,
w
1
=
y
1
H
4
(
r
u
∥
r
s
)
g
2
s
′
mod
⁡
p
are true or not. Secondly, the bank verifies ifs
e
b
H
1
2
(
m
∥
D
)
H
3
(
σ
∥
D
)
=
H
2
(
D
)
(
mod
⁡
n
b
) and checks the uniqueness of (
s
,
m
,
σ
,
D
). Finally, if all of the above facts are verified successfully, the bank will accept and store the e-cash in its database and record H
1
(
m
∥
D
) inexchange list. Otherwise, it will reject this transaction and trace the owner of the e-cash.Figure 3
Deposit protocol.


#### 3.2.5. E-Cash Renewal Protocol

In order to reduce the unlimited growth database problem of the bank, we have expiration date and renewal protocol in our scheme to achieve it, as shown in Figure4. When an unused e-cash is expired, the user has to exchange it for another e-cash with a new expiration date from the bank.(1)
User→ Bank: (
s
,
ρ
,
σ
,
D
)
The user recallsm
=
(
y
1
,
w
1
,
y
2
,
w
2
,
x
2
,
r
3
) and prepares
(8)
ρ
=
H
1
(
m
∥
D
)
and sends it together with the unused(
s
,
σ
,
D
) to the bank.
(2)
Verifications
Firstly, the bank checks the correctness of expiration dateD and makes sure ρ does not exist in theexchange list. Secondly, the bank verifies if s
e
b
H
1
(
ρ
)
H
3
(
σ
∥
D
)
≡
H
2
(
D
)
(
mod
⁡
n
b
). Finally, if all of the above facts are verified successfully, the bank will accept to exchange the e-cash. It will send a new expiration date D
′ and store ρ in theexchange list. Otherwise, it will reject the exchange request.
(3)
User→ Bank: (
α
^
,
ϵ
)
The user computes(9)
α
^
=
[
a
e
b
H
1
2
(
m
′
∥
D
′
)
]
-
1
mod
⁡
n
b
,
wherem
′
=
(
y
1
,
w
1
,
y
2
,
w
2
,
x
2
,
r
3
′
), r
3
′ is a random, and D
′ is the new expiration date issued by the bank. The user sends (
α
^
,
ϵ
,
I
D
c
) to the bank. Then the bank repeats the withdrawal protocol in Section 3.2.2 from Step 2 with the user.Figure 4
E-Cash renewal protocol.


#### 3.2.6. Double-Spending Checking and Anonymity Control

In our scheme, the identity of the users is anonymous in general except when the users violate any security rules and, therefore, their identities will be revealed.(1)
Double-Spending Checking
When an e-cash is being doubly spent, there must be two e-cash(s) with the same record prefixed by(
s
,
y
1
,
w
1
,
y
2
,
w
2
,
r
3
,
σ
,
D
) stored in the database of the bank. Therefore, the bank is able to detect any double-spent e-cash easily by checking the above parameters. For instance, the bank has received two e-cash(s),
(10)
(
s
,
y
1
,
w
1
,
y
2
,
w
2
,
x
2
,
r
3
,
r
4
,
σ
,
D
,
d
,
s
′
,
r
u
,
r
s
)
,
(
s
,
y
1
,
w
1
,
y
2
,
w
2
,
x
2
,
r
3
,
r
4
^
,
σ
,
D
,
d
^
,
s
′
^
,
r
^
u
,
r
^
s
)
.
Thus, the bank can obtain two equations as follows:(11)
s
′
≡
r
1
-
H
4
(
r
u
∥
r
s
)
x
1
(
mod
⁡
q
)
,
s
′
^
≡
r
1
-
H
4
(
r
^
u
∥
r
^
s
)
x
1
(
mod
⁡
q
)
.
The bank can derive(
x
1
,
r
1
) from the above equations and send (
s
,
y
1
,
w
1
,
y
2
,
w
2
,
x
2
,
r
3
,
σ
,
D
) and (
x
1
,
r
1
) to the judge to trace the owner of the e-cash.
(2)
Revocation
The judge can trace any user who doubly spends e-cash(s) or violates any transaction regulations. When the judge receives(
s
,
y
1
,
w
1
,
y
2
,
w
2
,
x
2
,
r
3
,
σ
,
D
) and (
x
1
,
r
1
) from the bank, it checks the following equations:
(12)
s
e
b
H
1
2
(
m
∥
D
)
H
3
(
σ
∥
D
)
≡
?
H
2
(
D
)
(
mod
⁡
n
b
)
,
y
1
≡
?
g
1
x
1
(
mod
⁡
p
)
,

w
1
≡
?
g
1
r
1
(
mod
⁡
p
)
.
If all of the above equalities are true, the judge will decryptσ and return the extracted I
D
c to the bank.


## 3.1. Outline of the Proposed Scheme

Here we are going to briefly describe the procedures of our scheme. The proposed scheme contains four protocols,withdrawal protocol, payment protocol, deposit protocol, ande-cash renewal protocol. A user withdraws an e-cash with an expiration date attached to it from the bank. A trusted computing platform (i.e.,judge device) [31, 32], as stated in the proposed scheme, is installed in the bank to hold the identity information of all users and it will further help trace users when it is needed. It is impossible for anyone except the judge to obtain any information embedded in the device [33]. Nowadays, judge device can be implemented by the technique of Trusted Platform Module (TPM) [32, 34] in practice.Before an e-cash is deposited, the depositor attaches the deposit date on the e-cash and sends it to the bank during the deposit stage. When the bank receives an e-cash, it will perform double-spending checking to verify whether the e-cash is doubly spent or not. The bank can derive secret parameters of the user who does double-spending and let the judge revoke the anonymity of the user. Besides, when an unused e-cash is expired, a user will be able to exchange it for a new one with a new expiration date. In our scheme, for the efficiency concerns, some of the unused parameters of users can remain unchanged while exchanging for a new valid e-cash. In the following sections, we will describe our scheme in detail.


## 3.2. The Proposed Scheme

Firstly, we define some notations as follows.(1)
H
1
,
H
2
,
H
3: three one-way hash functions, H
1
,
H
2
,
H
3
:
{
0,1
}
*
→
{
0,1
}
n.
(2)
H
4
,
H
5: two one-way hash functions, H
4
,
H
5 : {
0,1
}
*
→
{
0,1
}
q.
(3)
E
~
x, D
~
x: a secure symmetric cryptosystem. Plaintext is both encrypted and decrypted with a symmetric key x.
(4)
E
^
p
k
,
D
^
s
k: a secure asymmetric cryptosystem. Plaintext is encrypted with a public key p
k and decrypted with the corresponding private key s
k.
(5)
(
p
k
j
,
s
k
j
): the public-private key pair of the judge.
(6)
(
e
b
,
d
b
): the public-private key pair of bank.
(7)
D
a
t
e: expiration date. It represents an effective spending date of a withdrawn e-cash. Any e-cash withdrawn in the same period will have the same expiration date, and vice versa.
(8)
I
D
c: the identity of user C.
(9)
l
k, l
r: the security parameters.
(10)
A judge device: a tamper-resistant device which is issued by the judge. It is installed into the system of the bank. It is impossible to intercept or modify any information stored in the device.


### 3.2.1. Initialization

Initially, the bank randomly chooses two distinct large primes(
p
b
,
q
b
) and computes RSA parameters n
b
=
p
b
q
b. It selects an integer e
b at random such that GCD(
ϕ
(
n
b
)
,
e
b
)
=
1, where ϕ
(
n
b
)
=
(
p
b
-
1
)
(
q
b
-
1
) and 1
<
e
b
<
ϕ
(
n
b
). Then, it finds a d
b such that e
b
d
b
≡
1
(mod ϕ
(
n
b
)
). Secondly, it also chooses two other large primes p and q and two generators g
1 and g
2 of order q in Z
p
*. Then, the bank publishes (
n
b
,
e
b
,
p
,
q
,
g
1
,
g
2
,
p
k
j
,
H
1
,
H
2
,
H
3
,
H
4
,
H
5
,
E
~
,
D
~
,
E
^
,
D
^
). Meanwhile, the judge embeds (
n
b
,
e
b
,
p
,
q
,
g
1
,
g
2
,
p
k
j
,
s
k
j
,
H
1
,
H
2
,
H
3
,
H
4
,
H
5
,
E
~
,
D
~
,
E
^
,
D
^
) into a judge device and issues it to the bank.


### 3.2.2. Withdrawal Protocol

Users run the withdrawal protocol with banks to get an e-cash, as shown in Figure1, yet banks have to obtain information of users’ identity, such as I
D
c or account numbers, before the withdrawal protocol is proceeded. Therefore, users should perform an authentication with banks beforehand. Users can execute the withdrawal protocol by any devices that have the ability to compute and connect to the network. For instance, users can use mobile phones or computers to perform the withdrawal protocol and store the withdrawn e-cash. The detailed steps of the protocol are as follows.(1)
Bank→ User: D
Firstly, the user prepares parameters for withdrawing an e-cash. The user chooses integersa, x
1, x
2, r
1, r
2, and r
3 in random, where a
∈
R
Z
n
b
* and x
1, x
2, r
1, r
2, r
3
∈
R
{
0,1
,
…
,
q
-
1
} and selects a string k
∈
R
{
0,1
}
l
k randomly. The user then computes (
y
1
,
w
1
,
y
2
,
w
2
), where y
i
=
g
i
x
i
mod
⁡
p and w
i
=
g
i
r
i
mod
⁡
p for i
=
{
1,2
}. Secondly, the bank computes parameters for expiration date. It randomly chooses a r in Z
n
*, prepares D
=
Date
∥
r for some expiration date D
a
t
e. The bank will send D to the user when she/he requests to withdraw an e-cash.
(2)
User→ Bank: (
α
,
ϵ
)
After receivingD, the user prepares ϵ
=
E
^
p
k
j
(
k
∥
ID
c
) and
(1)
α
=
[
a
e
b
H
1
2
(
m
∥
D
)
]
-
1
mod
⁡
n
b
,
wherem
=
(
y
1
∥
w
1
∥
y
2
∥
w
2
∥
r
3
). Finally, the user sends (
α
,
ϵ
) to the bank.
(3)
Bank→ Judge device: (
ϵ
,
μ
,
D
)
The bank setsμ
=
I
D
c, where I
D
c is the identity of user C, and inputs it together with ϵ and D to the judge device.
(4)
Judge device→ Bank: (
β
,
E
~
k
(
b
,
σ
,
r
j
)
)
The judge device decryptsϵ and checks if μ
=
I
D
c. If not, it returns “ID error” to the bank; or else, it picks a random integer b
∈
R
Z
n
b
* and a string r
j
∈
R
{
0,1
}
l
r
j randomly. Then it computes σ
=
E
^
p
k
j
(
μ
∥
r
j
) and
(2)
β
=
[
b
e
b
H
3
(
σ
∥
D
)
]
-
1
mod
⁡
n
b
.
Finally, it encrypts(
b
,
σ
,
r
j
) by using the symmetric key k and outputs it together with β to the bank.
(5)
Bank→ User: (
t
,
E
~
k
(
b
,
σ
,
r
j
)
)
After receiving(
β
,
E
~
k
(
b
,
σ
,
r
j
)
) from the judge device, it computes
(3)
t
=
(
α
β
H
2
(
D
)
)
d
b
mod
⁡
n
b
and sends(
t
,
E
~
k
(
b
,
σ
,
r
j
)
) to the user.
(6)
Verifications
After receiving(
t
,
E
~
k
(
b
,
σ
,
r
j
)
), the user firstly decrypts the ciphertext by using the symmetric key k in order to obtain (
b
,
σ
,
r
j
). Secondly, she/he checks if his/her ID is embedded correctly by computing if σ
=
E
^
p
k
j
(
I
D
c
∥
r
j
) is true or not. Thirdly, she/he computes
(4)
s
=
a
b
t
mod
⁡
n
b and verifiess by checking if
(5)
s
e
b
H
1
2
(
m
∥
D
)
H
3
(
σ
∥
D
)
=
H
2
(
D
)
(
mod
⁡
n
b
)
is true or not. Finally, when all verifications are done, the user gets the e-cash tuples(
s
,
m
,
σ
,
D
) and stores (
x
1
,
x
2
,
r
1
,
r
2
) for further payment usages.Figure 1
Withdrawal protocol.


### 3.2.3. Payment Protocol

When a user has to spend the e-cash, she/he performs the protocol as shown in Figure2. The steps of the protocol are described as follows.(1)
User→ Shop: (
s
,
m
,
σ
,
D
,
x
2
,
r
2
)
The user sends(
s
,
m
,
σ
,
D
,
x
2
,
r
2
) to the shop, where D contains the expiration date of the e-cash.
(2)
Shop→ User: r
s
The shop first checksD to verify if the e-cash is still within the expiration date or not. If not, it terminates the transaction. Otherwise, it continues to verify s
e
b
H
1
2
(
m
∥
D
)
H
3
(
σ
∥
D
)
=
H
2
(
D
)
(
mod
⁡
n
b
). If it is not valid, the protocol is aborted; or else, it selects a string r
s
′
∈
R
{
0,1
}
l
r
j and sets a challenge r
s
=
(
I
D
s
∥
r
s
′
), where I
D
s is the identity of the shop. Finally, it sends r
s to the user.
(3)
User→ Shop: (
s
′
,
r
u
)
After receivingr
s from the shop, the user randomly selects a r
u
∈
R
Z
q
* and computes a response to the challenge
(6)
s
′
=
(
r
1
-
u
x
1
)
mod
⁡
q
,
whereu
=
H
4
(
r
u
∥
r
s
). Then, the user sends (
s
′
,
r
u
) to the shop.
(4)
Verifications
After receiving(
s
′
,
r
u
) from the user, the shop verifies if w
1
=
y
1
H
4
(
r
u
∥
r
s
)
g
s
′
(
mod
⁡
p
) is true or not. If it is true, the shop will accept the e-cash. On the other hand, if it is not, the shop will reject it. Since it is an offline e-cash, the shop does not have to deposit it to the bank immediately. It can store the e-cash and deposit it later together with other received e-cash(s).Figure 2
Payment protocol.


### 3.2.4. Deposit Protocol

As Figure3 shows, shops attach the deposit date to their e-cash(s) and deposit them to banks in this protocol. Banks perform double-spending checks when they receive these e-cash(s). If any e-cash is double-spent, the bank will revoke the anonymity of the e-cash owner with the help of the judge. The steps are described in detail as follows.(1)
Shop→ Bank: (
s
,
m
,
σ
,
D
,
d
,
r
4
,
s
′
,
r
u
,
r
s
)
The shop computesr
4
=
r
2
-
x
2
H
5
(
d
), where d is the deposit date, and sends (
s
,
m
,
σ
,
D
,
d
,
r
4
,
s
′
,
r
u
,
r
s
) to the bank.
(2)
Verifications
Firstly, the bank checks the correctness of expiration dateD and deposit date d, respectively, and also checks if
(7)
w
2
=
y
2
H
5
(
d
)
g
2
r
4
mod
⁡
p
,
w
1
=
y
1
H
4
(
r
u
∥
r
s
)
g
2
s
′
mod
⁡
p
are true or not. Secondly, the bank verifies ifs
e
b
H
1
2
(
m
∥
D
)
H
3
(
σ
∥
D
)
=
H
2
(
D
)
(
mod
⁡
n
b
) and checks the uniqueness of (
s
,
m
,
σ
,
D
). Finally, if all of the above facts are verified successfully, the bank will accept and store the e-cash in its database and record H
1
(
m
∥
D
) inexchange list. Otherwise, it will reject this transaction and trace the owner of the e-cash.Figure 3
Deposit protocol.


### 3.2.5. E-Cash Renewal Protocol

In order to reduce the unlimited growth database problem of the bank, we have expiration date and renewal protocol in our scheme to achieve it, as shown in Figure4. When an unused e-cash is expired, the user has to exchange it for another e-cash with a new expiration date from the bank.(1)
User→ Bank: (
s
,
ρ
,
σ
,
D
)
The user recallsm
=
(
y
1
,
w
1
,
y
2
,
w
2
,
x
2
,
r
3
) and prepares
(8)
ρ
=
H
1
(
m
∥
D
)
and sends it together with the unused(
s
,
σ
,
D
) to the bank.
(2)
Verifications
Firstly, the bank checks the correctness of expiration dateD and makes sure ρ does not exist in theexchange list. Secondly, the bank verifies if s
e
b
H
1
(
ρ
)
H
3
(
σ
∥
D
)
≡
H
2
(
D
)
(
mod
⁡
n
b
). Finally, if all of the above facts are verified successfully, the bank will accept to exchange the e-cash. It will send a new expiration date D
′ and store ρ in theexchange list. Otherwise, it will reject the exchange request.
(3)
User→ Bank: (
α
^
,
ϵ
)
The user computes(9)
α
^
=
[
a
e
b
H
1
2
(
m
′
∥
D
′
)
]
-
1
mod
⁡
n
b
,
wherem
′
=
(
y
1
,
w
1
,
y
2
,
w
2
,
x
2
,
r
3
′
), r
3
′ is a random, and D
′ is the new expiration date issued by the bank. The user sends (
α
^
,
ϵ
,
I
D
c
) to the bank. Then the bank repeats the withdrawal protocol in Section 3.2.2 from Step 2 with the user.Figure 4
E-Cash renewal protocol.


### 3.2.6. Double-Spending Checking and Anonymity Control

In our scheme, the identity of the users is anonymous in general except when the users violate any security rules and, therefore, their identities will be revealed.(1)
Double-Spending Checking
When an e-cash is being doubly spent, there must be two e-cash(s) with the same record prefixed by(
s
,
y
1
,
w
1
,
y
2
,
w
2
,
r
3
,
σ
,
D
) stored in the database of the bank. Therefore, the bank is able to detect any double-spent e-cash easily by checking the above parameters. For instance, the bank has received two e-cash(s),
(10)
(
s
,
y
1
,
w
1
,
y
2
,
w
2
,
x
2
,
r
3
,
r
4
,
σ
,
D
,
d
,
s
′
,
r
u
,
r
s
)
,
(
s
,
y
1
,
w
1
,
y
2
,
w
2
,
x
2
,
r
3
,
r
4
^
,
σ
,
D
,
d
^
,
s
′
^
,
r
^
u
,
r
^
s
)
.
Thus, the bank can obtain two equations as follows:(11)
s
′
≡
r
1
-
H
4
(
r
u
∥
r
s
)
x
1
(
mod
⁡
q
)
,
s
′
^
≡
r
1
-
H
4
(
r
^
u
∥
r
^
s
)
x
1
(
mod
⁡
q
)
.
The bank can derive(
x
1
,
r
1
) from the above equations and send (
s
,
y
1
,
w
1
,
y
2
,
w
2
,
x
2
,
r
3
,
σ
,
D
) and (
x
1
,
r
1
) to the judge to trace the owner of the e-cash.
(2)
Revocation
The judge can trace any user who doubly spends e-cash(s) or violates any transaction regulations. When the judge receives(
s
,
y
1
,
w
1
,
y
2
,
w
2
,
x
2
,
r
3
,
σ
,
D
) and (
x
1
,
r
1
) from the bank, it checks the following equations:
(12)
s
e
b
H
1
2
(
m
∥
D
)
H
3
(
σ
∥
D
)
≡
?
H
2
(
D
)
(
mod
⁡
n
b
)
,
y
1
≡
?
g
1
x
1
(
mod
⁡
p
)
,

w
1
≡
?
g
1
r
1
(
mod
⁡
p
)
.
If all of the above equalities are true, the judge will decryptσ and return the extracted I
D
c to the bank.


## 3.2.1. Initialization

Initially, the bank randomly chooses two distinct large primes(
p
b
,
q
b
) and computes RSA parameters n
b
=
p
b
q
b. It selects an integer e
b at random such that GCD(
ϕ
(
n
b
)
,
e
b
)
=
1, where ϕ
(
n
b
)
=
(
p
b
-
1
)
(
q
b
-
1
) and 1
<
e
b
<
ϕ
(
n
b
). Then, it finds a d
b such that e
b
d
b
≡
1
(mod ϕ
(
n
b
)
). Secondly, it also chooses two other large primes p and q and two generators g
1 and g
2 of order q in Z
p
*. Then, the bank publishes (
n
b
,
e
b
,
p
,
q
,
g
1
,
g
2
,
p
k
j
,
H
1
,
H
2
,
H
3
,
H
4
,
H
5
,
E
~
,
D
~
,
E
^
,
D
^
). Meanwhile, the judge embeds (
n
b
,
e
b
,
p
,
q
,
g
1
,
g
2
,
p
k
j
,
s
k
j
,
H
1
,
H
2
,
H
3
,
H
4
,
H
5
,
E
~
,
D
~
,
E
^
,
D
^
) into a judge device and issues it to the bank.


## 3.2.2. Withdrawal Protocol

Users run the withdrawal protocol with banks to get an e-cash, as shown in Figure1, yet banks have to obtain information of users’ identity, such as I
D
c or account numbers, before the withdrawal protocol is proceeded. Therefore, users should perform an authentication with banks beforehand. Users can execute the withdrawal protocol by any devices that have the ability to compute and connect to the network. For instance, users can use mobile phones or computers to perform the withdrawal protocol and store the withdrawn e-cash. The detailed steps of the protocol are as follows.(1)
Bank→ User: D
Firstly, the user prepares parameters for withdrawing an e-cash. The user chooses integersa, x
1, x
2, r
1, r
2, and r
3 in random, where a
∈
R
Z
n
b
* and x
1, x
2, r
1, r
2, r
3
∈
R
{
0,1
,
…
,
q
-
1
} and selects a string k
∈
R
{
0,1
}
l
k randomly. The user then computes (
y
1
,
w
1
,
y
2
,
w
2
), where y
i
=
g
i
x
i
mod
⁡
p and w
i
=
g
i
r
i
mod
⁡
p for i
=
{
1,2
}. Secondly, the bank computes parameters for expiration date. It randomly chooses a r in Z
n
*, prepares D
=
Date
∥
r for some expiration date D
a
t
e. The bank will send D to the user when she/he requests to withdraw an e-cash.
(2)
User→ Bank: (
α
,
ϵ
)
After receivingD, the user prepares ϵ
=
E
^
p
k
j
(
k
∥
ID
c
) and
(1)
α
=
[
a
e
b
H
1
2
(
m
∥
D
)
]
-
1
mod
⁡
n
b
,
wherem
=
(
y
1
∥
w
1
∥
y
2
∥
w
2
∥
r
3
). Finally, the user sends (
α
,
ϵ
) to the bank.
(3)
Bank→ Judge device: (
ϵ
,
μ
,
D
)
The bank setsμ
=
I
D
c, where I
D
c is the identity of user C, and inputs it together with ϵ and D to the judge device.
(4)
Judge device→ Bank: (
β
,
E
~
k
(
b
,
σ
,
r
j
)
)
The judge device decryptsϵ and checks if μ
=
I
D
c. If not, it returns “ID error” to the bank; or else, it picks a random integer b
∈
R
Z
n
b
* and a string r
j
∈
R
{
0,1
}
l
r
j randomly. Then it computes σ
=
E
^
p
k
j
(
μ
∥
r
j
) and
(2)
β
=
[
b
e
b
H
3
(
σ
∥
D
)
]
-
1
mod
⁡
n
b
.
Finally, it encrypts(
b
,
σ
,
r
j
) by using the symmetric key k and outputs it together with β to the bank.
(5)
Bank→ User: (
t
,
E
~
k
(
b
,
σ
,
r
j
)
)
After receiving(
β
,
E
~
k
(
b
,
σ
,
r
j
)
) from the judge device, it computes
(3)
t
=
(
α
β
H
2
(
D
)
)
d
b
mod
⁡
n
b
and sends(
t
,
E
~
k
(
b
,
σ
,
r
j
)
) to the user.
(6)
Verifications
After receiving(
t
,
E
~
k
(
b
,
σ
,
r
j
)
), the user firstly decrypts the ciphertext by using the symmetric key k in order to obtain (
b
,
σ
,
r
j
). Secondly, she/he checks if his/her ID is embedded correctly by computing if σ
=
E
^
p
k
j
(
I
D
c
∥
r
j
) is true or not. Thirdly, she/he computes
(4)
s
=
a
b
t
mod
⁡
n
b and verifiess by checking if
(5)
s
e
b
H
1
2
(
m
∥
D
)
H
3
(
σ
∥
D
)
=
H
2
(
D
)
(
mod
⁡
n
b
)
is true or not. Finally, when all verifications are done, the user gets the e-cash tuples(
s
,
m
,
σ
,
D
) and stores (
x
1
,
x
2
,
r
1
,
r
2
) for further payment usages.Figure 1
Withdrawal protocol.


## 3.2.3. Payment Protocol

When a user has to spend the e-cash, she/he performs the protocol as shown in Figure2. The steps of the protocol are described as follows.(1)
User→ Shop: (
s
,
m
,
σ
,
D
,
x
2
,
r
2
)
The user sends(
s
,
m
,
σ
,
D
,
x
2
,
r
2
) to the shop, where D contains the expiration date of the e-cash.
(2)
Shop→ User: r
s
The shop first checksD to verify if the e-cash is still within the expiration date or not. If not, it terminates the transaction. Otherwise, it continues to verify s
e
b
H
1
2
(
m
∥
D
)
H
3
(
σ
∥
D
)
=
H
2
(
D
)
(
mod
⁡
n
b
). If it is not valid, the protocol is aborted; or else, it selects a string r
s
′
∈
R
{
0,1
}
l
r
j and sets a challenge r
s
=
(
I
D
s
∥
r
s
′
), where I
D
s is the identity of the shop. Finally, it sends r
s to the user.
(3)
User→ Shop: (
s
′
,
r
u
)
After receivingr
s from the shop, the user randomly selects a r
u
∈
R
Z
q
* and computes a response to the challenge
(6)
s
′
=
(
r
1
-
u
x
1
)
mod
⁡
q
,
whereu
=
H
4
(
r
u
∥
r
s
). Then, the user sends (
s
′
,
r
u
) to the shop.
(4)
Verifications
After receiving(
s
′
,
r
u
) from the user, the shop verifies if w
1
=
y
1
H
4
(
r
u
∥
r
s
)
g
s
′
(
mod
⁡
p
) is true or not. If it is true, the shop will accept the e-cash. On the other hand, if it is not, the shop will reject it. Since it is an offline e-cash, the shop does not have to deposit it to the bank immediately. It can store the e-cash and deposit it later together with other received e-cash(s).Figure 2
Payment protocol.


## 3.2.4. Deposit Protocol

As Figure3 shows, shops attach the deposit date to their e-cash(s) and deposit them to banks in this protocol. Banks perform double-spending checks when they receive these e-cash(s). If any e-cash is double-spent, the bank will revoke the anonymity of the e-cash owner with the help of the judge. The steps are described in detail as follows.(1)
Shop→ Bank: (
s
,
m
,
σ
,
D
,
d
,
r
4
,
s
′
,
r
u
,
r
s
)
The shop computesr
4
=
r
2
-
x
2
H
5
(
d
), where d is the deposit date, and sends (
s
,
m
,
σ
,
D
,
d
,
r
4
,
s
′
,
r
u
,
r
s
) to the bank.
(2)
Verifications
Firstly, the bank checks the correctness of expiration dateD and deposit date d, respectively, and also checks if
(7)
w
2
=
y
2
H
5
(
d
)
g
2
r
4
mod
⁡
p
,
w
1
=
y
1
H
4
(
r
u
∥
r
s
)
g
2
s
′
mod
⁡
p
are true or not. Secondly, the bank verifies ifs
e
b
H
1
2
(
m
∥
D
)
H
3
(
σ
∥
D
)
=
H
2
(
D
)
(
mod
⁡
n
b
) and checks the uniqueness of (
s
,
m
,
σ
,
D
). Finally, if all of the above facts are verified successfully, the bank will accept and store the e-cash in its database and record H
1
(
m
∥
D
) inexchange list. Otherwise, it will reject this transaction and trace the owner of the e-cash.Figure 3
Deposit protocol.


## 3.2.5. E-Cash Renewal Protocol

In order to reduce the unlimited growth database problem of the bank, we have expiration date and renewal protocol in our scheme to achieve it, as shown in Figure4. When an unused e-cash is expired, the user has to exchange it for another e-cash with a new expiration date from the bank.(1)
User→ Bank: (
s
,
ρ
,
σ
,
D
)
The user recallsm
=
(
y
1
,
w
1
,
y
2
,
w
2
,
x
2
,
r
3
) and prepares
(8)
ρ
=
H
1
(
m
∥
D
)
and sends it together with the unused(
s
,
σ
,
D
) to the bank.
(2)
Verifications
Firstly, the bank checks the correctness of expiration dateD and makes sure ρ does not exist in theexchange list. Secondly, the bank verifies if s
e
b
H
1
(
ρ
)
H
3
(
σ
∥
D
)
≡
H
2
(
D
)
(
mod
⁡
n
b
). Finally, if all of the above facts are verified successfully, the bank will accept to exchange the e-cash. It will send a new expiration date D
′ and store ρ in theexchange list. Otherwise, it will reject the exchange request.
(3)
User→ Bank: (
α
^
,
ϵ
)
The user computes(9)
α
^
=
[
a
e
b
H
1
2
(
m
′
∥
D
′
)
]
-
1
mod
⁡
n
b
,
wherem
′
=
(
y
1
,
w
1
,
y
2
,
w
2
,
x
2
,
r
3
′
), r
3
′ is a random, and D
′ is the new expiration date issued by the bank. The user sends (
α
^
,
ϵ
,
I
D
c
) to the bank. Then the bank repeats the withdrawal protocol in Section 3.2.2 from Step 2 with the user.Figure 4
E-Cash renewal protocol.


## 3.2.6. Double-Spending Checking and Anonymity Control

In our scheme, the identity of the users is anonymous in general except when the users violate any security rules and, therefore, their identities will be revealed.(1)
Double-Spending Checking
When an e-cash is being doubly spent, there must be two e-cash(s) with the same record prefixed by(
s
,
y
1
,
w
1
,
y
2
,
w
2
,
r
3
,
σ
,
D
) stored in the database of the bank. Therefore, the bank is able to detect any double-spent e-cash easily by checking the above parameters. For instance, the bank has received two e-cash(s),
(10)
(
s
,
y
1
,
w
1
,
y
2
,
w
2
,
x
2
,
r
3
,
r
4
,
σ
,
D
,
d
,
s
′
,
r
u
,
r
s
)
,
(
s
,
y
1
,
w
1
,
y
2
,
w
2
,
x
2
,
r
3
,
r
4
^
,
σ
,
D
,
d
^
,
s
′
^
,
r
^
u
,
r
^
s
)
.
Thus, the bank can obtain two equations as follows:(11)
s
′
≡
r
1
-
H
4
(
r
u
∥
r
s
)
x
1
(
mod
⁡
q
)
,
s
′
^
≡
r
1
-
H
4
(
r
^
u
∥
r
^
s
)
x
1
(
mod
⁡
q
)
.
The bank can derive(
x
1
,
r
1
) from the above equations and send (
s
,
y
1
,
w
1
,
y
2
,
w
2
,
x
2
,
r
3
,
σ
,
D
) and (
x
1
,
r
1
) to the judge to trace the owner of the e-cash.
(2)
Revocation
The judge can trace any user who doubly spends e-cash(s) or violates any transaction regulations. When the judge receives(
s
,
y
1
,
w
1
,
y
2
,
w
2
,
x
2
,
r
3
,
σ
,
D
) and (
x
1
,
r
1
) from the bank, it checks the following equations:
(12)
s
e
b
H
1
2
(
m
∥
D
)
H
3
(
σ
∥
D
)
≡
?
H
2
(
D
)
(
mod
⁡
n
b
)
,
y
1
≡
?
g
1
x
1
(
mod
⁡
p
)
,

w
1
≡
?
g
1
r
1
(
mod
⁡
p
)
.
If all of the above equalities are true, the judge will decryptσ and return the extracted I
D
c to the bank.


## 4. Security Proofs

In this section, we provide security definitions and formal proofs of the following security features: unlinkability, unforgeability, traceability, and no-swindling for our proposed date attachable offline electronic cash scheme (D
A
O
E
C
S).


### 4.1. E-Cash Unlinkability

Based on the definition of unlinkability introduced by Abe and Okamoto [35] and Juels et al. [36], we formally define the unlinkability property of D
A
O
E
C
S.Definition 1 (The Linkage Game).
LetU
0, U
1, and J be two honest users and the judge that follows D
A
O
E
C
S, respectively. Let B be the bank that participates the following game with U
0, U
1, and J. The game environment is shown in Figure 5.Figure 5
The game environment of linkage game.Step 1.
According toD
A
O
E
C
S, B generates the bank’s public key (
e
b
,
n
b
), the bank’s private key (
d
b
,
p
b
,
q
b
), system parameters (
p
,
q
,
g
1
,
g
2
), the expiration date D, and the five public one-way hash functions H
1, H
2,  H
3, H
4, and H
5. J generates the judge’s public-private key pair (
p
k
j
,
s
k
j
).Step 2.
B generates x
1
i, x
2
i, r
1
i, r
2
i, r
3
i in random, where x
1, x
2, r
1, r
2, r
3
∈
R
{
0,1
,
…
,
q
-
1
}, and computes (
y
k
i
,
w
k
i
) for k
=
{
1,2
} and i
=
{
0,1
}, where y
k
i
=
g
k
x
k
mod
⁡
p and w
k
i
=
g
k
r
k
mod
⁡
p.Step 3.
We choose a bitb
^
∈
{
0,1
} randomly and place (
y
1
b
^
,
w
1
b
^
,
y
2
b
^
,
w
2
b
^
) and (
y
1
1
-
b
^
,
w
1
1
-
b
^
,
y
2
1
-
b
^
,
w
2
1
-
b
^
) on the private input tapes of U
0 and U
1, respectively, where b
^ is not disclosed to B.Step 4.
B performs the withdrawal protocol of D
A
O
E
C
S with U
0 and U
1, respectively.Step 5.
IfU
0 and U
1 output two e-cash(s) (
s
b
^
,
m
b
^
,
σ
b
^
,
D
b
^
) and (
s
1
-
b
^
,
m
1
-
b
^
,
σ
1
-
b
^
,
D
1
-
b
^
), where m
i
=
(
y
1
i
,
w
1
i
,
y
2
i
,
w
2
i
,
r
3
i
), on their private tapes, respectively, we give the two e-cash(s) in a random order to B; otherwise, ⊥ is given to B.Step 6.
B outputs b
^
′
∈
{
0,1
} as the guess of b
^. The bank B wins the game if b
^
′
=
b
^ and J has not revoked the anonymity of (
s
b
^
,
m
b
^
,
σ
b
^
,
D
b
^
) and (
s
1
-
b
^
,
m
1
-
b
^
,
σ
1
-
b
^
,
D
1
-
b
^
) to B. We define the advantage of B as
(13)
Ad
v
D
A
O
E
C
S
Linkability
(
B
)
=
|
2
Pr
[
b
^
′
=
b
^
]
-
1
|
,
where Pr
[
b
^
′
=
b
^
] denotes the probability of b
^
′
=
b
^.Definition 2 (Unlinkability).
AD
A
O
E
C
S satisfies the unlinkability property if and only if the advantage Ad
v
D
A
O
E
C
S
Linkability
(
B
) defined in Definition 1 is negligible.Theorem 3.
AD
A
O
E
C
S satisfies the unlinkability property of Definition 2 if the adopted cryptosystems are semantically secure.Proof.
IfB is given ⊥ in the Step 5 of the game, it will determine b
^ with probability 1
/
2, which is exactly the same as a random guess of b
^.
Here, we assume thatB gets two e-cash (
s
0
,
m
0
,
σ
0
,
D
0
) and (
s
1
,
m
1
,
σ
1
,
D
1
). Let (
α
i
,
β
i
,
t
i
,
ϵ
i
,
E
~
k
i
(
b
i
,
σ
i
,
r
j
i
)
), i
∈
{
0,1
}, be the view of data exchanged between U
i and B in the withdrawal protocol (Section 3.2.2) and let (
x
2
i
,
r
2
i
,
r
4
i
,
r
u
i
,
r
s
i
,
s
i
′
,
d
i
) be the view of data exchanged when B performs the payment protocol (Section 3.2.3) and the deposit protocol (Section 3.2.4) by using (
s
i
,
m
i
,
σ
i
,
D
i
), where i
∈
{
0,1
}.
For(
s
,
m
,
σ
,
D
,
x
2
,
r
2
,
r
4
,
r
u
,
r
s
,
s
′
,
d
)
∈
(14)
{
(
s
0
,
m
0
,
σ
0
,
D
0
,
x
2
0
,
r
2
0
,
r
4
0
,
r
u
0
,
r
s
0
,
s
0
′
,
d
0
)
,
h
(
s
1
,
m
1
,
σ
1
,
D
1
,
x
2
1
,
r
2
1
,
r
4
1
,
r
u
1
,
r
s
1
,
s
1
′
,
d
1
)
}
and (
α
i
,
β
i
,
t
i
,
ϵ
i
,
E
~
k
i
(
b
i
,
σ
i
,
r
j
i
)
), i
∈
{
0,1
}, there always exists a pair (
a
i
′
,
b
i
′
) such that
(15)
a
i
′
=
[
α
i
H
1
2
(
m
∥
D
)
]
-
d
b
mod
⁡
n
b
(
via
(
1
)
)
,
b
i
′
=
[
β
i
H
3
(
σ
∥
D
)
]
-
d
b
mod
⁡
n
b
(
via
(
2
)
)
.
And from (3), t
i
≡
(
α
i
β
i
H
2
(
D
)
)
d
b
(
mod
⁡
n
b
), (4) always holds as
(16)
s
≡
(
a
i
′
b
i
′
t
i
)
≡
[
(
H
1
2
(
m
∥
D
)
H
3
(
σ
∥
D
)
)
-
1
H
2
(
D
)
]
d
b
(
mod
⁡
n
b
)
.
Besides, E
^
p
k
j and E
~
k
i are semantically secure encryption functions. B cannot learn any information from ϵ
i and E
~
k
i
(
b
i
,
σ
i
,
r
j
i
).
From the above, given any(
s
,
m
,
σ
,
D
)
∈
{
(
s
0
,
m
0
,
σ
0
,
D
0
)
,
(
s
1
,
m
1
,
σ
1
,
D
1
)
} and (
α
i
,
β
i
,
t
i
), where i
∈
{
0,1
}, there always exists a corresponding pair (
a
i
′
,
b
i
′
) such that (1), (2), (3), and (4) are satisfied.
Thus, go back to Step6 of the game, the bank B succeeds in determining b
^ with probability (
1
/
2
)
+
ε, where ε is negligible since E
^ and E
~ are semantically secure. Therefore, we have Ad
v
D
A
O
E
C
S
Linkability
(
B
)
=
2
ε, which is negligible, so that D
A
O
E
C
S satisfies the unlinkability property.


### 4.2. E-Cash Unforgeability

In this section, we will formally prove that the proposed date attachable offline electronic cash scheme (D
A
O
E
C
S) is secure against forgery attack. The forgery attack can be roughly divided into two types, one is the typical one-more forgery type (i.e., (
l
,
l
+
1
)-forgery) [37] and the other is the forgery on some specific expiration date of an e-cash after sufficient communications with the signing oracle (i.e., bank). The details of definitions and our formal proofs will be described as follows.Definition 4 (Forgery Game 1 inD
A
O
E
C
S (FG-1)).
Letl
k
∈
N be a security parameter and A be an adversary in D
A
O
E
C
S. O
S is an oracle which plays the role of the bank in D
A
O
E
C
S to be responsible for issuing e-cash(s) (i.e., (
s
,
m
,
σ
,
D
), where m
=
(
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
D
)) according to the queries from A. A is allowed to query O
S for l times; consider the experiment Exp
A
FG-
1
(
l
k
) shown in Algorithm 1.  A wins the forgery game FG-1 if the probability Pr[
Ex
p
A
FG-
1
(
l
k
)
=
1
] of A is nonnegligible.Algorithm 1:Experiment FG-1.
Experiment  E
x
p
A
FG-
1
(
l
k
)
(
p
k
j
,
s
k
j
,
g
1
,
g
2
,
e
b
,
d
b
,
p
b
,
q
b
,
n
b
,
H
1
,
H
2
,
H
3
,
H
4
,
H
5
)
←
Setup
(
l
k
)
{
(
s
1
,
m
1
,
σ
1
,
D
1
)
,
…
,
(
s
l
+
1
,
m
l
+
1
,
σ
l
+
1
,
D
l
+
1
)
}
←
A
O
S
(
p
k
j
,
g
1
,
g
2
,
e
b
,
n
b
,
H
1
,
H
2
,
H
3
,
H
4
,
H
5
)
if the following checks are true,return 1;
(i) s
i
e
b
H
1
2
(
m
i
)
H
3
(
σ
i
∥
D
i
)
≡
H
2
(
D
i
) (mod n
b), ∀
i
∈
{
1
,
…
,
l
+
1
};
(ii) m
1
,
…
,
m
l
+
1 are all distinct
elsereturn 0;Definition 5 (Forgery Game 2 inD
A
O
E
C
S (FG-2)).
Letl
k
∈
N be a security parameter and A be an adversary in D
A
O
E
C
S. O
S is an oracle which plays the role of the bank in D
A
O
E
C
S to take charge of the following two events:(i)
issue e-cash(s) (i.e.,(
s
,
m
,
σ
,
D
), where m
=
(
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
D
)) according to the queries from A,
(ii)
record the total numberl
D
i of each distinct expiration date D
i.
A is allowed to query O
S for l times; consider the experiment Exp
A
FG-
2
(
l
k
) shown in Algorithm 2. A wins the forgery game FG-2 if the probability Pr[
Ex
p
A
FG-
2
(
k
)
=
1
] of A is nonnegligible.Algorithm 2:Experiment FG-2.
Experiment
E
x
p
A
FG-
2
(
l
k
)
(
p
k
j
,
s
k
j
,
g
1
,
g
2
,
e
b
,
d
b
,
p
b
,
q
b
,
n
b
,
H
1
,
H
2
,
H
3
,
H
4
,
H
5
)
←
Setup
(
l
k
)
{
(
s
i
,
m
i
,
σ
i
,
D
*
)
,
1
≤
i
≤
l
D
*
+
1
}
←
A
O
S
(
p
k
j
,
g
1
,
g
2
,
e
b
,
n
b
,
H
1
,
H
2
,
H
3
,
H
4
,
H
5
)
if the following checks are true,return 1;
(i)s
i
e
b
H
1
2
(
m
i
)
H
3
(
σ
i
∥
D
*
)
≡
H
2
(
D
*
) (mod n
b), ∀
i
∈
{
1
,
…
,
l
D
*
+
1
};
(ii)m
1
,
…
,
m
l
D
*
+
1 are all distinct;
elsereturn 0;Here we introduce the hard problems used in our proof models.Definition 6 (Alternative Formulation of RSA Chosen-Target Inversion Problem (RSA-ACTI)).
Letk
∈
N be a security parameter and A be an adversary who is allowed to access the RSA-inversion oracle O
inv and the target oracle O
t. A is allowed to query O
t and O
inv for m and q
h times, respectively. Consider Algorithm 3.
We sayA breaks the RSA-ACTI problem if the probability Pr[
Ex
p
A
RSA-ACTI
(
k
)
=
1
] of A is nonnegligible.Algorithm 3
Experiment
E
x
p
A
RSA-ACTI
(
k
)
(
N
,
e
,
d
)
←
R
K
e
y
G
e
n
(
k
).
(
y
1
,
…
,
y
m
)
←
O
t
(
N
,
e
,
k
)
{
π
,
(
x
1
,
y
1
)
,
…
,
(
x
n
,
y
n
)
}
←
A
O
inv
,
O
t
(
N
,
e
,
k
)
if the following checks are true,return 1;
(i)π
:
{
1
,
…
,
n
}
→
{
1
,
…
,
m
} is injective
(ii)x
i
e
≡
y
i (mod N), ∀
i
∈
{
1
,
.
.
.
,
n
}
(iii)n
>
q
h
elsereturn 0;Definition 7 (The RSA Inversion Problem).
Given(
e
,
n
), where n is the product of two distinct large primes p and q with roughly the same length and e is a positive integer relatively-prime to (
p
-
1
)
(
q
-
1
), and a randomly-chosen positive integer y less than n, find an integer x such that x
e
≡
y
(
mod
⁡
n
).Definition 8 (E-Cash Unforgeability).
If there exists no probabilistic polynomial-time adversary who can win FG-1 or FG-2, thenD
A
O
E
C
S is secure against forgery attacks.Theorem 9.
For a polynomial-time adversaryA who can win FG-1 or FG-2 with nonnegligible probability, there exists another adversary S who can break the RSA-ACTI problem or RSA inversion problem with nonnegligible probability.Proof.
S simulates the environment and controls three hash oracles, O
H
1, O
H
2, O
H
3 and an e-cash producing oracle O
S of D
A
O
E
C
S scheme to respond to different queries from A in the random oracle model and takes advantage of A to solve RSA-ACTI problem or RSA inversion problem, simultaneously. Then, for consistency, S maintains three lists L
H
1, L
H
2, and L
H
3 to record every response of O
H
1, O
H
2, and O
H
3, respectively.
Here we will start to do the simulation for the two games (i.e., FG-1 and FG-2) to proveD
A
O
E
C
S is secure against forgery attacks. The details of simulation are set below and illustrated in Figures 6 and 7, respectively.
Simulation in FG-1. In this proof model, S is allowed to query the oracles O
inv (i.e., (
·
)
d) and O
t of RSA-ACTI problem defined in Definition 6 for helping S to produce e-cash(s) and the corresponding verifying key is (
e
,
n
).(i)
H
1 Query of O
H
1
Initially, every blank record inL
H
1 can be represented as (
⊥
,
⊥
,
⊥
). When A sends m for querying the hash value H
1
(
m
), S will check the list L
H
1:
(a)
ifm
=
m
i for some i, then S retrieves the corresponding H
1
(
m
i
) and returns it to A;
(b)
else ifm
=
H
1
(
m
i
) and H
1
2
(
m
i
)
≠
⊥ for some i, then S retrieves the corresponding H
1
2
(
m
i
) and returns it to A;
(c)
else ifm
=
H
1
(
m
i
) and H
1
2
(
m
i
)
=
⊥ for some i, then S queries O
t to get an instance y and returns it to A, then fills the record (
m
i
,
H
1
(
m
i
)
,
⊥
) as (
m
i
,
H
1
(
m
i
)
,
y
) in L
H
1;
(d)
otherwise,S selects a random ρ
∈
Z
n, records (
m
,
ρ
,
⊥
) in L
H
1, and returns ρ to A.
(ii)
H
2 Query of O
H
2
WhenA asks for H
2 query by sending D to S, S will look up the list L
H
2:
(a)
ifD
=
D
i for some i, the corresponding τ will be retrieved and S will send (τ
e
mod
⁡
n) back to A;
(b)
otherwise,S will select a random τ
∈
Z
n, record (
D
,
τ
) in L
H
2, and return (τ
e
mod
⁡
n) back to A.
(iii)
H
3 Query of O
H
3
WhileA sends (
σ
,
D
) to S for H
3
(
σ
∥
D
), S will look up the list L
H
3:
(a)
if(
σ
,
D
)
=
(
σ
i
,
D
i
) for some i, the corresponding η will be retrieved and (η
e
mod
⁡
n) will be returned to A;
(b)
otherwise,S will select a random η
∈
Z
n, record (
(
σ
,
D
)
,
η
) in L
H
3, and return (η
e
mod
⁡
n) back to A.
(iv)
E-Cash Producing Query ofO
S
WhenA sends (
α
,
ϵ
,
D
) to S, S will do the following steps:
(1)
decryptϵ, obtain (
k
,
ID
);
(2)
randomly selectr
j and prepare σ
=
E
^
p
k
j
(
ID
∥
r
j
);
(3)
chooseη
∈
R
Z
n, set H
3
(
σ
∥
D
)
=
(
η
e
mod
n
), and store (
(
σ
,
D
)
,
η
) in L
H
3;
(4)
selectb
∈
R
Z
n
* and compute β
=
(
b
e
η
e
)
-
1
mod
n;
(5)
retrieve or assignτ such that H
2
(
D
)
=
(
τ
e
) as the O
H
2 query described above;
(6)
send(
α
β
τ
e
) to oracle O
inv to get t
=
(
α
β
τ
e
)
d
mod
⁡
n;
(7)
return(
t
,
E
~
k
(
b
,
σ
,
r
j
)
) back to A.
Eventually, assume thatA can successfully output l
+
1 e-cash tuples
(17)
{
(
s
1
,
m
1
,
σ
1
,
D
1
)
⋯
(
s
l
+
1
,
m
l
+
1
,
σ
l
+
1
,
D
l
+
1
)
}
,
where m
i are all distinct, ∀
i
,
1
≤
i
≤
l
+
1, such that s
i
e
H
1
2
(
m
)
H
3
(
σ
i
∥
D
i
)
=
H
2
(
D
i
) (mod
⁡
n) after l times to query O
S with nonnegligible probability ϵ
A.
According toL
H
1, L
H
2, and L
H
3, S can compute and retrieve RSA-inversion instances (∀
i, 1
≤
i
≤
l
+
1)
(18)
(
y
i
)
d
≡
(
H
1
2
(
m
i
)
)
d
≡
s
i
-
1
(
H
3
(
σ
i
∥
D
i
)
-
1
H
2
(
D
i
)
)
d
≡
s
i
-
1
η
i
-
1
(
τ
i
)
(
mod
⁡
n
)
.
Via A querying the signing oracle O
S for l times (i.e., query O
inv for l times by S), S can output l
+
1 RSA-inversion instances
(19)
{
(
s
1
-
1
η
1
-
1
(
τ
1
)
,
y
1
)
,
(
s
2
-
1
η
2
-
1
(
τ
2
)
,
y
2
)
,
…
,
(
s
l
+
1
-
1
η
l
+
1
-
1
(
τ
l
+
1
)
,
y
l
+
1
)
h
(
s
l
+
1
-
1
η
l
+
1
-
1
(
τ
l
+
1
)
,
y
l
+
1
)
}
and break the RSA-ACTI problem with nonnegligible probability at least ϵ
A.
Simulation in FG-2. Initially, S is given an instance (
y
,
e
,
n
) of RSA inversion problem defined in Definition 7 and simulates the environment as follows. (i)
H
1 Query of O
H
1
Initially, every blank record inL
H
1 can be represented as (
⊥
,
⊥
,
⊥
). When A sends m for querying the hash value H
1
(
m
), S will check the list L
H
1:
(a)
ifm
=
m
i for some i, then S retrieves the corresponding ρ
i and returns it to A;
(b)
else ifm
=
H
1
(
m
i
) and H
1
2
(
m
i
)
≠
⊥ for some i, then S retrieves the corresponding ς and returns (ς
e
mod
⁡
n) to A;
(c)
else ifm
=
H
1
(
m
i
) and H
1
2
(
m
i
)
=
⊥ for some i, then S selects a random ς
∈
Z
n, returns (ς
e
mod
⁡
n) to A, and then fills the record (
m
i
,
H
1
(
m
i
)
,
⊥
) as (
m
i
,
H
1
(
m
i
)
,
ς
) in L
H
1;
(d)
otherwise,S selects a random ρ
∈
Z
n, records (
m
,
ρ
,
⊥
) in L
H
1, and returns ρ to A.
(ii)
H
2 Query of O
H
2
WhenA asks for H
2 query by sending D to S, S will look up the list L
H
2:
(a)
ifD
=
D
i for some i, the corresponding τ will be retrieved and S will send (τ
e
mod
⁡
n) back to A;
(b)
otherwise,S will select a random τ
∈
Z
n, record (
D
,
τ
) in L
H
2, and return (τ
e
mod
⁡
n) back to A.
(iii)
H
3 Query of O
H
3
WhileA sends (
σ
,
D
) to S for H
3
(
σ
∥
D
), S will look up the list L
H
3:
(a)
if(
σ
,
D
)
=
(
σ
i
,
D
i
) for some i, the corresponding H
3
(
σ
i
∥
D
i
) will be retrieved and returned to A;
(b)
otherwise,S will select a random η
∈
Z
n, set H
3
(
σ
∥
D
)
=
(
η
e
y mod n), record (
(
σ
,
D
)
,
η
,
H
3
(
σ
∥
D
)
) in L
H
3, and return H
3
(
σ
∥
D
) back to A.
(iv)
E-Cash Producing Query ofO
S
Letl
D
i be a counter to record the number of queries on each expiration date D
i, which is initialized by 0. When A sends (
α
,
ϵ
,
D
) to S, S will do the following steps:
(1)
decryptϵ, obtain (
k
,
ID
);
(2)
randomly selectr
j and prepare σ
=
E
^
p
k
j
(
ID
∥
r
j
);
(3)
chooseη
∈
R
Z
n, set H
3
(
σ
∥
D
)
=
(
α
η
e
mod
⁡
n
), and store (
(
σ
,
D
)
,
⊥
,
(
α
η
e
mod
⁡
n
)
) and (
σ
,
D
) in L
H
3 and L
x, respectively;
(4)
selectb
∈
R
Z
n
* and compute β
=
(
b
e
α
η
e
)
-
1
mod
⁡
n;
(5)
retrieve or assignτ such that H
2
(
D
)
=
(
τ
e
) as the O
H
2 query described above;
(6)
computet
≡
(
α
β
τ
e
)
d
≡
(
(
b
η
)
-
1
τ
) (mod
⁡
n);
(7)
setl
D
=
l
D
+
1 and return (
t
,
E
~
k
(
b
,
σ
,
r
j
)
) back to A.
Eventually, assume thatA can successfully output l
D
′
+
1 e-cash tuples for some expiration date D
′
(20)
{
(
s
1
,
m
1
,
σ
1
,
D
′
)
⋯
(
s
l
D
′
+
1
,
m
l
D
′
+
1
,
σ
l
D
′
+
1
,
D
′
)
}
such that s
i
e
H
1
2
(
m
i
)
H
3
(
σ
i
∥
D
′
)
=
H
2
(
D
′
) (mod
⁡
n), ∀
i
,
1
≤
i
≤
l
D
′
+
1, after l
D
′ times to query O
S on D
′, with nonnegligible probability ϵ
A.
Assume some(
σ
i
,
D
′
), 1
≤
i
≤
l
D
′
+
1, is not recorded in L
x; then by the L
H
1, L
H
2, and L
H
3, S can compute and retrieve
(21)
(
s
i
)
e
≡
(
H
1
2
(
m
i
)
H
3
(
σ
i
∥
D
′
)
)
-
1
H
2
(
D
′
)
≡
(
(
ς
i
e
)
(
η
i
e
y
)
)
-
1
(
τ
i
e
)
(
mod
⁡
n
)
,
x
≡
y
d
≡
(
s
i
ς
i
η
i
)
-
1
τ
i
(
mod
⁡
n
)
and solve the RSA inversion problem with nonnegligible probability at least ϵ
A.Figure 6
The proof model of FG-1.Figure 7
The proof model of FG-2.


### 4.3. E-Cash Conditional-Traceability

In this section, we will prove that the ID information embedded in e-cash(s) cannot be replaced or moved out by any user against being traced after some misbehavior or criminals. The details of our proof model are illustrated in Figure8.Figure 8
The proof model of TG.Definition 10 (Tampering Game (TG)).
Letl
k
∈
N be a security parameter and A be an adversary in D
A
O
E
C
S. O
S is an oracle which plays the role of bank in D
A
O
E
C
S to record parameters from the queries of A and issue e-cash(s) (i.e., (
s
,
m
,
σ
,
D
), where m
=
(
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
D
)) accordingly. A is allowed to query O
S for l times; consider Algorithm 4.
A wins the game if the probability Pr[
Ex
p
A
TG
(
k
)
=
1
] of A is nonnegligible.Algorithm 4
Experiment
E
x
p
A
TG
(
l
k
)
(
p
k
j
,
s
k
j
,
g
1
,
g
2
,
e
b
,
d
b
,
p
b
,
q
b
,
n
b
,
H
1
,
H
2
,
H
3
,
H
4
,
H
5
)
←
Setup
(
l
k
)
(
s
′
,
m
′
,
σ
′
,
D
′
)
←
A
O
S
(
p
k
T
A
,
e
R
,
n
R
,
H
1
,
H
2
)
{
σ
1
,
…
,
σ
l
}
←
O
S
if the following two checks are true,return 1;
(i)σ
′
∉
{
σ
1
,
…
,
σ
l
}
(ii)s
′
e
H
1
2
(
m
′
)
H
3
(
σ
′
∥
D
′
)
=
H
2
(
D
′
) mod n
elsereturn 0;Definition 11 (E-Cash Traceability).
If there exists no probabilistic polynomial-time adversary who can win the tracing game TG, thenD
A
O
E
C
S satisfies the E-Cash Traceability.Definition 12 (Alternative Formulation of RSA Known-Target  Inversion Problem (RSA-AKTI)).
Letk
∈
N be a security parameter and A be an adversary who is allowed to access the RSA-inversion oracle O
inv and the target oracle O
t. A is allowed to query O
t and O
inv for q
t and q
h times (q
h
<
q
t), respectively. Consider Algorithm 5.
We sayA breaks the RSA-AKTI problem if the probability Pr[
Ex
p
A
RSA-AKTI
(
k
)
=
1
] of A is nonnegligible.Algorithm 5
Experiment
E
x
p
A
RSA-AKTI
(
k
)
(
N
,
e
,
d
)
←
R
K
e
y
G
e
n
(
k
).
(
y
1
,
…
,
y
q
t
)
←
O
t
(
N
,
e
,
k
)
{
(
x
1
,
y
1
)
,
…
,
(
x
q
t
,
y
q
t
)
}
←
A
O
inv
,
O
t
(
N
,
e
,
k
)
ifx
i
e
≡
y
i (mod N), ∀
i
∈
{
1
,
…
,
q
t
}, return 1;
elsereturn 0;Theorem 13.
For a polynomial-time adversaryA who can win the tracing game TG with nonnegligible probability, there exists another adversary S who can break the RSA-AKTI problem with nonnegligible probability.Proof.
S simulates the environment of D
A
O
E
C
S by controlling three hash oracles, O
H
1, O
H
2, O
H
3, to respond hash queries and an e-cash producing oracle O
S of D
A
O
E
C
S to respond e-cash producing queries from A, respectively, in the random oracle model. Eventually, S will take advantage of A’s capability to solve RSA-AKTI problem. Then, for consistency, S maintains three lists L
H
1, L
H
2, and L
H
3 to record every response of O
H
1, O
H
2, and O
H
3, respectively.
Besides, in the proof model,S is allowed to query the oracles O
inv (i.e., (
·
)
d) and O
t of the RSA-AKTI problem defined in Definition 12 for helping S produce valid e-cash(s) and the corresponding verifying key is (
e
,
n
).
Here we will do the simulation for gameTG to prove that D
A
O
E
C
S satisfies the e-cash traceability. Details are described as follows.(i)
H
1 Query of O
H
1
Initially, every blank record inL
H
1 can be represented as (
⊥
,
⊥
,
⊥
). When A sends m for querying the hash value H
1
(
m
), S will check the list L
H
1:
(a)
ifm
=
m
i for some i, then S retrieves the corresponding H
1
(
m
i
) and return it to A;
(b)
else ifm
=
H
1
(
m
i
) and H
1
2
(
m
i
)
≠
⊥ for some i, then S retrieves the corresponding ς
i and returns (ς
i
e
mod
⁡
n) to A;
(c)
else ifm
=
H
1
(
m
i
) and H
1
2
(
m
i
)
=
⊥ for some i, then S chooses ς
∈
R
Z
n, sets H
1
2
(
m
i
)
=
(
ς
e
mod
⁡
n), and returns H
1
2
(
m
i
) to A then fills the original record (
m
i
,
H
1
(
m
i
)
,
⊥
) as (
m
i
,
H
1
(
m
i
)
,
ς
) in L
H
1;
(d)
otherwise,S selects a random ρ
∈
Z
n, sets H
1
(
m
i
)
=
ρ, records (
m
,
H
1
(
m
i
)
,
⊥
) in L
H
1, and returns ρ to A.
(ii)
H
2 Query of O
H
2
WhenA asks for H
2 query by sending D to S, S will look up the list L
H
2:
(a)
ifD
=
D
i for some i, the corresponding τ will be retrieved and S will send (τ
e
mod
⁡
n) back to A;
(b)
otherwise,S will select a random τ
∈
Z
n, record (
D
,
τ
) in L
H
2, and return (τ
e
mod
⁡
n) back to A.
(iii)
H
3 Query of O
H
3
WhileA sends (
σ
,
D
) to S for H
3
(
σ
), S will look up the list L
H
3:
(a)
if(
σ
,
D
)
=
(
σ
i
,
D
i
) for some i, the corresponding y
i will be retrieved and returned to A;
(b)
otherwise,S will query O
t to get an instance y; record y and (
(
σ
,
D
)
,
y
) in L
T and L
H
3, respectively;
(c)
returny back to A.
(iv)
E-Cash Producing Query ofO
S
WhileA sends (
α
,
ϵ
,
D
) to S, S will do the following steps:
(1)
decryptϵ, obtain (
k
,
ID
);
(2)
randomly selectr
j and prepare σ
=
E
^
p
k
j
(
ID
∥
r
j
);
(3)
chooseη
∈
R
Z
n, set H
3
(
σ
∥
D
)
=
(
α
η
e
mod
⁡
n
), and store (
(
σ
,
D
)
,
H
3
(
σ
∥
D
)
) in L
H
3;
(4)
selectb
∈
R
Z
n
* and compute β
=
(
b
e
α
η
e
)
-
1
mod
⁡
n;
(5)
retrieve or assignτ such that H
2
(
D
)
=
(
τ
e
) as the O
H
2 query described above;
(6)
computet
≡
(
α
β
τ
e
)
d
≡
(
(
b
η
)
-
1
τ
) (mod
⁡
n);
(7)
return(
t
,
E
~
k
(
b
,
σ
,
r
j
)
) back to A.
Assume thatA can successfully output an e-cash tuples (
s
′
,
m
′
,
σ
′
,
D
′
), where σ
′ never appeals as a part for some O
S query such that s
′
e
H
1
2
(
m
′
)
H
3
(
σ
′
∥
D
′
)
≡
H
2
(
D
′
) (mod
⁡
n); then by L
H
1, L
H
2, and L
H
3, S can derive
(22)
(
y
′
)
d
≡
(
H
3
(
σ
′
∥
D
′
)
)
d
≡
s
′
-
1
(
H
1
2
(
m
′
)
-
1
H
2
(
D
′
)
)
d
≡
s
′
-
1
ς
′
-
1
τ
′
(
mod
⁡
n
)
.
Let |
L
T
|
=
q
t and L
T
=
{
y
1
,
…
,
y
q
t
}. S sends y
i
∈
(
L
T
-
{
y
′
}
), 1
≤
i
≤
(
q
t
-
1
), to O
inv and obtains q
t
-
1
x
i such that x
i
=
y
i
d
mod
⁡
n.
EventuallyS can output q
t RSA-inversion instances
(23)
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
…
,
(
x
q
t
-
1
,
y
q
t
-
1
)
,
(
(
s
′
-
1
ς
′
-
1
τ
′
)
,
y
′
)
}
after querying O
inv for q
h times, where q
h
=
q
t
-
1
<
q
t and thus, it breaks the RSA-AKTI problem with nonnegligible probability at least ϵ
A.


### 4.4. E-Cash No-Swindling

In typical online e-cash transactions, when an e-cash has been spent in previous transactions, another spending will be detected immediately owing to the double-spending check procedure. However, in an offline e-cash model, the merchant may accept a transaction involving a double-spent e-cash first and then do the double-spending check later. In this case, the original owner of the e-cash may suffer from loss. Therefore, a secure offline e-cash scheme should guarantee the following two events.(i)
No one, except the real owner, can spend a fresh and valid offline e-cash successfully.
(ii)
No one can double spend an e-cash successfully.Roughly, it can be referred to ase-cash no-swindling property. In this section, we will define the no-swindling property and formally prove that our scheme is secure against swindling attacks.Definition 14 (Swindling Game inD
A
O
E
C
S).
Letl
k
∈
N be a security parameter and A be an adversary in D
A
O
E
C
S. O
B is an oracle issuing generic e-cash(s) (i.e., (
s
,
y
1
,
w
1
,
x
2
,
r
2
,
r
3
,
σ
,
D
)) of D
A
O
E
C
S to A. O
off
⁡ is an oracle to show the expanding form (
s
,
y
1
,
w
1
,
x
2
,
r
2
,
r
3
,
σ
,
D
,
r
s
,
s
′
) for the payment according to the input (
s
,
m
,
σ
,
D
). Consider the two experiments SWG-1 and SWG-2 shown in Algorithms 6 and 7, respectively.
A wins the game if the probability Pr[
Ex
p
A
SWG-
1
(
l
k
)
=
1
] or Pr[
Ex
p
A
SWG-
2
(
l
k
)
=
1
] of A is nonnegligible.Algorithm 6:Experiment SWG-1.
Experiment
E
x
p
A
SWG-
1
(
l
k
)
(
p
k
j
,
s
k
j
,
g
1
,
g
2
,
e
b
,
d
b
,
p
b
,
q
b
,
n
b
,
p
,
q
,
H
1
,
H
2
,
H
3
,
H
4
,
H
5
)
←
Setup
(
l
k
)
{
(
s
,
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
σ
,
D
,
r
u
,
r
s
,
s
′
)
}
←
A
O
B
,
O
off
⁡
(
p
k
j
,
g
1
,
g
2
,
e
b
,
n
b
,
p
,
q
,
H
1
,
H
2
,
H
3
,
H
4
,
H
5
)
if the following checks are true,return 1;
(i) s
e
b
H
1
2
(
y
H
4
(
r
u
∥
r
s
)
g
s
′
mod
⁡
p
∥
y
1
∥
w
2
∥
y
2
∥
D
∥
r
3
)
H
3
(
σ
∥
D
)
=
H
2
(
D
) mod n
b;
(ii) (
s
,
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
σ
,
D
) never be a query to O
off
⁡
elsereturn 0;Algorithm 7:Experiment SWG-2.
Experiment
E
x
p
A
SWG-
2
(
l
k
)
(
p
k
j
,
s
k
j
,
g
1
,
g
2
,
e
b
,
d
b
,
p
b
,
q
b
,
n
b
,
p
,
q
,
H
1
,
H
2
,
H
3
,
H
4
,
H
5
)
←
Setup
(
l
k
)
{
(
s
,
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
σ
,
D
,
r
u
,
r
s
,
s
′
)
}
←
A
O
B
,
O
off
⁡
(
p
k
j
,
g
1
,
g
2
,
e
b
,
n
b
,
p
,
q
,
H
1
,
H
2
,
H
3
,
H
4
,
H
5
)
if the following checks are true,return 1;
(i)s
e
b
H
1
2
(
y
H
4
(
r
u
∥
r
s
)
g
s
′
mod
⁡
p
∥
y
1
∥
w
2
∥
y
2
∥
D
∥
r
3
)
H
3
(
σ
∥
D
)
=
H
2
(
D
) mod n
b;
(ii)(
s
,
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
σ
,
D
) is allowed to be queried to O
off
⁡ for once;
(iii)(
s
,
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
σ
,
D
,
r
s
,
s
′
) is not obtained from O
off
⁡
elsereturn 0;Definition 15 (E-Cash No-Swindling).
If there exists no probabilistic polynomial-time adversary who can win the swindling game defined in Definition14, then D
A
O
E
C
S satisfies e-cash no-swindling.Theorem 16.
For a polynomial-time adversaryA who can win the swindling game SWG with nonnegligible probability, there exists another adversary S who can solve the discrete logarithm problem with nonnegligible probability.Proof.
Consider the swindling game defined in Definition14. S simulates the environment by controlling the hash oracles, O
H
4, to respond hash queries on H
4 of D
A
O
E
C
S in the random oracle model. Eventually, S will take advantage of A’s capability to solve the discrete logarithm problem. Then, for consistency, S maintains a list L
H
4 to record every response of O
H
4. S is given all parameters (
p
k
j
,
s
k
j
,
g
1
,
g
2
,
e
b
,
d
b
,
p
b
,
q
b
,
n
b
,
p
,
q
,
H
1
,
H
2
,
H
3
,
H
4
,
H
5
) of D
A
O
E
C
S and an instance y
* of discrete logarithm problem (i.e., y
*
=
g
x
*
mod
⁡
p). Here we will describe the simulations for the two experiments Exp
A
SWG-
1 and Exp
A
SWG-
2, individually.
The simulation forExp
A
SWG-
1 is illustrated in Figure 9 and each oracle is constructed as follows.(i)
OracleO
B
Initially,S guesses that the generic e-cash produced from νth query will be the attack target. When A sends ith query to O
B for an e-cash, O
B will do the following:
(a)
selectr
1, x
1, r
3
∈
R
Z
q and y
2, w
2
∈
R
Z
p;
(b)
ifi
=
ν,
(1)
compute (w
1
=
(
y
*
)
r
1
mod
⁡
p) and (y
1
=
g
x
1
mod
⁡
p);
(c)
ifi
≠
ν,
(1)
compute (w
1
=
g
r
1
mod
⁡
p) and (y
1
=
g
x
1
mod
⁡
p);
(d)
prepares
=
(
(
H
1
2
(
m
)
H
3
(
σ
∥
D
)
)
-
1
H
2
(
D
)
)
d
b
mod
⁡
n
b, where m
=
(
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
D
);
(e)
record(
i
,
(
s
,
m
,
σ
,
D
)
,
(
r
1
,
x
1
)
)
) in list L
B and return (
s
,
m
,
σ
,
D
) to A.
(ii)
OracleO
off
⁡
WhenA sends a valid e-cash tuple (
s
,
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
σ
,
D
,
r
s
) to O
off
⁡, it will look up the list L
B:
(a)
if(
s
,
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
σ
,
D
) exists with prefix index ν, then abort;
(b)
otherwise,O
off
⁡ will retrieve the corresponding (
r
1
,
x
1
); choose a random r
u, compute u
=
H
4
(
r
u
∥
r
s
) and (s
′
=
r
1
-
u
x
1
mod
⁡
q), and send (
s
,
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
σ
,
D
,
r
u
,
r
s
,
s
′
) back to A.
Assume thatA can successfully output a valid offline e-cash expansion tuple (
s
*
,
w
1
*
,
y
1
*
,
w
2
*
,
y
2
*
,
r
3
*
,
σ
*
,
D
*
,
r
u
*
,
r
s
*
,
s
′
*
), where (
s
*
,
w
1
*
,
y
1
*
,
w
2
*
,
y
2
*
,
r
3
*
,
σ
*
,
D
*
) is prefixed with ν and postfixed with (
r
1
*
,
x
1
*
) in L
B. Then, since w
1
*
=
y
1
*
H
4
(
r
u
*
∥
r
s
*
)
g
s
′
*
mod
⁡
p and w
1
*
=
(
y
*
)
r
1
*, S can derive
(24)
x
*
=
(
r
1
*
)
-
1
(
x
1
*
H
4
(
r
u
*
∥
r
s
*
)
+
s
′
*
)
mod
⁡
q
and solve the discrete logarithm problem with nonnegligible probability at least (
1
/
q
O
B
)
ϵ
A, where q
O
B is the total number of O
B query.
The simulation forExp
A
SWG-
2 is illustrated in Figure 10 and each oracle is constructed as follows.(i)
OracleO
B
Initially,S guesses that the generic e-cash produced from νth query will be the attack target. When A sends ith query to O
B for an e-cash, O
B will do the followings.
(a)
ifi
=
ν:
(1)
selects
′, u, x
1, r
3
∈
R
Z
q and y
2, w
2
∈
R
Z
p;
(2)
compute (y
1
=
(
y
*
)
x
1
mod
⁡
p) and (w
1
=
y
1
u
g
s
′
mod
⁡
p);
(3)
prepares
=
(
(
H
1
2
(
m
)
H
3
(
σ
∥
D
)
)
-
1
H
2
(
D
)
)
d
b
mod
⁡
n
b, where m
=
(
w
1, y
1, w
2, y
2, r
3, D
);
(4)
record(
i
,
(
s
,
m
,
σ
,
D
)
,
(
u
,
s
′
)
)
) in list L
B;
(b)
ifi
≠
ν:
(1)
selectr
1, x
1, r
3
∈
R
Z
q and y
2, w
2
∈
R
Z
p;
(2)
compute (w
1
=
g
r
1
mod
⁡
p) and (y
1
=
g
x
1
mod
⁡
p);
(3)
prepares
=
(
(
H
1
2
(
m
)
H
3
(
σ
∥
D
)
)
-
1
H
2
(
D
)
)
d
b
mod
⁡
n
b, where m
=
(
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
D
);
(4)
record(
i
,
(
s
,
m
,
σ
,
D
)
,
(
r
1
,
x
1
)
)
) in list L
B;
(c)
return(
s
,
m
,
σ
,
D
) to A.
(ii)
OracleO
off
⁡
A status parametersta is initialized by 0. When A sends a valid e-cash tuple (
s
,
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
σ
,
D
,
r
s
) to O
off
⁡, it will look up the list L
B:
(a)
if(
s
,
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
σ
,
D
) exists with prefix index ν and sta
=
0, O
off
⁡ will perform the following procedures:
(1)
setsta
=
1
(2)
retrieve the corresponding(
u
,
s
′
) from L
B and choose a random r
u;
(3)
setH
4
(
r
u
∥
r
s
)
=
u and record (
(
r
u
∥
r
s
)
,
u
) in L
H;
(4)
record(
s
,
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
σ
,
D
,
r
u
,
r
s
,
s
′
) in list L
off
⁡;
(5)
send(
s
,
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
σ
,
D
,
r
u
,
r
s
,
s
′
) back to A;
(b)
if(
s
,
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
σ
,
D
) exists with prefix index ≠
ν, O
off
⁡ will retrieve the corresponding (
r
1
,
x
1
), choose random r
u and u, set H
4
(
r
u
∥
r
s
)
=
u, record (
(
r
u
∥
r
s
)
,
u
) in L
H, compute (s
′
=
r
1
-
u
x
1
mod
⁡
q), and send (
s
,
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
σ
,
D
,
r
u
,
r
s
,
s
′
) back to A.
(c)
Otherwise, abort.
(iii)
OracleO
H
4
WhileA sends (
r
u
∥
r
s
) to query for H
4
(
r
u
∥
r
s
), O
H
4 will check the list L
H:
(a)
if(
r
u
∥
r
s
) exists as the prefix of some record, O
H
4 will retrieve the corresponding u and return it to A;
(b)
otherwise,O
H
4 will choose a random u, record (
(
r
u
∥
r
s
)
,
u
) in L
H, and return u to A.
Assume thatA can successfully output a valid offline e-cash expansion tuple (
s
*
,
w
1
*
,
y
1
*
,
w
2
*
,
y
2
*
,
r
3
*
,
σ
*
,
D
*
,
r
u
*
,
r
s
*
,
s
′
*
), where (
s
*
,
w
1
*
,
y
1
*
,
w
2
*
,
y
2
*
,
r
3
*
,
σ
*
,
D
*
) is prefixed with ν and postfixed with (
u
,
s
′
) in L
B and H
4
(
r
u
*
∥
r
s
*
)
≠
u.
Then, viaL
H, since
(25)
(
y
*
x
1
*
)
u
*
g
s
′
*
≡
(
y
1
*
)
H
4
(
r
u
*
∥
r
s
*
)
g
s
′
*
≡
w
1
*
≡
(
y
*
x
1
*
)
u
g
s
′
(
mod
⁡
p
)
,
S can derive
(26)
x
*
=
(
x
1
*
(
u
*
-
u
)
)
-
1
(
s
′
-
s
′
*
)
mod
⁡
q
and solve the discrete logarithm problem with nonnegligible probability at least (
1
/
q
O
B
)
ϵ
A, where q
O
B is the total number of O
B query.Figure 9
The proof model of SWG-1.Figure 10
The proof model of SWG-2.Summarize the proof models for the two experiments shown above, if there exists a polynomial-time adversary who can win the swindling game with nonnegligible probability, then there exists another one who can solve the discrete logarithm problem with nonnegligible probability. It implies that there exists no p.p.t. adversary who can win the swindling game, and our proposed offline e-cash schemeD
A
O
E
C
S satisfies no-swindling property.


## 4.1. E-Cash Unlinkability

Based on the definition of unlinkability introduced by Abe and Okamoto [35] and Juels et al. [36], we formally define the unlinkability property of D
A
O
E
C
S.Definition 1 (The Linkage Game).
LetU
0, U
1, and J be two honest users and the judge that follows D
A
O
E
C
S, respectively. Let B be the bank that participates the following game with U
0, U
1, and J. The game environment is shown in Figure 5.Figure 5
The game environment of linkage game.Step 1.
According toD
A
O
E
C
S, B generates the bank’s public key (
e
b
,
n
b
), the bank’s private key (
d
b
,
p
b
,
q
b
), system parameters (
p
,
q
,
g
1
,
g
2
), the expiration date D, and the five public one-way hash functions H
1, H
2,  H
3, H
4, and H
5. J generates the judge’s public-private key pair (
p
k
j
,
s
k
j
).Step 2.
B generates x
1
i, x
2
i, r
1
i, r
2
i, r
3
i in random, where x
1, x
2, r
1, r
2, r
3
∈
R
{
0,1
,
…
,
q
-
1
}, and computes (
y
k
i
,
w
k
i
) for k
=
{
1,2
} and i
=
{
0,1
}, where y
k
i
=
g
k
x
k
mod
⁡
p and w
k
i
=
g
k
r
k
mod
⁡
p.Step 3.
We choose a bitb
^
∈
{
0,1
} randomly and place (
y
1
b
^
,
w
1
b
^
,
y
2
b
^
,
w
2
b
^
) and (
y
1
1
-
b
^
,
w
1
1
-
b
^
,
y
2
1
-
b
^
,
w
2
1
-
b
^
) on the private input tapes of U
0 and U
1, respectively, where b
^ is not disclosed to B.Step 4.
B performs the withdrawal protocol of D
A
O
E
C
S with U
0 and U
1, respectively.Step 5.
IfU
0 and U
1 output two e-cash(s) (
s
b
^
,
m
b
^
,
σ
b
^
,
D
b
^
) and (
s
1
-
b
^
,
m
1
-
b
^
,
σ
1
-
b
^
,
D
1
-
b
^
), where m
i
=
(
y
1
i
,
w
1
i
,
y
2
i
,
w
2
i
,
r
3
i
), on their private tapes, respectively, we give the two e-cash(s) in a random order to B; otherwise, ⊥ is given to B.Step 6.
B outputs b
^
′
∈
{
0,1
} as the guess of b
^. The bank B wins the game if b
^
′
=
b
^ and J has not revoked the anonymity of (
s
b
^
,
m
b
^
,
σ
b
^
,
D
b
^
) and (
s
1
-
b
^
,
m
1
-
b
^
,
σ
1
-
b
^
,
D
1
-
b
^
) to B. We define the advantage of B as
(13)
Ad
v
D
A
O
E
C
S
Linkability
(
B
)
=
|
2
Pr
[
b
^
′
=
b
^
]
-
1
|
,
where Pr
[
b
^
′
=
b
^
] denotes the probability of b
^
′
=
b
^.Definition 2 (Unlinkability).
AD
A
O
E
C
S satisfies the unlinkability property if and only if the advantage Ad
v
D
A
O
E
C
S
Linkability
(
B
) defined in Definition 1 is negligible.Theorem 3.
AD
A
O
E
C
S satisfies the unlinkability property of Definition 2 if the adopted cryptosystems are semantically secure.Proof.
IfB is given ⊥ in the Step 5 of the game, it will determine b
^ with probability 1
/
2, which is exactly the same as a random guess of b
^.
Here, we assume thatB gets two e-cash (
s
0
,
m
0
,
σ
0
,
D
0
) and (
s
1
,
m
1
,
σ
1
,
D
1
). Let (
α
i
,
β
i
,
t
i
,
ϵ
i
,
E
~
k
i
(
b
i
,
σ
i
,
r
j
i
)
), i
∈
{
0,1
}, be the view of data exchanged between U
i and B in the withdrawal protocol (Section 3.2.2) and let (
x
2
i
,
r
2
i
,
r
4
i
,
r
u
i
,
r
s
i
,
s
i
′
,
d
i
) be the view of data exchanged when B performs the payment protocol (Section 3.2.3) and the deposit protocol (Section 3.2.4) by using (
s
i
,
m
i
,
σ
i
,
D
i
), where i
∈
{
0,1
}.
For(
s
,
m
,
σ
,
D
,
x
2
,
r
2
,
r
4
,
r
u
,
r
s
,
s
′
,
d
)
∈
(14)
{
(
s
0
,
m
0
,
σ
0
,
D
0
,
x
2
0
,
r
2
0
,
r
4
0
,
r
u
0
,
r
s
0
,
s
0
′
,
d
0
)
,
h
(
s
1
,
m
1
,
σ
1
,
D
1
,
x
2
1
,
r
2
1
,
r
4
1
,
r
u
1
,
r
s
1
,
s
1
′
,
d
1
)
}
and (
α
i
,
β
i
,
t
i
,
ϵ
i
,
E
~
k
i
(
b
i
,
σ
i
,
r
j
i
)
), i
∈
{
0,1
}, there always exists a pair (
a
i
′
,
b
i
′
) such that
(15)
a
i
′
=
[
α
i
H
1
2
(
m
∥
D
)
]
-
d
b
mod
⁡
n
b
(
via
(
1
)
)
,
b
i
′
=
[
β
i
H
3
(
σ
∥
D
)
]
-
d
b
mod
⁡
n
b
(
via
(
2
)
)
.
And from (3), t
i
≡
(
α
i
β
i
H
2
(
D
)
)
d
b
(
mod
⁡
n
b
), (4) always holds as
(16)
s
≡
(
a
i
′
b
i
′
t
i
)
≡
[
(
H
1
2
(
m
∥
D
)
H
3
(
σ
∥
D
)
)
-
1
H
2
(
D
)
]
d
b
(
mod
⁡
n
b
)
.
Besides, E
^
p
k
j and E
~
k
i are semantically secure encryption functions. B cannot learn any information from ϵ
i and E
~
k
i
(
b
i
,
σ
i
,
r
j
i
).
From the above, given any(
s
,
m
,
σ
,
D
)
∈
{
(
s
0
,
m
0
,
σ
0
,
D
0
)
,
(
s
1
,
m
1
,
σ
1
,
D
1
)
} and (
α
i
,
β
i
,
t
i
), where i
∈
{
0,1
}, there always exists a corresponding pair (
a
i
′
,
b
i
′
) such that (1), (2), (3), and (4) are satisfied.
Thus, go back to Step6 of the game, the bank B succeeds in determining b
^ with probability (
1
/
2
)
+
ε, where ε is negligible since E
^ and E
~ are semantically secure. Therefore, we have Ad
v
D
A
O
E
C
S
Linkability
(
B
)
=
2
ε, which is negligible, so that D
A
O
E
C
S satisfies the unlinkability property.


## 4.2. E-Cash Unforgeability

In this section, we will formally prove that the proposed date attachable offline electronic cash scheme (D
A
O
E
C
S) is secure against forgery attack. The forgery attack can be roughly divided into two types, one is the typical one-more forgery type (i.e., (
l
,
l
+
1
)-forgery) [37] and the other is the forgery on some specific expiration date of an e-cash after sufficient communications with the signing oracle (i.e., bank). The details of definitions and our formal proofs will be described as follows.Definition 4 (Forgery Game 1 inD
A
O
E
C
S (FG-1)).
Letl
k
∈
N be a security parameter and A be an adversary in D
A
O
E
C
S. O
S is an oracle which plays the role of the bank in D
A
O
E
C
S to be responsible for issuing e-cash(s) (i.e., (
s
,
m
,
σ
,
D
), where m
=
(
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
D
)) according to the queries from A. A is allowed to query O
S for l times; consider the experiment Exp
A
FG-
1
(
l
k
) shown in Algorithm 1.  A wins the forgery game FG-1 if the probability Pr[
Ex
p
A
FG-
1
(
l
k
)
=
1
] of A is nonnegligible.Algorithm 1:Experiment FG-1.
Experiment  E
x
p
A
FG-
1
(
l
k
)
(
p
k
j
,
s
k
j
,
g
1
,
g
2
,
e
b
,
d
b
,
p
b
,
q
b
,
n
b
,
H
1
,
H
2
,
H
3
,
H
4
,
H
5
)
←
Setup
(
l
k
)
{
(
s
1
,
m
1
,
σ
1
,
D
1
)
,
…
,
(
s
l
+
1
,
m
l
+
1
,
σ
l
+
1
,
D
l
+
1
)
}
←
A
O
S
(
p
k
j
,
g
1
,
g
2
,
e
b
,
n
b
,
H
1
,
H
2
,
H
3
,
H
4
,
H
5
)
if the following checks are true,return 1;
(i) s
i
e
b
H
1
2
(
m
i
)
H
3
(
σ
i
∥
D
i
)
≡
H
2
(
D
i
) (mod n
b), ∀
i
∈
{
1
,
…
,
l
+
1
};
(ii) m
1
,
…
,
m
l
+
1 are all distinct
elsereturn 0;Definition 5 (Forgery Game 2 inD
A
O
E
C
S (FG-2)).
Letl
k
∈
N be a security parameter and A be an adversary in D
A
O
E
C
S. O
S is an oracle which plays the role of the bank in D
A
O
E
C
S to take charge of the following two events:(i)
issue e-cash(s) (i.e.,(
s
,
m
,
σ
,
D
), where m
=
(
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
D
)) according to the queries from A,
(ii)
record the total numberl
D
i of each distinct expiration date D
i.
A is allowed to query O
S for l times; consider the experiment Exp
A
FG-
2
(
l
k
) shown in Algorithm 2. A wins the forgery game FG-2 if the probability Pr[
Ex
p
A
FG-
2
(
k
)
=
1
] of A is nonnegligible.Algorithm 2:Experiment FG-2.
Experiment
E
x
p
A
FG-
2
(
l
k
)
(
p
k
j
,
s
k
j
,
g
1
,
g
2
,
e
b
,
d
b
,
p
b
,
q
b
,
n
b
,
H
1
,
H
2
,
H
3
,
H
4
,
H
5
)
←
Setup
(
l
k
)
{
(
s
i
,
m
i
,
σ
i
,
D
*
)
,
1
≤
i
≤
l
D
*
+
1
}
←
A
O
S
(
p
k
j
,
g
1
,
g
2
,
e
b
,
n
b
,
H
1
,
H
2
,
H
3
,
H
4
,
H
5
)
if the following checks are true,return 1;
(i)s
i
e
b
H
1
2
(
m
i
)
H
3
(
σ
i
∥
D
*
)
≡
H
2
(
D
*
) (mod n
b), ∀
i
∈
{
1
,
…
,
l
D
*
+
1
};
(ii)m
1
,
…
,
m
l
D
*
+
1 are all distinct;
elsereturn 0;Here we introduce the hard problems used in our proof models.Definition 6 (Alternative Formulation of RSA Chosen-Target Inversion Problem (RSA-ACTI)).
Letk
∈
N be a security parameter and A be an adversary who is allowed to access the RSA-inversion oracle O
inv and the target oracle O
t. A is allowed to query O
t and O
inv for m and q
h times, respectively. Consider Algorithm 3.
We sayA breaks the RSA-ACTI problem if the probability Pr[
Ex
p
A
RSA-ACTI
(
k
)
=
1
] of A is nonnegligible.Algorithm 3
Experiment
E
x
p
A
RSA-ACTI
(
k
)
(
N
,
e
,
d
)
←
R
K
e
y
G
e
n
(
k
).
(
y
1
,
…
,
y
m
)
←
O
t
(
N
,
e
,
k
)
{
π
,
(
x
1
,
y
1
)
,
…
,
(
x
n
,
y
n
)
}
←
A
O
inv
,
O
t
(
N
,
e
,
k
)
if the following checks are true,return 1;
(i)π
:
{
1
,
…
,
n
}
→
{
1
,
…
,
m
} is injective
(ii)x
i
e
≡
y
i (mod N), ∀
i
∈
{
1
,
.
.
.
,
n
}
(iii)n
>
q
h
elsereturn 0;Definition 7 (The RSA Inversion Problem).
Given(
e
,
n
), where n is the product of two distinct large primes p and q with roughly the same length and e is a positive integer relatively-prime to (
p
-
1
)
(
q
-
1
), and a randomly-chosen positive integer y less than n, find an integer x such that x
e
≡
y
(
mod
⁡
n
).Definition 8 (E-Cash Unforgeability).
If there exists no probabilistic polynomial-time adversary who can win FG-1 or FG-2, thenD
A
O
E
C
S is secure against forgery attacks.Theorem 9.
For a polynomial-time adversaryA who can win FG-1 or FG-2 with nonnegligible probability, there exists another adversary S who can break the RSA-ACTI problem or RSA inversion problem with nonnegligible probability.Proof.
S simulates the environment and controls three hash oracles, O
H
1, O
H
2, O
H
3 and an e-cash producing oracle O
S of D
A
O
E
C
S scheme to respond to different queries from A in the random oracle model and takes advantage of A to solve RSA-ACTI problem or RSA inversion problem, simultaneously. Then, for consistency, S maintains three lists L
H
1, L
H
2, and L
H
3 to record every response of O
H
1, O
H
2, and O
H
3, respectively.
Here we will start to do the simulation for the two games (i.e., FG-1 and FG-2) to proveD
A
O
E
C
S is secure against forgery attacks. The details of simulation are set below and illustrated in Figures 6 and 7, respectively.
Simulation in FG-1. In this proof model, S is allowed to query the oracles O
inv (i.e., (
·
)
d) and O
t of RSA-ACTI problem defined in Definition 6 for helping S to produce e-cash(s) and the corresponding verifying key is (
e
,
n
).(i)
H
1 Query of O
H
1
Initially, every blank record inL
H
1 can be represented as (
⊥
,
⊥
,
⊥
). When A sends m for querying the hash value H
1
(
m
), S will check the list L
H
1:
(a)
ifm
=
m
i for some i, then S retrieves the corresponding H
1
(
m
i
) and returns it to A;
(b)
else ifm
=
H
1
(
m
i
) and H
1
2
(
m
i
)
≠
⊥ for some i, then S retrieves the corresponding H
1
2
(
m
i
) and returns it to A;
(c)
else ifm
=
H
1
(
m
i
) and H
1
2
(
m
i
)
=
⊥ for some i, then S queries O
t to get an instance y and returns it to A, then fills the record (
m
i
,
H
1
(
m
i
)
,
⊥
) as (
m
i
,
H
1
(
m
i
)
,
y
) in L
H
1;
(d)
otherwise,S selects a random ρ
∈
Z
n, records (
m
,
ρ
,
⊥
) in L
H
1, and returns ρ to A.
(ii)
H
2 Query of O
H
2
WhenA asks for H
2 query by sending D to S, S will look up the list L
H
2:
(a)
ifD
=
D
i for some i, the corresponding τ will be retrieved and S will send (τ
e
mod
⁡
n) back to A;
(b)
otherwise,S will select a random τ
∈
Z
n, record (
D
,
τ
) in L
H
2, and return (τ
e
mod
⁡
n) back to A.
(iii)
H
3 Query of O
H
3
WhileA sends (
σ
,
D
) to S for H
3
(
σ
∥
D
), S will look up the list L
H
3:
(a)
if(
σ
,
D
)
=
(
σ
i
,
D
i
) for some i, the corresponding η will be retrieved and (η
e
mod
⁡
n) will be returned to A;
(b)
otherwise,S will select a random η
∈
Z
n, record (
(
σ
,
D
)
,
η
) in L
H
3, and return (η
e
mod
⁡
n) back to A.
(iv)
E-Cash Producing Query ofO
S
WhenA sends (
α
,
ϵ
,
D
) to S, S will do the following steps:
(1)
decryptϵ, obtain (
k
,
ID
);
(2)
randomly selectr
j and prepare σ
=
E
^
p
k
j
(
ID
∥
r
j
);
(3)
chooseη
∈
R
Z
n, set H
3
(
σ
∥
D
)
=
(
η
e
mod
n
), and store (
(
σ
,
D
)
,
η
) in L
H
3;
(4)
selectb
∈
R
Z
n
* and compute β
=
(
b
e
η
e
)
-
1
mod
n;
(5)
retrieve or assignτ such that H
2
(
D
)
=
(
τ
e
) as the O
H
2 query described above;
(6)
send(
α
β
τ
e
) to oracle O
inv to get t
=
(
α
β
τ
e
)
d
mod
⁡
n;
(7)
return(
t
,
E
~
k
(
b
,
σ
,
r
j
)
) back to A.
Eventually, assume thatA can successfully output l
+
1 e-cash tuples
(17)
{
(
s
1
,
m
1
,
σ
1
,
D
1
)
⋯
(
s
l
+
1
,
m
l
+
1
,
σ
l
+
1
,
D
l
+
1
)
}
,
where m
i are all distinct, ∀
i
,
1
≤
i
≤
l
+
1, such that s
i
e
H
1
2
(
m
)
H
3
(
σ
i
∥
D
i
)
=
H
2
(
D
i
) (mod
⁡
n) after l times to query O
S with nonnegligible probability ϵ
A.
According toL
H
1, L
H
2, and L
H
3, S can compute and retrieve RSA-inversion instances (∀
i, 1
≤
i
≤
l
+
1)
(18)
(
y
i
)
d
≡
(
H
1
2
(
m
i
)
)
d
≡
s
i
-
1
(
H
3
(
σ
i
∥
D
i
)
-
1
H
2
(
D
i
)
)
d
≡
s
i
-
1
η
i
-
1
(
τ
i
)
(
mod
⁡
n
)
.
Via A querying the signing oracle O
S for l times (i.e., query O
inv for l times by S), S can output l
+
1 RSA-inversion instances
(19)
{
(
s
1
-
1
η
1
-
1
(
τ
1
)
,
y
1
)
,
(
s
2
-
1
η
2
-
1
(
τ
2
)
,
y
2
)
,
…
,
(
s
l
+
1
-
1
η
l
+
1
-
1
(
τ
l
+
1
)
,
y
l
+
1
)
h
(
s
l
+
1
-
1
η
l
+
1
-
1
(
τ
l
+
1
)
,
y
l
+
1
)
}
and break the RSA-ACTI problem with nonnegligible probability at least ϵ
A.
Simulation in FG-2. Initially, S is given an instance (
y
,
e
,
n
) of RSA inversion problem defined in Definition 7 and simulates the environment as follows. (i)
H
1 Query of O
H
1
Initially, every blank record inL
H
1 can be represented as (
⊥
,
⊥
,
⊥
). When A sends m for querying the hash value H
1
(
m
), S will check the list L
H
1:
(a)
ifm
=
m
i for some i, then S retrieves the corresponding ρ
i and returns it to A;
(b)
else ifm
=
H
1
(
m
i
) and H
1
2
(
m
i
)
≠
⊥ for some i, then S retrieves the corresponding ς and returns (ς
e
mod
⁡
n) to A;
(c)
else ifm
=
H
1
(
m
i
) and H
1
2
(
m
i
)
=
⊥ for some i, then S selects a random ς
∈
Z
n, returns (ς
e
mod
⁡
n) to A, and then fills the record (
m
i
,
H
1
(
m
i
)
,
⊥
) as (
m
i
,
H
1
(
m
i
)
,
ς
) in L
H
1;
(d)
otherwise,S selects a random ρ
∈
Z
n, records (
m
,
ρ
,
⊥
) in L
H
1, and returns ρ to A.
(ii)
H
2 Query of O
H
2
WhenA asks for H
2 query by sending D to S, S will look up the list L
H
2:
(a)
ifD
=
D
i for some i, the corresponding τ will be retrieved and S will send (τ
e
mod
⁡
n) back to A;
(b)
otherwise,S will select a random τ
∈
Z
n, record (
D
,
τ
) in L
H
2, and return (τ
e
mod
⁡
n) back to A.
(iii)
H
3 Query of O
H
3
WhileA sends (
σ
,
D
) to S for H
3
(
σ
∥
D
), S will look up the list L
H
3:
(a)
if(
σ
,
D
)
=
(
σ
i
,
D
i
) for some i, the corresponding H
3
(
σ
i
∥
D
i
) will be retrieved and returned to A;
(b)
otherwise,S will select a random η
∈
Z
n, set H
3
(
σ
∥
D
)
=
(
η
e
y mod n), record (
(
σ
,
D
)
,
η
,
H
3
(
σ
∥
D
)
) in L
H
3, and return H
3
(
σ
∥
D
) back to A.
(iv)
E-Cash Producing Query ofO
S
Letl
D
i be a counter to record the number of queries on each expiration date D
i, which is initialized by 0. When A sends (
α
,
ϵ
,
D
) to S, S will do the following steps:
(1)
decryptϵ, obtain (
k
,
ID
);
(2)
randomly selectr
j and prepare σ
=
E
^
p
k
j
(
ID
∥
r
j
);
(3)
chooseη
∈
R
Z
n, set H
3
(
σ
∥
D
)
=
(
α
η
e
mod
⁡
n
), and store (
(
σ
,
D
)
,
⊥
,
(
α
η
e
mod
⁡
n
)
) and (
σ
,
D
) in L
H
3 and L
x, respectively;
(4)
selectb
∈
R
Z
n
* and compute β
=
(
b
e
α
η
e
)
-
1
mod
⁡
n;
(5)
retrieve or assignτ such that H
2
(
D
)
=
(
τ
e
) as the O
H
2 query described above;
(6)
computet
≡
(
α
β
τ
e
)
d
≡
(
(
b
η
)
-
1
τ
) (mod
⁡
n);
(7)
setl
D
=
l
D
+
1 and return (
t
,
E
~
k
(
b
,
σ
,
r
j
)
) back to A.
Eventually, assume thatA can successfully output l
D
′
+
1 e-cash tuples for some expiration date D
′
(20)
{
(
s
1
,
m
1
,
σ
1
,
D
′
)
⋯
(
s
l
D
′
+
1
,
m
l
D
′
+
1
,
σ
l
D
′
+
1
,
D
′
)
}
such that s
i
e
H
1
2
(
m
i
)
H
3
(
σ
i
∥
D
′
)
=
H
2
(
D
′
) (mod
⁡
n), ∀
i
,
1
≤
i
≤
l
D
′
+
1, after l
D
′ times to query O
S on D
′, with nonnegligible probability ϵ
A.
Assume some(
σ
i
,
D
′
), 1
≤
i
≤
l
D
′
+
1, is not recorded in L
x; then by the L
H
1, L
H
2, and L
H
3, S can compute and retrieve
(21)
(
s
i
)
e
≡
(
H
1
2
(
m
i
)
H
3
(
σ
i
∥
D
′
)
)
-
1
H
2
(
D
′
)
≡
(
(
ς
i
e
)
(
η
i
e
y
)
)
-
1
(
τ
i
e
)
(
mod
⁡
n
)
,
x
≡
y
d
≡
(
s
i
ς
i
η
i
)
-
1
τ
i
(
mod
⁡
n
)
and solve the RSA inversion problem with nonnegligible probability at least ϵ
A.Figure 6
The proof model of FG-1.Figure 7
The proof model of FG-2.


## 4.3. E-Cash Conditional-Traceability

In this section, we will prove that the ID information embedded in e-cash(s) cannot be replaced or moved out by any user against being traced after some misbehavior or criminals. The details of our proof model are illustrated in Figure8.Figure 8
The proof model of TG.Definition 10 (Tampering Game (TG)).
Letl
k
∈
N be a security parameter and A be an adversary in D
A
O
E
C
S. O
S is an oracle which plays the role of bank in D
A
O
E
C
S to record parameters from the queries of A and issue e-cash(s) (i.e., (
s
,
m
,
σ
,
D
), where m
=
(
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
D
)) accordingly. A is allowed to query O
S for l times; consider Algorithm 4.
A wins the game if the probability Pr[
Ex
p
A
TG
(
k
)
=
1
] of A is nonnegligible.Algorithm 4
Experiment
E
x
p
A
TG
(
l
k
)
(
p
k
j
,
s
k
j
,
g
1
,
g
2
,
e
b
,
d
b
,
p
b
,
q
b
,
n
b
,
H
1
,
H
2
,
H
3
,
H
4
,
H
5
)
←
Setup
(
l
k
)
(
s
′
,
m
′
,
σ
′
,
D
′
)
←
A
O
S
(
p
k
T
A
,
e
R
,
n
R
,
H
1
,
H
2
)
{
σ
1
,
…
,
σ
l
}
←
O
S
if the following two checks are true,return 1;
(i)σ
′
∉
{
σ
1
,
…
,
σ
l
}
(ii)s
′
e
H
1
2
(
m
′
)
H
3
(
σ
′
∥
D
′
)
=
H
2
(
D
′
) mod n
elsereturn 0;Definition 11 (E-Cash Traceability).
If there exists no probabilistic polynomial-time adversary who can win the tracing game TG, thenD
A
O
E
C
S satisfies the E-Cash Traceability.Definition 12 (Alternative Formulation of RSA Known-Target  Inversion Problem (RSA-AKTI)).
Letk
∈
N be a security parameter and A be an adversary who is allowed to access the RSA-inversion oracle O
inv and the target oracle O
t. A is allowed to query O
t and O
inv for q
t and q
h times (q
h
<
q
t), respectively. Consider Algorithm 5.
We sayA breaks the RSA-AKTI problem if the probability Pr[
Ex
p
A
RSA-AKTI
(
k
)
=
1
] of A is nonnegligible.Algorithm 5
Experiment
E
x
p
A
RSA-AKTI
(
k
)
(
N
,
e
,
d
)
←
R
K
e
y
G
e
n
(
k
).
(
y
1
,
…
,
y
q
t
)
←
O
t
(
N
,
e
,
k
)
{
(
x
1
,
y
1
)
,
…
,
(
x
q
t
,
y
q
t
)
}
←
A
O
inv
,
O
t
(
N
,
e
,
k
)
ifx
i
e
≡
y
i (mod N), ∀
i
∈
{
1
,
…
,
q
t
}, return 1;
elsereturn 0;Theorem 13.
For a polynomial-time adversaryA who can win the tracing game TG with nonnegligible probability, there exists another adversary S who can break the RSA-AKTI problem with nonnegligible probability.Proof.
S simulates the environment of D
A
O
E
C
S by controlling three hash oracles, O
H
1, O
H
2, O
H
3, to respond hash queries and an e-cash producing oracle O
S of D
A
O
E
C
S to respond e-cash producing queries from A, respectively, in the random oracle model. Eventually, S will take advantage of A’s capability to solve RSA-AKTI problem. Then, for consistency, S maintains three lists L
H
1, L
H
2, and L
H
3 to record every response of O
H
1, O
H
2, and O
H
3, respectively.
Besides, in the proof model,S is allowed to query the oracles O
inv (i.e., (
·
)
d) and O
t of the RSA-AKTI problem defined in Definition 12 for helping S produce valid e-cash(s) and the corresponding verifying key is (
e
,
n
).
Here we will do the simulation for gameTG to prove that D
A
O
E
C
S satisfies the e-cash traceability. Details are described as follows.(i)
H
1 Query of O
H
1
Initially, every blank record inL
H
1 can be represented as (
⊥
,
⊥
,
⊥
). When A sends m for querying the hash value H
1
(
m
), S will check the list L
H
1:
(a)
ifm
=
m
i for some i, then S retrieves the corresponding H
1
(
m
i
) and return it to A;
(b)
else ifm
=
H
1
(
m
i
) and H
1
2
(
m
i
)
≠
⊥ for some i, then S retrieves the corresponding ς
i and returns (ς
i
e
mod
⁡
n) to A;
(c)
else ifm
=
H
1
(
m
i
) and H
1
2
(
m
i
)
=
⊥ for some i, then S chooses ς
∈
R
Z
n, sets H
1
2
(
m
i
)
=
(
ς
e
mod
⁡
n), and returns H
1
2
(
m
i
) to A then fills the original record (
m
i
,
H
1
(
m
i
)
,
⊥
) as (
m
i
,
H
1
(
m
i
)
,
ς
) in L
H
1;
(d)
otherwise,S selects a random ρ
∈
Z
n, sets H
1
(
m
i
)
=
ρ, records (
m
,
H
1
(
m
i
)
,
⊥
) in L
H
1, and returns ρ to A.
(ii)
H
2 Query of O
H
2
WhenA asks for H
2 query by sending D to S, S will look up the list L
H
2:
(a)
ifD
=
D
i for some i, the corresponding τ will be retrieved and S will send (τ
e
mod
⁡
n) back to A;
(b)
otherwise,S will select a random τ
∈
Z
n, record (
D
,
τ
) in L
H
2, and return (τ
e
mod
⁡
n) back to A.
(iii)
H
3 Query of O
H
3
WhileA sends (
σ
,
D
) to S for H
3
(
σ
), S will look up the list L
H
3:
(a)
if(
σ
,
D
)
=
(
σ
i
,
D
i
) for some i, the corresponding y
i will be retrieved and returned to A;
(b)
otherwise,S will query O
t to get an instance y; record y and (
(
σ
,
D
)
,
y
) in L
T and L
H
3, respectively;
(c)
returny back to A.
(iv)
E-Cash Producing Query ofO
S
WhileA sends (
α
,
ϵ
,
D
) to S, S will do the following steps:
(1)
decryptϵ, obtain (
k
,
ID
);
(2)
randomly selectr
j and prepare σ
=
E
^
p
k
j
(
ID
∥
r
j
);
(3)
chooseη
∈
R
Z
n, set H
3
(
σ
∥
D
)
=
(
α
η
e
mod
⁡
n
), and store (
(
σ
,
D
)
,
H
3
(
σ
∥
D
)
) in L
H
3;
(4)
selectb
∈
R
Z
n
* and compute β
=
(
b
e
α
η
e
)
-
1
mod
⁡
n;
(5)
retrieve or assignτ such that H
2
(
D
)
=
(
τ
e
) as the O
H
2 query described above;
(6)
computet
≡
(
α
β
τ
e
)
d
≡
(
(
b
η
)
-
1
τ
) (mod
⁡
n);
(7)
return(
t
,
E
~
k
(
b
,
σ
,
r
j
)
) back to A.
Assume thatA can successfully output an e-cash tuples (
s
′
,
m
′
,
σ
′
,
D
′
), where σ
′ never appeals as a part for some O
S query such that s
′
e
H
1
2
(
m
′
)
H
3
(
σ
′
∥
D
′
)
≡
H
2
(
D
′
) (mod
⁡
n); then by L
H
1, L
H
2, and L
H
3, S can derive
(22)
(
y
′
)
d
≡
(
H
3
(
σ
′
∥
D
′
)
)
d
≡
s
′
-
1
(
H
1
2
(
m
′
)
-
1
H
2
(
D
′
)
)
d
≡
s
′
-
1
ς
′
-
1
τ
′
(
mod
⁡
n
)
.
Let |
L
T
|
=
q
t and L
T
=
{
y
1
,
…
,
y
q
t
}. S sends y
i
∈
(
L
T
-
{
y
′
}
), 1
≤
i
≤
(
q
t
-
1
), to O
inv and obtains q
t
-
1
x
i such that x
i
=
y
i
d
mod
⁡
n.
EventuallyS can output q
t RSA-inversion instances
(23)
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
…
,
(
x
q
t
-
1
,
y
q
t
-
1
)
,
(
(
s
′
-
1
ς
′
-
1
τ
′
)
,
y
′
)
}
after querying O
inv for q
h times, where q
h
=
q
t
-
1
<
q
t and thus, it breaks the RSA-AKTI problem with nonnegligible probability at least ϵ
A.


## 4.4. E-Cash No-Swindling

In typical online e-cash transactions, when an e-cash has been spent in previous transactions, another spending will be detected immediately owing to the double-spending check procedure. However, in an offline e-cash model, the merchant may accept a transaction involving a double-spent e-cash first and then do the double-spending check later. In this case, the original owner of the e-cash may suffer from loss. Therefore, a secure offline e-cash scheme should guarantee the following two events.(i)
No one, except the real owner, can spend a fresh and valid offline e-cash successfully.
(ii)
No one can double spend an e-cash successfully.Roughly, it can be referred to ase-cash no-swindling property. In this section, we will define the no-swindling property and formally prove that our scheme is secure against swindling attacks.Definition 14 (Swindling Game inD
A
O
E
C
S).
Letl
k
∈
N be a security parameter and A be an adversary in D
A
O
E
C
S. O
B is an oracle issuing generic e-cash(s) (i.e., (
s
,
y
1
,
w
1
,
x
2
,
r
2
,
r
3
,
σ
,
D
)) of D
A
O
E
C
S to A. O
off
⁡ is an oracle to show the expanding form (
s
,
y
1
,
w
1
,
x
2
,
r
2
,
r
3
,
σ
,
D
,
r
s
,
s
′
) for the payment according to the input (
s
,
m
,
σ
,
D
). Consider the two experiments SWG-1 and SWG-2 shown in Algorithms 6 and 7, respectively.
A wins the game if the probability Pr[
Ex
p
A
SWG-
1
(
l
k
)
=
1
] or Pr[
Ex
p
A
SWG-
2
(
l
k
)
=
1
] of A is nonnegligible.Algorithm 6:Experiment SWG-1.
Experiment
E
x
p
A
SWG-
1
(
l
k
)
(
p
k
j
,
s
k
j
,
g
1
,
g
2
,
e
b
,
d
b
,
p
b
,
q
b
,
n
b
,
p
,
q
,
H
1
,
H
2
,
H
3
,
H
4
,
H
5
)
←
Setup
(
l
k
)
{
(
s
,
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
σ
,
D
,
r
u
,
r
s
,
s
′
)
}
←
A
O
B
,
O
off
⁡
(
p
k
j
,
g
1
,
g
2
,
e
b
,
n
b
,
p
,
q
,
H
1
,
H
2
,
H
3
,
H
4
,
H
5
)
if the following checks are true,return 1;
(i) s
e
b
H
1
2
(
y
H
4
(
r
u
∥
r
s
)
g
s
′
mod
⁡
p
∥
y
1
∥
w
2
∥
y
2
∥
D
∥
r
3
)
H
3
(
σ
∥
D
)
=
H
2
(
D
) mod n
b;
(ii) (
s
,
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
σ
,
D
) never be a query to O
off
⁡
elsereturn 0;Algorithm 7:Experiment SWG-2.
Experiment
E
x
p
A
SWG-
2
(
l
k
)
(
p
k
j
,
s
k
j
,
g
1
,
g
2
,
e
b
,
d
b
,
p
b
,
q
b
,
n
b
,
p
,
q
,
H
1
,
H
2
,
H
3
,
H
4
,
H
5
)
←
Setup
(
l
k
)
{
(
s
,
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
σ
,
D
,
r
u
,
r
s
,
s
′
)
}
←
A
O
B
,
O
off
⁡
(
p
k
j
,
g
1
,
g
2
,
e
b
,
n
b
,
p
,
q
,
H
1
,
H
2
,
H
3
,
H
4
,
H
5
)
if the following checks are true,return 1;
(i)s
e
b
H
1
2
(
y
H
4
(
r
u
∥
r
s
)
g
s
′
mod
⁡
p
∥
y
1
∥
w
2
∥
y
2
∥
D
∥
r
3
)
H
3
(
σ
∥
D
)
=
H
2
(
D
) mod n
b;
(ii)(
s
,
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
σ
,
D
) is allowed to be queried to O
off
⁡ for once;
(iii)(
s
,
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
σ
,
D
,
r
s
,
s
′
) is not obtained from O
off
⁡
elsereturn 0;Definition 15 (E-Cash No-Swindling).
If there exists no probabilistic polynomial-time adversary who can win the swindling game defined in Definition14, then D
A
O
E
C
S satisfies e-cash no-swindling.Theorem 16.
For a polynomial-time adversaryA who can win the swindling game SWG with nonnegligible probability, there exists another adversary S who can solve the discrete logarithm problem with nonnegligible probability.Proof.
Consider the swindling game defined in Definition14. S simulates the environment by controlling the hash oracles, O
H
4, to respond hash queries on H
4 of D
A
O
E
C
S in the random oracle model. Eventually, S will take advantage of A’s capability to solve the discrete logarithm problem. Then, for consistency, S maintains a list L
H
4 to record every response of O
H
4. S is given all parameters (
p
k
j
,
s
k
j
,
g
1
,
g
2
,
e
b
,
d
b
,
p
b
,
q
b
,
n
b
,
p
,
q
,
H
1
,
H
2
,
H
3
,
H
4
,
H
5
) of D
A
O
E
C
S and an instance y
* of discrete logarithm problem (i.e., y
*
=
g
x
*
mod
⁡
p). Here we will describe the simulations for the two experiments Exp
A
SWG-
1 and Exp
A
SWG-
2, individually.
The simulation forExp
A
SWG-
1 is illustrated in Figure 9 and each oracle is constructed as follows.(i)
OracleO
B
Initially,S guesses that the generic e-cash produced from νth query will be the attack target. When A sends ith query to O
B for an e-cash, O
B will do the following:
(a)
selectr
1, x
1, r
3
∈
R
Z
q and y
2, w
2
∈
R
Z
p;
(b)
ifi
=
ν,
(1)
compute (w
1
=
(
y
*
)
r
1
mod
⁡
p) and (y
1
=
g
x
1
mod
⁡
p);
(c)
ifi
≠
ν,
(1)
compute (w
1
=
g
r
1
mod
⁡
p) and (y
1
=
g
x
1
mod
⁡
p);
(d)
prepares
=
(
(
H
1
2
(
m
)
H
3
(
σ
∥
D
)
)
-
1
H
2
(
D
)
)
d
b
mod
⁡
n
b, where m
=
(
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
D
);
(e)
record(
i
,
(
s
,
m
,
σ
,
D
)
,
(
r
1
,
x
1
)
)
) in list L
B and return (
s
,
m
,
σ
,
D
) to A.
(ii)
OracleO
off
⁡
WhenA sends a valid e-cash tuple (
s
,
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
σ
,
D
,
r
s
) to O
off
⁡, it will look up the list L
B:
(a)
if(
s
,
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
σ
,
D
) exists with prefix index ν, then abort;
(b)
otherwise,O
off
⁡ will retrieve the corresponding (
r
1
,
x
1
); choose a random r
u, compute u
=
H
4
(
r
u
∥
r
s
) and (s
′
=
r
1
-
u
x
1
mod
⁡
q), and send (
s
,
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
σ
,
D
,
r
u
,
r
s
,
s
′
) back to A.
Assume thatA can successfully output a valid offline e-cash expansion tuple (
s
*
,
w
1
*
,
y
1
*
,
w
2
*
,
y
2
*
,
r
3
*
,
σ
*
,
D
*
,
r
u
*
,
r
s
*
,
s
′
*
), where (
s
*
,
w
1
*
,
y
1
*
,
w
2
*
,
y
2
*
,
r
3
*
,
σ
*
,
D
*
) is prefixed with ν and postfixed with (
r
1
*
,
x
1
*
) in L
B. Then, since w
1
*
=
y
1
*
H
4
(
r
u
*
∥
r
s
*
)
g
s
′
*
mod
⁡
p and w
1
*
=
(
y
*
)
r
1
*, S can derive
(24)
x
*
=
(
r
1
*
)
-
1
(
x
1
*
H
4
(
r
u
*
∥
r
s
*
)
+
s
′
*
)
mod
⁡
q
and solve the discrete logarithm problem with nonnegligible probability at least (
1
/
q
O
B
)
ϵ
A, where q
O
B is the total number of O
B query.
The simulation forExp
A
SWG-
2 is illustrated in Figure 10 and each oracle is constructed as follows.(i)
OracleO
B
Initially,S guesses that the generic e-cash produced from νth query will be the attack target. When A sends ith query to O
B for an e-cash, O
B will do the followings.
(a)
ifi
=
ν:
(1)
selects
′, u, x
1, r
3
∈
R
Z
q and y
2, w
2
∈
R
Z
p;
(2)
compute (y
1
=
(
y
*
)
x
1
mod
⁡
p) and (w
1
=
y
1
u
g
s
′
mod
⁡
p);
(3)
prepares
=
(
(
H
1
2
(
m
)
H
3
(
σ
∥
D
)
)
-
1
H
2
(
D
)
)
d
b
mod
⁡
n
b, where m
=
(
w
1, y
1, w
2, y
2, r
3, D
);
(4)
record(
i
,
(
s
,
m
,
σ
,
D
)
,
(
u
,
s
′
)
)
) in list L
B;
(b)
ifi
≠
ν:
(1)
selectr
1, x
1, r
3
∈
R
Z
q and y
2, w
2
∈
R
Z
p;
(2)
compute (w
1
=
g
r
1
mod
⁡
p) and (y
1
=
g
x
1
mod
⁡
p);
(3)
prepares
=
(
(
H
1
2
(
m
)
H
3
(
σ
∥
D
)
)
-
1
H
2
(
D
)
)
d
b
mod
⁡
n
b, where m
=
(
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
D
);
(4)
record(
i
,
(
s
,
m
,
σ
,
D
)
,
(
r
1
,
x
1
)
)
) in list L
B;
(c)
return(
s
,
m
,
σ
,
D
) to A.
(ii)
OracleO
off
⁡
A status parametersta is initialized by 0. When A sends a valid e-cash tuple (
s
,
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
σ
,
D
,
r
s
) to O
off
⁡, it will look up the list L
B:
(a)
if(
s
,
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
σ
,
D
) exists with prefix index ν and sta
=
0, O
off
⁡ will perform the following procedures:
(1)
setsta
=
1
(2)
retrieve the corresponding(
u
,
s
′
) from L
B and choose a random r
u;
(3)
setH
4
(
r
u
∥
r
s
)
=
u and record (
(
r
u
∥
r
s
)
,
u
) in L
H;
(4)
record(
s
,
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
σ
,
D
,
r
u
,
r
s
,
s
′
) in list L
off
⁡;
(5)
send(
s
,
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
σ
,
D
,
r
u
,
r
s
,
s
′
) back to A;
(b)
if(
s
,
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
σ
,
D
) exists with prefix index ≠
ν, O
off
⁡ will retrieve the corresponding (
r
1
,
x
1
), choose random r
u and u, set H
4
(
r
u
∥
r
s
)
=
u, record (
(
r
u
∥
r
s
)
,
u
) in L
H, compute (s
′
=
r
1
-
u
x
1
mod
⁡
q), and send (
s
,
w
1
,
y
1
,
w
2
,
y
2
,
r
3
,
σ
,
D
,
r
u
,
r
s
,
s
′
) back to A.
(c)
Otherwise, abort.
(iii)
OracleO
H
4
WhileA sends (
r
u
∥
r
s
) to query for H
4
(
r
u
∥
r
s
), O
H
4 will check the list L
H:
(a)
if(
r
u
∥
r
s
) exists as the prefix of some record, O
H
4 will retrieve the corresponding u and return it to A;
(b)
otherwise,O
H
4 will choose a random u, record (
(
r
u
∥
r
s
)
,
u
) in L
H, and return u to A.
Assume thatA can successfully output a valid offline e-cash expansion tuple (
s
*
,
w
1
*
,
y
1
*
,
w
2
*
,
y
2
*
,
r
3
*
,
σ
*
,
D
*
,
r
u
*
,
r
s
*
,
s
′
*
), where (
s
*
,
w
1
*
,
y
1
*
,
w
2
*
,
y
2
*
,
r
3
*
,
σ
*
,
D
*
) is prefixed with ν and postfixed with (
u
,
s
′
) in L
B and H
4
(
r
u
*
∥
r
s
*
)
≠
u.
Then, viaL
H, since
(25)
(
y
*
x
1
*
)
u
*
g
s
′
*
≡
(
y
1
*
)
H
4
(
r
u
*
∥
r
s
*
)
g
s
′
*
≡
w
1
*
≡
(
y
*
x
1
*
)
u
g
s
′
(
mod
⁡
p
)
,
S can derive
(26)
x
*
=
(
x
1
*
(
u
*
-
u
)
)
-
1
(
s
′
-
s
′
*
)
mod
⁡
q
and solve the discrete logarithm problem with nonnegligible probability at least (
1
/
q
O
B
)
ϵ
A, where q
O
B is the total number of O
B query.Figure 9
The proof model of SWG-1.Figure 10
The proof model of SWG-2.Summarize the proof models for the two experiments shown above, if there exists a polynomial-time adversary who can win the swindling game with nonnegligible probability, then there exists another one who can solve the discrete logarithm problem with nonnegligible probability. It implies that there exists no p.p.t. adversary who can win the swindling game, and our proposed offline e-cash schemeD
A
O
E
C
S satisfies no-swindling property.


## 5. E-Cash Advanced Features and Performance Comparisons

In this section, we compare the e-cash features and performance of our proposed scheme with other schemes given in [9, 13–15, 21, 22, 27, 38–40]. We analyze the features and performance of the aforementioned schemes and form a table (Table 1) for the summary.Table 1
Advanced features and performance comparisons.
Ours
[38]
[14]
[15]
[9]
[21]
[22]
[39]
[40]
[13]
[27]
Advanced features
On/off-line
Off
Off
Off
Off
On
Off
Off
Off
Off
On
Off
Conditional-traceability
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes
Yes
No
Date attachability
Yes
No
No
No
Yes
Yes
No
No
No
No
Yes
No-swindling
Yes
No
No
No
—
No
Yes
No
No
—
No
Renewal protocol
Yes
—
Yes
—
No
Yes
Yes
—
—
—
Yes
Formal proof
Yes
Yes
No
Yes
No
No
Yes
Yes
Yes
Yes
No
Performance
Transaction cost⋆
5
E
+
7
M   +
7
H
+
1
inv   +
1
A   ≈
1454
M
14
E
+
14
M   +
1
H
+
5
A   ≈
3375
M
6
E
+
8
M   ≈
1448
M
23
E
+
14
M   +
1
A   ≈
5534
M
2
E
+
2
M   +
2
H   ≈
966
M
5
E
+
9
M
+
1
H
+
1
inv
+
2
A
≈
1450
M
2
E
≈
480
M
18
E
+
15
M
+
2
H
+
8
A
≈
4337
M
31
E
+
22
M
+
6
H
+
10
A
≈
7468
M
22
E
+
11
M   +
4
A   ≈
5291
M
6
E
+
8
M   +
1
H    ≈
1449
M
Communication cost⋄
1092
576
1288
939
769
644
300
828
968
1536
728
According to [41], H
≈
M
,
E
≈
inv
≈
240
M.
E: a modular exponentiation; M: a modular multiplication; H: a hash operation; zkp: a zero-knowledge proof.
A: a modular addition; inv: a modular inversion.
⋆The computation cost of withdrawal and payment protocols at user side.
⋄The communication cost of each transaction at user side in bytes.


### 5.1. Features Comparisons

All the schemes mentioned above fulfill the basic security requirements stated in Section1, which are anonymity, unlinkability, unforgeability, and no double-spending. Besides these features, there can be other advanced features on an e-cash system discussed in the literatures. We focus on three other advanced features, which are traceability, date attachability, and no-swindling, and we compare the proposed scheme with the aforementioned schemes.We also propose an e-cash renewal protocol for users to exchange a new valid e-cash with their unused but expired e-cash(s); therefore, users do not have to deposit the e-cash before it expires and withdraw a new e-cash again. Our proposed e-cash renewal protocol reduces the computation cost by 49.5% as compared to withdrawal and deposit protocols, which is almost half of the effort of getting a new e-cash, at the user side. It does a great help to the users since their devices usually have a weaker computation capability, such as smart phones.


### 5.2. Performance Comparisons

According to [41], we can summarize and induce the computation cost of all operations as follows. The computation cost of a modular exponentiation computation is about 240 times of the computation cost of a modular multiplication computation, while the computation cost of a modular inversion almost equals to that of a modular exponentiation. Also, the computation cost of a hash operation almost equals to that of a modular multiplication.With the above assumptions, the total computation cost of users during withdrawal and payment phases of our proposed scheme can be induced as 1452 times of a modular multiplication computation, while other works [9, 13–15, 21, 22, 27, 38–40] need 3375, 1448, 5534, 966, 1450, 480, 4337, 7468, 5291, and 1449 times of a modular multiplication computation to finish withdrawal and payment phases at the user ends.According to [15], we assume the RSA parameters n
,
p
,
q are 1024, 512, and 512 bits, respectively. We adopt AES and SHA-1 as the symmetric cryotsystem and one-way hash function used in all protocols, respectively; therefore, the signed message and hash massage are in 128 and 160 bits, respectively. We assume the expiration date is in 32 bits.With the above assumptions, we compute the communication cost of each offline transaction, withdrawal, and payment, at the user side. Our scheme needs 2048 bits for withdrawing an e-cash and 6688 bits for spending an e-cash, which is 1092 bytes for each transaction.The details of the comparisons are summarized in Table1.


## 5.1. Features Comparisons

All the schemes mentioned above fulfill the basic security requirements stated in Section1, which are anonymity, unlinkability, unforgeability, and no double-spending. Besides these features, there can be other advanced features on an e-cash system discussed in the literatures. We focus on three other advanced features, which are traceability, date attachability, and no-swindling, and we compare the proposed scheme with the aforementioned schemes.We also propose an e-cash renewal protocol for users to exchange a new valid e-cash with their unused but expired e-cash(s); therefore, users do not have to deposit the e-cash before it expires and withdraw a new e-cash again. Our proposed e-cash renewal protocol reduces the computation cost by 49.5% as compared to withdrawal and deposit protocols, which is almost half of the effort of getting a new e-cash, at the user side. It does a great help to the users since their devices usually have a weaker computation capability, such as smart phones.


## 5.2. Performance Comparisons

According to [41], we can summarize and induce the computation cost of all operations as follows. The computation cost of a modular exponentiation computation is about 240 times of the computation cost of a modular multiplication computation, while the computation cost of a modular inversion almost equals to that of a modular exponentiation. Also, the computation cost of a hash operation almost equals to that of a modular multiplication.With the above assumptions, the total computation cost of users during withdrawal and payment phases of our proposed scheme can be induced as 1452 times of a modular multiplication computation, while other works [9, 13–15, 21, 22, 27, 38–40] need 3375, 1448, 5534, 966, 1450, 480, 4337, 7468, 5291, and 1449 times of a modular multiplication computation to finish withdrawal and payment phases at the user ends.According to [15], we assume the RSA parameters n
,
p
,
q are 1024, 512, and 512 bits, respectively. We adopt AES and SHA-1 as the symmetric cryotsystem and one-way hash function used in all protocols, respectively; therefore, the signed message and hash massage are in 128 and 160 bits, respectively. We assume the expiration date is in 32 bits.With the above assumptions, we compute the communication cost of each offline transaction, withdrawal, and payment, at the user side. Our scheme needs 2048 bits for withdrawing an e-cash and 6688 bits for spending an e-cash, which is 1092 bytes for each transaction.The details of the comparisons are summarized in Table1.


## 6. Conclusion

In this paper, we have presented earlier a provably secure offline electronic cash scheme with an expiration date and a deposit date attached to it. Besides, we have also designed an e-cash renewal protocol, where users can exchange their unused and expired e-cash(s) for new ones more efficiently. Compared with other similar works, our scheme is efficient from the aspect of considering computation cost of the user side and satisfying all security properties, simultaneously. Except for anonymity, unlinkability, unforgeability, and no double-spending, we also formally prove that our scheme achieves conditional-traceability and no-swindling. Not only does our scheme help the bank to manage their huge databases against unlimited growth, but also it strengthens the preservation of users’ privacy and rights as well.



---

*Source: 216973-2014-05-18.xml*