# Secure Electronic Cash Scheme with Anonymity Revocation

Authors: Baoyuan Kang; Danhui Xu
Journal: Mobile Information Systems
 (2016)

---

## Abstract

In a popular electronic cash scheme, there are three participants: the bank, the customer, and the merchant. First, a customer opens an account in a bank. Then, he withdraws ane-cash from his account and pays it to a merchant. After checking the electronic cash’s validity, the merchant accepts it and deposits it to the bank. There are a number of requirements for an electronic cash scheme, such as, anonymity, unforgeability, unreusability, divisibility, transferability, and portability. Anonymity property of electronic cash schemes can ensure the privacy of payers. However, this anonymity property is easily abused by criminals. In 2011, Chen et al. proposed a novel electronic cash system with trustee-based anonymity revocation from pairing. On demand, the trustee can disclose the identity for e-cash. But, in this paper we point out that Chen et al.’s scheme is subjected to some drawbacks. To contribute secure electronic cash schemes, we propose a new offline electronic cash scheme with anonymity revocation. We also provide the formally security proofs of the unlinkability and unforgeability. Furthermore, the proposed scheme ensures the property of avoiding merchant frauds.


---

## Body

## 1. Introduction

Due to the fast progress of computer networks and Internet, information technology is used in electronic commerce. Many electronic commerce services can be found over the internet. So, an electronic payment mechanism is necessary for electronic commerce. And electronic payment is one of the key issues of electronic commerce development. To realize the digitalization of traditional cash and electronic payment, in 1983, Chaum suggested the first electronic cash scheme [1]. Popularly, in an electronic cash scheme, there are three participants: the bank, the customer, and the merchant. First, a customer opens an account in a bank. Then, he withdraws an e-cash from his account and pays it to a merchant. After checking the electronic cash’s validity, the merchant accepts it and deposits it to the bank. For security and efficiency, there are a number of requirements for an electronic cash scheme, such as anonymity, unforgeability, unreusability, divisibility, transferability, and portability [2]. Some of them are listed below.Anonymity/Unlinkability. The customer of the cash must be anonymous. As long as the coin is spent legitimately, neither the merchant nor the bank can identify the customer of the coin.Unforgeability. Only authorized banks can generate electronic cash.Unreusability. The electronic cash cannot be reused. The scheme can detect the malicious customer, who spends the cash twice.Electronic cash schemes can be divided into two categories: online and offline. In online schemes, as paying a coin to a merchant, the bank must attend to validate the coin and detect its reuse. But, in offline schemes, double spending can only be figured out when the merchant deposits the coin to the bank in the next phase. After Chaum’s scheme, a lot of electronic cash schemes [3–9] have been proposed based on blind signatures and restrictive blind signatures. Afterward, many more complex schemes have been proposed [10–13]. Recently, Eslami and Talebi proposed an untraceable electronic cash scheme [2] and claimed that their scheme satisfies all main security requirements, such as anonymity, unreusability, and date attachability. However, Baseri et al. [14] showed that Eslami and Talebi’s scheme is subjected to some weaknesses in perceptibility of double spender, unforgeability, and date attachability. Baseri et al. also contributed a novel electronic cash scheme.Untraceable electronic cash is an attractive payment tool for electronic commerce because its anonymity property can ensure the privacy of payers. However, this anonymity property is easily abused by criminals. In 2011, Chen et al. [15] proposed an electronic cash system with trustee-based anonymity revocation from pairing. On demand, the trustee can disclose the identity of the owner of an e-cash. Chen et al. claimed that their scheme is the first attempt to incorporate mutual authentication and key agreement into e-cash protocols and their scheme satisfies the security requirements of untraceability, verifiability, unforgeability, and anonymity revocation. But, in 2012, Chang [16] claimed that he finds some weaknesses of Chen et al.’s scheme. Then, Chen et al. [17] immediately provided a response to rebut Chang’s attacks. By thoroughly investigating Chen et al.’s scheme, we find that, despite Chang’s attacks being really wrong, Chen et al.’s scheme is surely insecure. Chen et al.’s scheme is subjected to some drawbacks. (1) The first flaw is the attack on the unforgeability by the dishonest customer. (2) The second flaw is the attack on double spending owner tracing. (3) The third flaw is the potential bank attack.To contribute secure electronic cash schemes, we propose a new offline electronic cash scheme with anonymity revocation. Furthermore, the proposed scheme ensures the property of avoiding merchant frauds.The remainder of this paper is organized as follows. Related concept of bilinear pairing and CDH problem are introduced in Section2. In Section 3, we show some weaknesses of Chen et al.’s scheme. In Section 4 we propose a new electronic cash scheme with anonymity revocation. In Section 5 we show the verifiability of the proposed scheme. Double spender detection is covered in Section 6. In Section 7 we show that the proposed scheme satisfies uncheatability of merchants. Provable security of our scheme is covered in Section 8. In Section 9 we compare our scheme with the others. Finally conclusions are given in Section 10.


## 2. Preliminary

### 2.1. The Bilinear Pairing

LetG1 be a cyclic additive group generated by P, whose order is a prime q, and let G2 be a cyclic multiplicative group of the same order. Let e:G1×G1→G2 be a pairing map which satisfies the following conditions:(1)
Bilinearity: for anyP,Q,R∈G1, we have e(P+Q,R)=e(P,R)e(Q,R).In particular, for anya,b∈Zq, e(aP,bP)=e(P,abP)=e(abP,P)=e(P,P)ab.(2)
Nondegeneracy: there existsP,Q∈G1, such that e(P,Q)≠1.(3)
Computability: there is an efficient algorithm to computee(P,Q) for all P,Q∈G1.


