A Fair Electronic Cash System with Identity-Based Group Signature Scheme ()
1. Introduction
The first group signature scheme was proposed by David Chaum and van-Heyst in 1991 [1]. Group signature schemes allow a group member to sign messages on behalf of the group. Such signatures must be anonymous and unlinkable but, whenever needed, a designated group manager can reveal the identity of the signer [1-3]. Shamir proposed an identity based signature to simplify key management procedures of certificate-based public key infrastructures (PKI) [4]. A lot of identity based group signatures have been proposed after Shamir [5-8]. Many group signatures scheme have been proposed recently, but several of them were suggested application electronic cash. [9-11] introduced group signatures into electronic cash schemes which are anonymous and unlinkability.
Main Contribution
In this paper, identity based group signature scheme is proposed, which satisfies the electronic cash based on group signatures. Furthermore it provides to keep group member anonymous and unlinkability if he does not cheat. In this scheme we use trusted third party, which acts the group manager. The user is a group member who should register at TTP before start any interaction with the bank.
The rest of this paper is as follows: in the next section, we introduce some preliminaries work. Our identity based group signature is presented in Section 3. In Section 4, we propose a new electronic cash system. We explain security analysis of our scheme in Section 5. Final section concludes.
2. Preliminaries
In this section, we will describe the definition and properties of elliptic curve cryptography, bilinear pairings, Gap Diffie-Hellman Group and Group signature models.
2.1. Elliptic Curve Cryptography
2.1.1. Definition1: Addition Rules of Elliptic Curve [12]
It is possible to define an addition rule to add points on E. The addition rule is specified as follows:
Identity: ![](https://www.scirp.org/html/14-7800063\76a86e48-561e-459a-87ed-16cc4a3789f0.jpg)
![](https://www.scirp.org/html/14-7800063\3ff7706c-32f4-4cd1-bbbc-1f0cf722f7f1.jpg)
Negation: if
then
where
and denoted by
.
Note: ![](https://www.scirp.org/html/14-7800063\e60f200d-51ab-4bed-9db1-fe1b7cfd2d50.jpg)
Add two points with different x-coordinates:
Let
be two points such that
then
as shown in Figure 1, where
![](https://www.scirp.org/html/14-7800063\786485f0-b07e-49a7-b114-83f60e8da084.jpg)
![](https://www.scirp.org/html/14-7800063\c702e313-1ed1-41cf-a623-5e617c44b9b4.jpg)
Add a point to itself (double a point) with
:
Let
, then
, where:
![](https://www.scirp.org/html/14-7800063\f7428680-fc4e-4a43-896d-421cb2d09bfb.jpg)
![](https://www.scirp.org/html/14-7800063\b67aab36-7070-45ce-a53d-eacf5d19d687.jpg)
Figure 1. Architecture of our electronic cash scheme.
2.1.2. Definition 2 Elliptic Curve Discrete Logarithm Problem (ECDLP)
Given an elliptic curve E defined over a finite field
, a point
of order n, find the integer
such that
. The integer x is called the discrete logarithm of Q to the base P denoted as
. If x is sufficient large, then it is infeasible to compute it [13].
2.2. Bilinear Pairings
Let
and
be two cyclic groups generates by P, whose order is a prime q, where
is additive groups and
is multiplicative group. A pairing is a function:
![](https://www.scirp.org/html/14-7800063\f875bb20-ab27-4799-97df-efda0334f376.jpg)
All pairing will satisfy the following properties:
1) Bilinear: For all
and
then ![](https://www.scirp.org/html/14-7800063\ed253ab3-55ff-47a1-95b0-3148c3a80822.jpg)
2) Non-degenerate: There exists
such that ![](https://www.scirp.org/html/14-7800063\acd22bf6-c652-4674-b297-9668631bef26.jpg)
3) Computable: There is an efficient algorithm to compute
for all
.
2.3. Gap Diffie-Hellman Group
We first introduce the following problems in G [14].
1) Discrete Logarithm Problem (DLP): if given P and Q, to find
from
.
2) Computation Diffie-Hellman Problem (CDHP). Given
for
, to compute
.
3) Decisional Diffie-Hellman Problem (DDHP).
Given
, or
, to decide whether
.
We call
a GDH group if DDHP can be solved in polynomial time but no polynomial times an algorithm can solve CDHP or DLP with non-negligible advantage within polynomial time.
2.4. Group Signature Model
A group signature scheme is comprised of the following procedures [5]:
1) Setup: An algorithm that generates the group public key and a group master key for the group manager.
2) Extract: A protocol between the group manager and a group member that generates the user’s secret key and public key.
3) Sign: A probabilistic algorithm (with inputs as a group public key, a membership secret and a message m) outputs a group signature of m.
4) Verify: An algorithm for establishing the validity of an alleged group signature of a message with respect to the group public key.
5) Reveal: An algorithm that, given a message, a valid group signature on it, a group public key and a group manager’s master key, determines the identity of the actual signer.
A secure group signature scheme should satisfy all or part of the properties:
1) Correctness: Group signatures produced by a group member must be valid.
2) Unforgeability: Only group members are able to sign messages on behalf of the group.
3) Anonymity: It is infeasible to find out the group member who signed a message without the group manager’s secret key.
4) Unlinkability: Deciding whether two different valid signatures were computed by the same group member is computationally hard.
5) Exculpability: Neither a group member nor the group manager can sign on behalf of other group members.
6) Traceability: The group manager is always able to identify the actual signer for a valid signature in case of disputes.
7) Coalition-resistance: No coalition of members can prevent a group signature from being opened.
3. Our Identity Based Group Signature
In this section we consider ID-based group signature scheme from bilinear pairings, which can be implemented as follows:
3.1. Setup
Setup is a system generation. The group manager executes the following:
Choose
as defined in 2.2 and choose
.Select three hash function cryptography
which satisfy
and
Select
as secret key.
Compute
and publish
as public key.
3.2. Extract
Before the user joins the group, manager should execute this step:
1) Select random number
as private key.
2) Compute
as public key.
When the user wants to become the member of group then the user i and the group manager can cooperates as follows:
1) The user sends his public key with ID (identification) to the group manager.
2) Group manager select random numbers
for every member who want become group member.
3) Group manager calculate
where
and then sends
to the user as the membership certificate.
3.3. Sign
When the user wants to sign message m, the user can do the followings:
The user selects random elements
and
, and then calculates the followings:
![](https://www.scirp.org/html/14-7800063\46f27236-3712-4b92-bbf0-a4a51f22d198.jpg)
![](https://www.scirp.org/html/14-7800063\0a941fba-bf90-46f2-b3e5-091c15ace9b9.jpg)
![](https://www.scirp.org/html/14-7800063\e992ab4a-7e0a-43f3-a168-7e6b51fdcb05.jpg)
![](https://www.scirp.org/html/14-7800063\0c3cb7c2-3eff-4a37-a97a-6a15962a0d72.jpg)
![](https://www.scirp.org/html/14-7800063\fe33fbe3-42d7-446f-a128-ecae975b50d0.jpg)
![](https://www.scirp.org/html/14-7800063\1f23d00d-855a-4438-bb6d-4177cd107ab2.jpg)
![](https://www.scirp.org/html/14-7800063\da3fad2c-87f0-45f4-9117-2e1aef166273.jpg)
![](https://www.scirp.org/html/14-7800063\57551a5c-8aa9-41f4-b792-69c55f5fad73.jpg)
![](https://www.scirp.org/html/14-7800063\b3b62639-9e8b-4d83-843c-9369094bd231.jpg)
![](https://www.scirp.org/html/14-7800063\eaadf382-aa85-42df-90ad-4bd27f0de15a.jpg)
![](https://www.scirp.org/html/14-7800063\eac43817-e85f-4be6-822d-fb11f192575f.jpg)
![](https://www.scirp.org/html/14-7800063\7af24db7-4600-476a-a297-6f7cdafe5601.jpg)
The resulting signature on the message m is (U, C, D, W, R, S).
3.4. Verify
When the receiver wants to verify the group signature (U, C, D, W, R, S) of the message m which is signed by the signer, the receiver first computes
and then verifies
.
3.5. Open
This algorithm is only executed by the group manager. Given valid group signatures the group manager can easily find the identity of the signer. The signer cannot deny his group signatures after group manager presents the followings:
![](https://www.scirp.org/html/14-7800063\f183536e-055c-43ca-aa9f-46fe702f8719.jpg)
![](https://www.scirp.org/html/14-7800063\927cd21e-c7a4-4b2d-be45-07f968db88d6.jpg)
4. Our Electronic Cash System
4.1. Electronic Cash Architecture
In this section, we describe our system architecture and how each protocol of e-cash works. Figure 1 shows configuration of group signatures, which involves three protocols: withdraw protocol, payment protocol and deposit protocol. Thus group signatures architecture consists four main parties: Trust Third Party (TTP) acts the group manager; banks, users and shops acts the group member. Their relation between each part with other as follows:
1) Trusted Third Party (TTP) is acting as group manager and the users act group membership. The user should be registering at TTP before start any interaction with the bank. After registration, the user will get a valid membership certificate and a secret key from TTP.
2) The bank issues the valid electronic cash. The bank protects the privacy of the customers, and also uses the blind signature technique to sign the electronic cash.
3) The customer spends electronic cash in a payment protocol with a shop over an anonymous channel.
4) The shop deposits electronic cash that he gets from the user in the payment protocol into his bank account.
4.2. Setup
TTP (Central Bank (CB)) generates and publishes the same system parameters that proposed in Section 3.1.
When the bank i
registers in CB, they should perform the following steps:
1)
selects random number
as private key and computes
as public key.
2)
sends public key with his identification
to the CB.
3) The CB does the same in Section 3.2 and sends
to
as membership certificate.
And also the user i
and merchant i
should do the same steps that
does when they want to register in CB.
Then the central bank will send the group member ship
to
respectively.
4.3. Open an Account
Every group member should open an account in any bank he needs it. They need to do as follows:
1) The group member sends
to the bank
.
2)
opens an account and sends it to the group member.
4.4. Withdraw Protocol
The withdrawal protocol involves
and
which the user opens an account in. When legal
wants to withdraw electronic cash from his account in the bank, the user must prove himself to the bank. The withdraw protocol request contains the amount of electronic cash, which is less than or equal the balance. If the amount is greater than balance then the withdraw protocol should be stopped, otherwise, the user and the bank execute the following steps:
1) the user chooses random number
and computes
sends A1 and A2 to the bank i.
2) the bank selects random number
and
and computes
![](https://www.scirp.org/html/14-7800063\5572b502-3544-4ca0-a80b-7ac975c423f5.jpg)
sends
to
.
3) the
calculates
selects random numbers
and computes
,
,
, ![](https://www.scirp.org/html/14-7800063\4149ae1a-c30e-4842-bb5b-6327969d7342.jpg)
, ![](https://www.scirp.org/html/14-7800063\a2d7df45-363a-4d48-8bb0-ecd5981a6cbf.jpg)
, ![](https://www.scirp.org/html/14-7800063\fdc59b62-f706-4aa5-9ac7-98ff9af3422a.jpg)
![](https://www.scirp.org/html/14-7800063\ed9ec9a6-5725-4842-b1a1-509eab343d66.jpg)
sends
to
.
4) the Bi computes
sends
to
.
5) the
checks
(1)
and
(2)
If (1) and (2) holds, then the user accepts and computes ![](https://www.scirp.org/html/14-7800063\256e5948-400b-4e2f-b166-a4e2c57b86ef.jpg)
We can proof (1) and (2) as follows:
![](https://www.scirp.org/html/14-7800063\9f36e972-c2e6-465d-accb-263969748e4d.jpg)
![](https://www.scirp.org/html/14-7800063\b1c66d33-7dbc-4de7-af0d-874317d958a0.jpg)
4.5. Payment Protocol
The payment protocol involves the customer and the merchant. If the customer wants to buy some goods from the merchant, they should execute the follows:
1) The customer chooses a random
and computes ![](https://www.scirp.org/html/14-7800063\8f4f2e96-81fe-4641-8236-28fd8512f682.jpg)
User sends
to merchant.
2) The merchant generates a transaction message of payment for the customer d as challenge and sends to user d = H0(A, B, C, D, Z, Z1, S2,
,amount, amount type, date/time)
3) User calculates responses
![](https://www.scirp.org/html/14-7800063\554e0446-5242-4a31-a2f6-4c59c3f5e1cd.jpg)
User sends
to merchant.
4) The signature of electronic cash is
.
5) Merchant accepts if and only if
(3)
(4)
Now we can proof (3) and (4) as followings:
![](https://www.scirp.org/html/14-7800063\c11f919b-2349-4e53-a165-395a9a6ffeaf.jpg)
![](https://www.scirp.org/html/14-7800063\3a526d0d-bc56-4015-ae87-fb1a95d09969.jpg)
4.6. Deposit Protocol
In this protocol the merchant i sends electronic cash to his bank i. There are two cases we will discuss as follows:
First case: if the shop i and user i have accounts in the same bank. Since the deposit protocol involves merchant and bank, they will execute the following steps:
1) The merchant sends signatures of electronic cash
to the bank.
2) The bank verifies the validity of signature of e cash
.
3) If the signature of e cash
is hold, then the bank searches the deposit database to find out the same electronic cash has been deposited before or not. If it has not been in its deposit database, the bank accepts the electronic cash and credits the amount to the shop account, otherwise the bank i rejects transaction.
Second case: if the user i and merchant i have accounts in different banks such as user i has an account in the bank i and shop i has an account in bank j.
Assume merchant i wants to deposit the received electronic cash from user i to his bank j, they will do the following steps:
1) The merchant sends signature of electronic cash
to bank j.
2) Bank j verifies the validity of signature of e cash
with bank i’s public key.
3) If it succeeds then bank j sends the electronic cash to bank i.
4) Bank i searches the deposit database to find out whether electronic cash has been deposited before, if it is not has been stored in deposit database then bank i debits the amount from user i account and sends it to the merchant i account in his bank j, otherwise bank i can detect double depositing or double spending.
4.7. The Tracing Protocol
Customer Tracing Protocol
The customer tracing protocol involves the bank and the trusted third party. This protocol is used to determine the identity of the customer in a specific payment transaction. Money laundering is big problem of electronic cash; here it can be protected by detecting the identity of the illegal customers.
1) The customer tracing protocol is as follows:
The bank sends to the CB the signatures of electronic cash
that received from the merchant in the deposit protocol.
2) The CB verifies the validity of the signature of electronic cash as the merchant does in the deposit protocol.
3) The CB can calculate
from
as follows:
(5)
From
then put it into (5)
![](https://www.scirp.org/html/14-7800063\9ba140d7-fef5-428b-af5b-995e29b83540.jpg)
Finally we get
![](https://www.scirp.org/html/14-7800063\e80ee3e6-0d64-4d50-b49c-7a42990e0bdc.jpg)
The CB sends
to the bank.
Then the bank can find the actual identity corresponding to
in his database.
5. Analysis of Security
Theorem 1
A group member and the group manager cannot sign electronic cash on behalf of the other group members with non-negligible probability.
Proof:
Assume there is a group member who has
wants to sign electronic cash on behalf of the group member who has
.
He chooses random number
, computes and sends
to bank i.
![](https://www.scirp.org/html/14-7800063\081fa4c4-390f-4f4d-8553-6941f6a1774b.jpg)
![](https://www.scirp.org/html/14-7800063\d40227aa-a917-4c6d-9758-b30fd4b9b08c.jpg)
The bank calculates and sends
back to him as withdraw protocol.
He selects random numbers
and computes
as withdraw protocol, computes
as follows:
,
,
,![](https://www.scirp.org/html/14-7800063\34114e97-34fd-4623-802b-154e3fcd63f4.jpg)
Finally he calculates c as
![](https://www.scirp.org/html/14-7800063\1f6fa727-4484-468d-85fa-d4ff04836151.jpg)
This equation can be equal to that equation in withdraw protocol, if and only if
![](https://www.scirp.org/html/14-7800063\aaf23795-7d2a-4e27-aad5-1fa0f89c4ba3.jpg)
The probability of
is
,
. If he wants to choose exactly
, he needs to solve discrete logarithm problem
as
.
Theorem 2
The proposed fair electronic cash system can protect the customer’s privacy and keep the system anonymous.
Proof:
Deciding whether a payment signature from a customer requires knowing
of the user. However, to know
of the user in our scheme requires solving discrete logarithm problem
to find out the user secret key. Since solving discrete logarithm problem is very difficult, then no one can know
except CB.
Theorem 3
In the payment protocol, only users that register in the CB are able to sign a payment message with his membership key.
Proof:
It is difficult to find
from
. The forger cannot find the same
then it is impossible to get certificate membership
to sign a payment message.
Theorem 4
Our proposed scheme keeps the system unlinkability.
Proof: To decide whether two signatures of electronic cash
and
are from the same customer requires deciding whether
it is not easy to compute it.
From the four theorems and traceable protocol above, it is easy to deduce that our scheme satisfies the security properties of group signatures and provides electronic cash against double spending, blackmailing and money laundering.
6. Conclusion
We have presented new fair electronic cash system with identity based group signature scheme. It satisfies all basic requirements to protect electronic cash. Furthermore, we show how our group signature scheme could construct fair electronic cash, which satisfy properties of secure group signature scheme.