### 2.2. The CDH Problem

LetG be a cyclic additive group of prime order q and P a generator of G. The computational Diffie-Hellman (CDH) problem is to compute abP for given P,aP,bP∈G.


## 2.1. The Bilinear Pairing

LetG1 be a cyclic additive group generated by P, whose order is a prime q, and let G2 be a cyclic multiplicative group of the same order. Let e:G1×G1→G2 be a pairing map which satisfies the following conditions:(1)
Bilinearity: for anyP,Q,R∈G1, we have e(P+Q,R)=e(P,R)e(Q,R).In particular, for anya,b∈Zq, e(aP,bP)=e(P,abP)=e(abP,P)=e(P,P)ab.(2)
Nondegeneracy: there existsP,Q∈G1, such that e(P,Q)≠1.(3)
Computability: there is an efficient algorithm to computee(P,Q) for all P,Q∈G1.


## 2.2. The CDH Problem

LetG be a cyclic additive group of prime order q and P a generator of G. The computational Diffie-Hellman (CDH) problem is to compute abP for given P,aP,bP∈G.


## 3. Effective Attacks on Chen et al.’s Scheme

In this section, we show the drawbacks of Chen et al.’s scheme [15]. For the sake of brevity, we omit the review of Chen et al.’s scheme. To know Chen et al.’s scheme in detail, readers can read literature [15].


### 3.1. Attack on the Unforgeability by the Dishonest Customer

When the customer obtains ane-cash {CNO,LST,(R,S)}, he can randomly select a∈Zq∗ and forge e-cash {CNO,a·LST,(a·R,a·S)}, because the e-cash {CNO,LST,(R,S)} satisfies(1)eS,P=eH3CNOQB,R·eLST·QB,Ppub.So,(2)eS,Pa=eH3CNOQB,Ra·eLST·QB,Ppuba.Then,(3)ea·S,P=eH3CNOQB,a·R·ea·LST·QB,Ppub.That is to say, the customer forges a valid e-cash {CNO,a·LST,(a·R,a·S)}.Of course, in payment protocol, when the merchant gets ane-cash from customers, he also can similarly forge e-cash. Further, these forged e-cash make the scheme fail in double spending owner tracing, because it is impossible to find the customer identity from a·LST.Note that(R,S) is a signature on CNO and LST. Furthermore, CNO does not play distinction function to an e-cash. CNO is only a randomly selected number. Any customer can randomly choose any CNO for their e-cash. If CNO has some function, it is only to certain customer. It is not strange that different customers may choose same CNO for their e-cash. So, this attack is a successful forgery.


### 3.2. Attack by the Dishonest Merchant

In practice, there are always many merchants from different shops. After receiving ane-cash {CNO,LST,(R,S)} from a customer, the merchant may spend {CNO,LST,(R,S)} to another merchant. This attack is correct due to the fact that the verification equation (4)eS,P=eH3CNO·QB,R·eLST·QB,Ppubis only related to CNO,LST,R,S. And no extra information should be provided by customers in the verification process. Later, even if the bank finds double spending, the bank and the trustee cannot find real double spender, because the double spender may not be the customer himself.


### 3.3. Potential Attack by the Bank

However, in payment protocol, the only verification to thee-cash {CNO,LST,(R,S)} is to examine whether the following equation holds:(5)eS,P=eH3CNO·QB,R·eLST·QB,Ppub.But, when let R=aPpub (a is a randomly selected number in Zq∗) in the above equation, then(6)eS,P=eH3CNO·QB,aPpub·eLST·QB,Ppub=ea·H3CNO·QB,Ppub·eLST·QB,Ppub=ea·H3CNO+LST·QB,Ppub=ea·H3CNO+LST·SB,P.So, the bank can randomly select CNO and LST. Then Let R=aPpub, S=(a·H3(CNO)+LST)·SB to generate an e-cash {CNO,LST,(R,S)}.This apparently violates the withdrawal protocol above the customer and the bank together performing a blind signature function to complete thee-cash withdrawal.


## 3.1. Attack on the Unforgeability by the Dishonest Customer

When the customer obtains ane-cash {CNO,LST,(R,S)}, he can randomly select a∈Zq∗ and forge e-cash {CNO,a·LST,(a·R,a·S)}, because the e-cash {CNO,LST,(R,S)} satisfies(1)eS,P=eH3CNOQB,R·eLST·QB,Ppub.So,(2)eS,Pa=eH3CNOQB,Ra·eLST·QB,Ppuba.Then,(3)ea·S,P=eH3CNOQB,a·R·ea·LST·QB,Ppub.That is to say, the customer forges a valid e-cash {CNO,a·LST,(a·R,a·S)}.Of course, in payment protocol, when the merchant gets ane-cash from customers, he also can similarly forge e-cash. Further, these forged e-cash make the scheme fail in double spending owner tracing, because it is impossible to find the customer identity from a·LST.Note that(R,S) is a signature on CNO and LST. Furthermore, CNO does not play distinction function to an e-cash. CNO is only a randomly selected number. Any customer can randomly choose any CNO for their e-cash. If CNO has some function, it is only to certain customer. It is not strange that different customers may choose same CNO for their e-cash. So, this attack is a successful forgery.


## 3.2. Attack by the Dishonest Merchant

In practice, there are always many merchants from different shops. After receiving ane-cash {CNO,LST,(R,S)} from a customer, the merchant may spend {CNO,LST,(R,S)} to another merchant. This attack is correct due to the fact that the verification equation (4)eS,P=eH3CNO·QB,R·eLST·QB,Ppubis only related to CNO,LST,R,S. And no extra information should be provided by customers in the verification process. Later, even if the bank finds double spending, the bank and the trustee cannot find real double spender, because the double spender may not be the customer himself.


## 3.3. Potential Attack by the Bank

However, in payment protocol, the only verification to thee-cash {CNO,LST,(R,S)} is to examine whether the following equation holds:(5)eS,P=eH3CNO·QB,R·eLST·QB,Ppub.But, when let R=aPpub (a is a randomly selected number in Zq∗) in the above equation, then(6)eS,P=eH3CNO·QB,aPpub·eLST·QB,Ppub=ea·H3CNO·QB,Ppub·eLST·QB,Ppub=ea·H3CNO+LST·QB,Ppub=ea·H3CNO+LST·SB,P.So, the bank can randomly select CNO and LST. Then Let R=aPpub, S=(a·H3(CNO)+LST)·SB to generate an e-cash {CNO,LST,(R,S)}.This apparently violates the withdrawal protocol above the customer and the bank together performing a blind signature function to complete thee-cash withdrawal.


## 4. Our Proposed Scheme

Based on an id-based signature scheme [21] proposed by Hess and an efficient id-based blind signature [22] proposed by Zhang and Kim, we propose an offline electronic cash scheme with anonymity revocation. In the proposed scheme there are four participants: Trustee T, the bank B, the customer C, and the merchant M. There are five protocols: license issuing, withdrawal, payment, deposit, and e-cash owner tracing. Here any communication between any two entities should be encrypted, and this can be done by incorporating mutual authentication and key agreement protocols, likely in [15]. Here, for brevity, we omit those encryptions in five protocols.


### 4.1. System Setup

In this stage, the Key Generation Center (KGC) chooses a cyclic additive groupG1 which is generated by P with prime order q and chooses a cyclic multiplicative group G2 of the same order and a bilinear map e:G1×G1→G2. KGC also chooses a random s∈Zq∗ as the master key and sets Ppub=sP public and chooses cryptographic hash functions H1:{0,1}∗→G1, H2:{0,1}∗→Zq∗. The system parameter list is params=(G1,G2,e,P,Ppub,H1,H2).When the customerC submits his identity, IDC to the KGC, the KGC computes the public key QC=H1(IDC) and private key SC=sQC for the customer C. Similarly, the KGC generates the public/private key pairs (QT,ST), (QB,SB), and (QM,SM) for Trustee T, the Bank B, and the Merchant M, respectively.


### 4.2. License-Issuing Protocol

Before withdrawinge-cash from the bank, customer C needs to ask trustee T to issue him a license. The following steps describe the protocol, which is also illustrated in Box 1.Box 1:License-issuing protocol.
Customer               Trustee
Selects random numbers,
b
,
z
,
w
1
,
w
2
∈
Z
q
∗,
→{IDC,b,z,w1,w2}
Chooses random number
x∈Zq∗, computes
LST=EKT(IDC⊕x).
Selects a random number,
r∈Zq∗, computes
R=e(P,P)r
u=H2(b-1LSTR)
V=uST+rP
Selects random number
y∈Zq∗, and computes
Y=e(P,P)y,
d=H2((A1+A2+A3+A4)Y)
F=dST+yP
←(LST,u,V,d,F)
Computes
R′=e(V,P)e(uQT,Ppub)-1
Y′=e(F,P)e(dQT,Ppub)-1
And checks whether
u=H2(b-1LSTR′)
d=H2((A1+A2+A3+A4)Y′)
Obtains the license,(LST,u,V)
and the signature,(d,F) on A1+A2+A3+A4(1) CustomerC selects four random numbers, b,z,w1,w2∈Zq∗, and sends {IDC,b,z,w1,w2} to Trustee T.(2)T chooses a random number, x∈Zq∗, and computes LST as LST=EKT(IDC⊕x). Here E is a symmetric encryption algorithm, and KT is a secret key.(3) To sign onb-1LST, trustee T selects a random number, r∈Zq∗, and computes(7)R=eP,Pr,u=H2b-1LST∥R,V=uST+rP.The trusteeT also signs on A1+A2+A3+A4; here A1=(bz+z)Ppub, A2=(w1+w2)Ppub. A3=w1Ppub, and A4=bzPpub. T selects a random number, y∈Zq∗, and computes(8)Y=eP,Py,d=H2A1+A2+A3+A4∥Y,F=dST+yP.After that, trusteeT stores (LST,x) to the database and sends (LST,u,V,d,F) to the customer C.(4) The customerC computes(9)R′=eV,PeuQT,Ppub-1,Y′=eF,PedQT,Ppub-1and checks whether(10)u=H2b-1LST∥R′,d=H2A1+A2+A3+A4∥Y′.If so, The customerC obtains the license, (LST,u,V) and the signature (d,F) on A1+A2+A3+A4.


### 4.3. Withdrawal Protocol

To complete thee-cash withdrawal, customer C and bank B together perform the following steps. This protocol is also illustrated in Box 2.Box 2:Withdrawal protocol.
Customer               Bank
→{IDC,(b-1LST,u,V)}
Computes
R′=eV,PeuQT,Ppub-1
Checks whether
u=H2b-1LSTR′
Selects random number
k∈Zq∗, computes
K=kQB
←K
Selects two random number,
a,c∈Zq∗, computes
K′=aK+acQB
h=a-1H2LSTK′+c
→h
Computes
S=k+hSB
←S
Computes
S′=aS
Checks whether
e(S′,P)=e(K′+H2(LSTK′QB,Ppub)
Obtains ane-cash (LST,K′,S′)(1) CustomerC sends {IDC,(b-1LST,u,V)} to the bank B.(2)B first computes(11)R′=eV,PeuQT,Ppub-1and checks whether(12)u=H2b-1LST∥R′.If so, the bankB selects a random number, k∈Zq∗, computes K=kQB, and sends K to the customer C.(3) The customerC selects two random numbers, a,c∈Zq∗, computes(13)K′=aK+acQB,h=a-1H2LST∥K′+c,and sends h to the bank B.(4) The bankB computes(14)S=k+hSBand sends S to the customer C.(5) CustomerC computes(15)S′=aSand checks whether(16)eS′,P=eK′+H2LST∥K′QB,Ppub.If so, the customer C obtains an e-cash LST,K′,S′.


### 4.4. Payment Protocol

When the customerC wants to spend his cash at the shop, the customer C and the merchant M do the following steps. This protocol is also illustrated in Box 3.Box 3:Payment protocol.
Customer               Merchant
→(LST,K′,S′)
Checks whether
e(S′,P)=eK′+H2LSTK′QB,Ppub
Selects random number
l∈Zq∗, computes
L=e(P,P)l
j=H2(LSTK′S′L)
D=jSM+lP
←(j,D)
Computes
L′=e(D,P)e(jQM,Ppub)-1
Checks whether
j=H2(LSTK′S′L′)
Computes
f1=bjz+w1
f2=jz+w2
→(f1,f2,A1,A2,A3,A4,j,d,F)
Checks whether
e((f1+f2)QT,Ppub)=e(QT,jA1+A2)
Computes
Y′=e(F,P)e(dQT,Ppub)-1
Checks whether
d=H2((A1+A2+A3+A4)Y′)
Accepts the payment(1) CustomerC sends LST,K′,S′ to the merchant M.(2) The merchantM checks whether(17)eS′,P=eK′+H2LST∥K′QB,Ppub.If so, he selects a random number l∈Zq∗ and computes(18)L=eP,Pl,j=H2LST∥K′∥S′∥L,D=jSM+lP.Then he sends (j,D) to the customer C.(3) The customerC computes(19)L′=eD,PejQM,Ppub-1and checks whether(20)j=H2LST∥K′∥S′∥L′.If so, he computes(21)f1=bjz+w1,f2=jz+w2.Then he sends (f1,f2,A1,A2,A3,A4,j,d,F) to the merchant M.(4) The merchantM checks whether(22)ef1+f2QT,Ppub=eQT,jA1+A2and computes(23)Y′=eF,PedQT,Ppub-1and checks whether(24)d=H2A1+A2+A3+A4∥Y′.If so, the merchant accepts the payment.


### 4.5. Deposit Protocol

When the merchantM wants to deposit the received e-cash into his account in the bank B, the following steps are done between the bank B and the merchant M. This protocol is also illustrated in Box 4.Box 4:Deposit protocol.
Merchant                    Bank
→(LST,K′,S′,f1,f2,j,A1,A2,A3,A4,d,F)
Computes
Y′=e(F,P)e(dQT,Ppub)-1
Checks whether
e(S′,P)=e(K′+H2(LSTK′)QB,Ppub)
e((f1+f2)QT,Ppub)=e(QT,jA1+A2)
e(f1QT,Ppub)=e(QT,A3+jA4)
d=H2((A1+A2+A3+A4)Y′)
Checks whether thee-cash is being double spent;
if it is fresh, reedits the merchant’s account(1) The merchantM sends LST,K′,S′,f1,f2,j,A1,A2,A3,A4,d,F to the bank B.(2) The bankB first checks whether the coin exists in its deposit. If the coin exists, it runs the double spender detection procedure. Else, the bank computes(25)Y′=eF,PedQT,Ppub-1and checks whether(26)eS′,P=eK′+H2LST∥K′QB,Ppub,ef1+f2QT,Ppub=eQT,jA1+A2,ef1QT,Ppub=eQT,A3+jA4,d=H2A1+A2+A3+A4∥Y′.If the above four equations hold, the bank accepts the coin, stores it in the deposit table, and transfers money to the merchant M.


### 4.6. Revoking the Anonymity

In the case that ane-cash LST,K′,S′ is abused by a criminal, whether the cash is spent twice or not, the trustee can revoke the anonymity of the e-cash by the LST provided by the bank. As soon as the trustee T receives the request of revoking anonymity, T checks his database to find record (LST,x) and computes the identity information IDC=DKT(LST)⊕x by using his secret key KT.


## 4.1. System Setup

In this stage, the Key Generation Center (KGC) chooses a cyclic additive groupG1 which is generated by P with prime order q and chooses a cyclic multiplicative group G2 of the same order and a bilinear map e:G1×G1→G2. KGC also chooses a random s∈Zq∗ as the master key and sets Ppub=sP public and chooses cryptographic hash functions H1:{0,1}∗→G1, H2:{0,1}∗→Zq∗. The system parameter list is params=(G1,G2,e,P,Ppub,H1,H2).When the customerC submits his identity, IDC to the KGC, the KGC computes the public key QC=H1(IDC) and private key SC=sQC for the customer C. Similarly, the KGC generates the public/private key pairs (QT,ST), (QB,SB), and (QM,SM) for Trustee T, the Bank B, and the Merchant M, respectively.


## 4.2. License-Issuing Protocol

Before withdrawinge-cash from the bank, customer C needs to ask trustee T to issue him a license. The following steps describe the protocol, which is also illustrated in Box 1.Box 1:License-issuing protocol.
Customer               Trustee
Selects random numbers,
b
,
z
,
w
1
,
w
2
∈
Z
q
∗,
→{IDC,b,z,w1,w2}
Chooses random number
x∈Zq∗, computes
LST=EKT(IDC⊕x).
Selects a random number,
r∈Zq∗, computes
R=e(P,P)r
u=H2(b-1LSTR)
V=uST+rP
Selects random number
y∈Zq∗, and computes
Y=e(P,P)y,
d=H2((A1+A2+A3+A4)Y)
F=dST+yP
←(LST,u,V,d,F)
Computes
R′=e(V,P)e(uQT,Ppub)-1
Y′=e(F,P)e(dQT,Ppub)-1
And checks whether
u=H2(b-1LSTR′)
d=H2((A1+A2+A3+A4)Y′)
Obtains the license,(LST,u,V)
and the signature,(d,F) on A1+A2+A3+A4(1) CustomerC selects four random numbers, b,z,w1,w2∈Zq∗, and sends {IDC,b,z,w1,w2} to Trustee T.(2)T chooses a random number, x∈Zq∗, and computes LST as LST=EKT(IDC⊕x). Here E is a symmetric encryption algorithm, and KT is a secret key.(3) To sign onb-1LST, trustee T selects a random number, r∈Zq∗, and computes(7)R=eP,Pr,u=H2b-1LST∥R,V=uST+rP.The trusteeT also signs on A1+A2+A3+A4; here A1=(bz+z)Ppub, A2=(w1+w2)Ppub. A3=w1Ppub, and A4=bzPpub. T selects a random number, y∈Zq∗, and computes(8)Y=eP,Py,d=H2A1+A2+A3+A4∥Y,F=dST+yP.After that, trusteeT stores (LST,x) to the database and sends (LST,u,V,d,F) to the customer C.(4) The customerC computes(9)R′=eV,PeuQT,Ppub-1,Y′=eF,PedQT,Ppub-1and checks whether(10)u=H2b-1LST∥R′,d=H2A1+A2+A3+A4∥Y′.If so, The customerC obtains the license, (LST,u,V) and the signature (d,F) on A1+A2+A3+A4.


## 4.3. Withdrawal Protocol

To complete thee-cash withdrawal, customer C and bank B together perform the following steps. This protocol is also illustrated in Box 2.Box 2:Withdrawal protocol.
Customer               Bank
→{IDC,(b-1LST,u,V)}
Computes
R′=eV,PeuQT,Ppub-1
Checks whether
u=H2b-1LSTR′
Selects random number
k∈Zq∗, computes
K=kQB
←K
Selects two random number,
a,c∈Zq∗, computes
K′=aK+acQB
h=a-1H2LSTK′+c
→h
Computes
S=k+hSB
←S
Computes
S′=aS
Checks whether
e(S′,P)=e(K′+H2(LSTK′QB,Ppub)
Obtains ane-cash (LST,K′,S′)(1) CustomerC sends {IDC,(b-1LST,u,V)} to the bank B.(2)B first computes(11)R′=eV,PeuQT,Ppub-1and checks whether(12)u=H2b-1LST∥R′.If so, the bankB selects a random number, k∈Zq∗, computes K=kQB, and sends K to the customer C.(3) The customerC selects two random numbers, a,c∈Zq∗, computes(13)K′=aK+acQB,h=a-1H2LST∥K′+c,and sends h to the bank B.(4) The bankB computes(14)S=k+hSBand sends S to the customer C.(5) CustomerC computes(15)S′=aSand checks whether(16)eS′,P=eK′+H2LST∥K′QB,Ppub.If so, the customer C obtains an e-cash LST,K′,S′.


## 4.4. Payment Protocol

When the customerC wants to spend his cash at the shop, the customer C and the merchant M do the following steps. This protocol is also illustrated in Box 3.Box 3:Payment protocol.
Customer               Merchant
→(LST,K′,S′)
Checks whether
e(S′,P)=eK′+H2LSTK′QB,Ppub
Selects random number
l∈Zq∗, computes
L=e(P,P)l
j=H2(LSTK′S′L)
D=jSM+lP
←(j,D)
Computes
L′=e(D,P)e(jQM,Ppub)-1
Checks whether
j=H2(LSTK′S′L′)
Computes
f1=bjz+w1
f2=jz+w2
→(f1,f2,A1,A2,A3,A4,j,d,F)
Checks whether
e((f1+f2)QT,Ppub)=e(QT,jA1+A2)
Computes
Y′=e(F,P)e(dQT,Ppub)-1
Checks whether
d=H2((A1+A2+A3+A4)Y′)
Accepts the payment(1) CustomerC sends LST,K′,S′ to the merchant M.(2) The merchantM checks whether(17)eS′,P=eK′+H2LST∥K′QB,Ppub.If so, he selects a random number l∈Zq∗ and computes(18)L=eP,Pl,j=H2LST∥K′∥S′∥L,D=jSM+lP.Then he sends (j,D) to the customer C.(3) The customerC computes(19)L′=eD,PejQM,Ppub-1and checks whether(20)j=H2LST∥K′∥S′∥L′.If so, he computes(21)f1=bjz+w1,f2=jz+w2.Then he sends (f1,f2,A1,A2,A3,A4,j,d,F) to the merchant M.(4) The merchantM checks whether(22)ef1+f2QT,Ppub=eQT,jA1+A2and computes(23)Y′=eF,PedQT,Ppub-1and checks whether(24)d=H2A1+A2+A3+A4∥Y′.If so, the merchant accepts the payment.


## 4.5. Deposit Protocol

When the merchantM wants to deposit the received e-cash into his account in the bank B, the following steps are done between the bank B and the merchant M. This protocol is also illustrated in Box 4.Box 4:Deposit protocol.
Merchant                    Bank
→(LST,K′,S′,f1,f2,j,A1,A2,A3,A4,d,F)
Computes
Y′=e(F,P)e(dQT,Ppub)-1
Checks whether
e(S′,P)=e(K′+H2(LSTK′)QB,Ppub)
e((f1+f2)QT,Ppub)=e(QT,jA1+A2)
e(f1QT,Ppub)=e(QT,A3+jA4)
d=H2((A1+A2+A3+A4)Y′)
Checks whether thee-cash is being double spent;
if it is fresh, reedits the merchant’s account(1) The merchantM sends LST,K′,S′,f1,f2,j,A1,A2,A3,A4,d,F to the bank B.(2) The bankB first checks whether the coin exists in its deposit. If the coin exists, it runs the double spender detection procedure. Else, the bank computes(25)Y′=eF,PedQT,Ppub-1and checks whether(26)eS′,P=eK′+H2LST∥K′QB,Ppub,ef1+f2QT,Ppub=eQT,jA1+A2,ef1QT,Ppub=eQT,A3+jA4,d=H2A1+A2+A3+A4∥Y′.If the above four equations hold, the bank accepts the coin, stores it in the deposit table, and transfers money to the merchant M.


## 4.6. Revoking the Anonymity

In the case that ane-cash LST,K′,S′ is abused by a criminal, whether the cash is spent twice or not, the trustee can revoke the anonymity of the e-cash by the LST provided by the bank. As soon as the trustee T receives the request of revoking anonymity, T checks his database to find record (LST,x) and computes the identity information IDC=DKT(LST)⊕x by using his secret key KT.


## 5. Verifiability of the Proposed Scheme

Firstly, we show that the blind licenseb-1LST can be verified by equation(27)u=H2b-1LST∥R′.Since(28)R′=eV,PeuQT,Ppub-1=eV,Pe-uST,P=eV-uST,P=erP,P=R,u=H2b-1LST∥R=H2b-1LST∥R′.Secondly, we show that thee-cash can be verified by equation(29)eS′,P=eK′+H2LST∥K′QB,Ppub.In fact,(30)eS′,P=eaS,P=eak+hSB,P=eak+a-1H2LST∥K′+cQB,Ppub=eakQB+acQB+H2LST∥K′QB,Ppub=eK′+H2LST∥K′QB,Ppub.Thirdly, we show that the signature(j,D) on LST,K′,S′ by merchant can be verified by equation(31)j=H2LST∥K′∥S′∥L′.Since(32)L′=eD,PejQM,Ppub-1=eD,Pe-jSM,P=eD-jSM,P=elP,P=L,j=H2LST∥K′∥S′∥L=H2LST∥K′∥S′∥L′.Fourthly, we show that the information(f1,f2) can be verified by the equations(33)ef1+f2QT,Ppub=eQT,jA1+A2,ef1QT,Ppub=eQT,A3+jA4.In fact,(34)ef1+f2QT,Ppub=ebjz+w1+jz+w2QT,Ppub=ebjz+jzQT+w1+w2QT,Ppub=ebjz+jzQT,Ppubew1+w2QT,Ppub=eQT,bjz+jzPpubeQT,w1+w2Ppub=eQT,jA1eQT,A2=eQT,jA1+A2,ef1QT,Ppub=ebjz+w1QT,Ppub=eQT,bjz+w1Ppub=QT,A3+jA4.Finally, we show that the signature(d,F) on A1+A2+A3+A4 by trustee can be verified by the equation(35)d=H2A1+A2+A3+A4∥Y′.Since(36)Y′=eF,PedQT,Ppub-1=eF,Pe-dST,P=eF-dST,P=eyP,P=Y,d=H2A1+A2+A3+A4∥Y=H2A1+A2+A3+A4∥Y′.


## 6. Double Spender Detection

In the case that the customer spends ane-cash twice or more, the bank B can compute(37)b=f1-f1′f2-f2′,b-1LST.Then, the bank B checks its databases in the withdrawal protocol to find the record {IDC,(b-1LST,u,V)} and knows the identity information IDC of the malicious customer C.Here(f1,f2) and (f1′,f2′) are information the customer C sends to the merchant M in payment phase in twice consumption, respectively. In fact,(38)f1=bj1z+w1,f1′=bj2z+w1,f2=j1z+w2,f2′=j2z+w2.So,(39)b=f1-f1′f2-f2′.Hence, the bank C can compute b-1LST and obtain the identity information IDC of the malicious customer C.


## 7. Uncheatability of Merchants

When the customer sendse-cash LST,K′,S′ to the merchant, the merchant computes signature (j,D) on LST,K′,S′. When the merchant sends (j,D) to the customer, the customer first verifies it using the public key QM of the merchant M. When (j,D) satisfies the verification equation, the customer sends (f1,f2,A1,A2,A3,A4,d,F) to the merchant. If later the merchant uses e-cash LST,K′,S′ and (f1,f2,A1,A2,A3,A4,d,F) to spend to other merchants and cheats the customer, the customer can show the merchant’s signature to some arbitration agency. So, the scheme can effectively resist merchants cheat attack.


## 8. Provable Security

In this section, we show that the proposed scheme satisfies the property of unlinkability and unforgeability.Definition 1 (the linkability game).
Letη be a security parameter and let C1 and C2 be two customers. C1,C2, and the bank B are involved in the following game.
Step  1. The bank B outputs two Licenses LST0 and LST1.
Step  2. We randomly choose a bit b′∈{0,1} and place (Kb′,LSTb′) and (K1-b′,LST1-b′) on the private input tapes of C1 and C2, respectively. The bit b′ will not be disclosed to the bank B.
Step  3. The bank B and two customers C1,C2 perform the withdrawal protocol of the proposed scheme.
Step  4. If C1 and C2 output two e-cash (LSTb′,Kb′′,Sb′′) and (LST1-b′,K1-b′′,S1-b′′) on their private tapes, respectively, we give the two 3 tuples in a random order to the bank; otherwise, ⊥ is given to B.
Step  5. The bank B outputs b′∗∈{0,1} as the guess of b′. B wins the game if b′∗=b′. We define the advantage of B as(40)AdvBTracealityη=2pb′∗=b′-1.Definition 2 (unlinkability).
The proposed scheme satisfies the unlinkability property if the advantageAdvBTracealityη is negligible.Theorem 3.
The proposed scheme satisfies the unlinkability property.Proof of Theorem3.
We consider the condition in Definition1. Let LST,K′,S′ be one of the two e-cash given to the bank and let (K,h,S) be the view of the bank in one of the withdrawal protocols. It is sufficient to show that there exist two random factors (a,c) that map (K,h,S) to LST,K′,S′. We know(41)K′=aK+acQB,h=a-1H2LST∥K′+c,S′=aS.
So, by equationS′=aS, there is a unique a. Then, by equation h=a-1H2LST∥K′+c, there is a unique c. Furthermore, when S and S′ are correctly computed, the following equation holds:(42)eS,P=eK+a-1H2LST∥K′+cQB,Ppub,eS′,P=eK′+H2LST∥K′QB,Ppub.So, it holds when  K′=aK+acQB. It is to say that (a,c) always exists regardless of the values LST,K′,S′ and (K,h,S). Therefore, even an infinitely powerful bank outputs a correct value b′ with probability of exactly 1/2. So, the proposed scheme satisfies the unlinkability property.Definition 4 (the forgeability game).
The adversary F and the challenger A play the following game.
Step  1. The challenger A takes a security parameter and generates the public parametersparams and sendsparams to the adversary F.
Step  2. The adversary F can perform polynomially bounded number of hash queries, extract queries, and e-cash queries. These three kinds of queries answer the hash function, private key, and e-cash query by the adversary F, respectively.
Step  3. The adversary F outputs a tuple σ=LST,K′,S′,IDB. This tuple satisfies the following requirements:(1)
LST,K′,S′ is a valid e-cash with regard to the bank B.(2)
The adversary F has never requested the private key of the bankB.(3)
σ=LST,K′,S′,IDB has never been queried during the e-cash query.Definition 5 (unforgeability).
An adversary F is said to be an(ε,t,qE,qI,qH)-forger if it has advantage at least ε in the above game, runs in time at most t, and makes at most qE, qI, and qH extract, e-cash, and hashing queries, respectively. A scheme is said to be (ε,t,qE,qI,qH)-secure against A in the sense of unforgeable against e-cash existential forgery attack if no (ε,t,qE,qI,qH)-forger exists.Theorem 6.
If the CDH problem is hard, then the proposed scheme is secure againste-cash existential forgery attack.Proof of Theorem6.
Suppose that F is a forger who can forgee-cash in the proposed scheme. A CDH instance (P,xP,yP) is given for x,y∈RZq∗, By using the forgery algorithm F, we will construct an algorithm A which outputs the CDH solution xyP in G. Algorithm A performs the following simulation by interacting with the forger F.
Setup. Algorithm A sets Ppub=xP and starts by giving F the system parameters including (P,Ppub).
At any time, F can query the random oracleH1,H2 and extract and cash queries. To answer these queries, A does the following.
H
1-Queries. At any time F can query the random oracle H1. To respond to these queries, A maintains a list H1-list of tuples (ID,W,t,e) as explained below. When an identity ID is submitted to the H1 oracle, A responds as follows: If the query ID already appears on the H1-list in a tuple (ID,W,t,e), A responds with H1(ID)=W. Otherwise, A generates a random coin e∈{0,1}. If e=0 then A computes W=t(yP) for a random t∈Zq∗; If e=1 then A computes W=tP. A adds the tuple (ID,W,t,e) to H1-list and responds to F with H1(ID)=W.
H
2-Queries. To respond to H2-Queries, A maintains a list referred to as H2-list of tuples LST∥K′,d. When F queries the H2 oracle at LST∥K′, A responds as follows: If the query LST∥K′ already appears on the H2-list in a tuple LST∥K′,d, then A responds with H2LST∥K′=d∈Zq. Otherwise, A generates a random d∈Zq and adds the tuples LST∥K′,d to H2-list and responds to F with H2LST∥K′=d.
Extract Queries. When F queries the private key corresponding to ID, A first finds the corresponding (ID,W,t,e) from the H1-list. If e=0, then A fails and halts. Otherwise, A computes the private key SID=t·Ppub=t(xP) by using the tuple (ID,W,t,e) in the H1-list and responds to F with SID.
Cash Queries. If F requests an e-cash on LST under ID, A responds to this query as follows: A first finds the corresponding tuple (ID,W,t,e) from H1-list and chooses one random number l,d∈Zq∗ and computes K′=lP-dW. If LST∥K′,d already appears on the H2-list, A chooses another l,d∈Zq∗ and tries again. Otherwise, A computes S′=l·Ppub and stores LST∥K′,d on the H2-list. Then A responds to F with S′,K′. Indeed, the output is valid e-cash on LST for ID. In fact,(43)eK′+H2LST∥K′QB,Ppub=elP-dW+dW,Ppub=elP,Ppub=elPpub,P=eS′,P.
Output. If A does not abort as a result of F’s extract query, then F’s view is identical to its view in the real attack. By Forking Lemma, after replying F with the same random tape, A obtains two valid e-cash:(44)LST,K′,S′,LST,K′,S′∗.Correspondingly, there are two valid signatures (S,K) and (S∗,K), because(45)S=k+hSB,S∗=k+h∗SB.So, by the security proof of [22], A obtains (xy)P=SB=(h-h∗)-1(S-S∗).
This completes the proof.


## 9. Comparisons

In this section, we compare our scheme with [15, 18–20] in some features, communication efficiency, and computation cost. The features are anonymity/unlinkability, unforgeability, verification, double-spending owner tracing, anonymity revocation, and uncheatability of merchant. Our scheme satisfies all of above features, but the others do not. We show the comparison result in Table 1. In Table 2, we compare the communication efficiency of our scheme with other schemes. Fan et al.’s scheme [18] and Zhang et al.’s scheme [20] are not trustee based, and therefore they do not have license-issuing protocol and owner tracing protocol. Juang’s scheme [19] also does not have license-issuing protocol and owner tracing protocol but has the initializing phase and recovering phase. For comparison, the numbers of rounds of initializing phase and recovering phase in Juang’s scheme are computed to license-issuing protocol and owner tracing protocol, respectively. By Table 2, the proposed scheme demonstrates better communication efficiency under enhanced security. Our scheme and schemes [15, 20] are all id-based scheme using bilinear pairings. So, in Table 3, we compare the computation cost of our scheme with schemes [15, 20]. It is necessary to illustrate that Zhang et al.’s scheme [20] has no license-issuing protocol and owner tracing protocol and for fair comparison, we have not computed the computation cost of encryption and its related computation cost in Chen et al.’s scheme. Compared with Chen et al.’s scheme, there are eleven more pairings computations in the proposed scheme. These eleven pairings computations are in payment protocol and deposit protocol and useful to prevent the merchant from cheat. In practice, we can use elliptic curves to reduce the computation cost of bilinear pairings.Table 1
Comparison of features of our scheme with recent schemes.
F1
F2
F3
F4
F5
F6
Chen et al. [15]
Yes
Fail
Yes
Yes
Yes
Fail
Fan et al. [18]
Yes
Yes
No
Yes
Yes
No
Juang [19]
Yes
Yes
Yes
Yes
No
No
Zhang et al. [20]
Yes
Yes
Yes
No
No
No
Ours
Yes
Yes
Yes
Yes
Yes
Yes
F1: anonymity/unlinkability; F2: unforgeability; F3: verification; F4: double-spending owner tracing; F5: anonymity revocation; F6: uncheatability of merchant.Table 2
Required number of rounds for each protocol in compared schemes.
P1
P2
P3
P4
P5
Chen et al. [15]
2
2
1
1
1
Fan et al. [18]
—
4
3
1
—
Juang [19]
3
3
1
1
2
Zhang et al. [20]
—
3
2
1
—
Ours
2
4
3
1
1
P1: license-issuing protocol; P2: withdrawal protocol; P3: payment protocol; P4: deposit protocol; P5: owner tracing.Table 3
Comparison of computation costs.
P1
P2
P3
P4
P5
Chen et al. [15]
E + 2H + 3B
4H + 6B
H + 3B
H + 3B
D
Zhang et al. [20]
—
2H + 2B + L
2H + 3B
2H + 3B
—
Ours
E + 4H + 5B + 2L
2H + 4B
4H + 9B
2H + 8B
D
P1: license-issuing protocol; P2: withdrawal protocol; P3: payment protocol; P4: deposit protocol; P5: owner tracing.
E: symmetrical encryption; D: symmetrical decryption; H: hash computation; B: bilinear pairings; L: modular exponentiation.


## 10. Conclusion

In this paper, we show that Chen et al.’s electronic cash scheme is suffering from some weaknesses in unforgeability and merchant frauds. To contribute a secure scheme, we propose a new offline electronic cash scheme with anonymity revocation. We also provide the formally security proofs of the unlinkability and unforgeability. Furthermore, the proposed scheme ensures the property of avoiding merchant frauds.



---

*Source: 2620141-2016-04-26.xml*