Development of Self-Issuable (Divisible and Transferable) Offline Electronic Cash

Shinsuke Tamura, Hazim A. Haddad

Information Security and Computer Fraud OPEN ACCESSPEER-REVIEWED

Development of Self-Issuable (Divisible and Transferable) Offline Electronic Cash

Shinsuke Tamura1,, Hazim A. Haddad1

1School of Engineering, University of Fukui, Fukui, Japan

Abstract

Based on anonymous tag based credentials and linear Mix-nets, this paper develops a scheme for e-cash systems that can be used in offline environments. The developed scheme makes e-cash holders anonymous while disabling them to use e-cash dishonestly. It also makes e-cash divisible and transferable. In detail, although no one except cash holders themselves can know correspondences between them and their e-cash, e-cash issuing authority can identify dishonest cash holders that had generated and/or spent e-cash illegitimately. In addition, cash holders can generate new e-cash of arbitrary values from their holding e-cash to make purchases of amounts less than original cash values. Also, cash holders can use e-cash that they had received from others as same as the one directly issued to them from the issuing authority.

Cite this article:

  • Shinsuke Tamura, Hazim A. Haddad. Development of Self-Issuable (Divisible and Transferable) Offline Electronic Cash. Information Security and Computer Fraud. Vol. 3, No. 1, 2015, pp 15-24. http://pubs.sciepub.com/iscf/3/1/3
  • Tamura, Shinsuke, and Hazim A. Haddad. "Development of Self-Issuable (Divisible and Transferable) Offline Electronic Cash." Information Security and Computer Fraud 3.1 (2015): 15-24.
  • Tamura, S. , & Haddad, H. A. (2015). Development of Self-Issuable (Divisible and Transferable) Offline Electronic Cash. Information Security and Computer Fraud, 3(1), 15-24.
  • Tamura, Shinsuke, and Hazim A. Haddad. "Development of Self-Issuable (Divisible and Transferable) Offline Electronic Cash." Information Security and Computer Fraud 3, no. 1 (2015): 15-24.

Import into BibTeX Import into EndNote Import into RefMan Import into RefWorks

At a glance: Figures

1. Introduction

Together with credit card systems e-cash systems are one of the most convenient paying schemes in e-society and many schemes had been proposed already [1-7][1]. Among various features that existing e-cash schemes aim to achieve, anonymity, divisibility and transferability are most important, where anonymity ensures that correspondences between e-cash and their holders are not revealed, and divisibility and transferability enable each cash holder to divide its e-cash into ones with smaller cash values and to use e-cash that it had received from others, respectively.

But in offline environments where e-cash issuing authorities do not participate in individual purchases, to efficiently satisfy these requirements is not easy. Regarding the divisibility, existing schemes must assume the unit cash value for dividing original e-cash in advance and required computation and/or communication costs increase when the unit becomes small [7]. Also, several schemes cannot achieve complete anonymity, e.g. cash holders cannot conceal links among e-cash that they generated by dividing same e-cash [1]. In the same way, many existing transferable e-cash schemes cannot achieve complete anonymity [4, 5]. For example, authorities can identify cash holders that used illegitimately transferred e-cash even if they were honest [5]. In addition, they are not convenient enough, e.g. volume of information that constitutes each e-cash increases every time when the e-cash is transferred [6] or cash holders must maintain numbers of receipts obtained from payees even after they had spent their e-cash [5].

While exploiting anonymous tag based credentials [8, 9, 11] and linear Mix-nets [10, 11], this paper proposes a scheme that efficiently and effectively achieves the above 3 features, i.e. it achieves complete anonymity while enabling authorities to identify dishonest entities. Also, each cash holder can divide its e-cash into ones with arbitrary (even decimal) cash values to pay them to others provided that the total value of divided e-cash does not exceed the value of the original e-cash. In addition, volume of information that constitutes each e-cash or computation and communication cost for handling the e-cash does not increase even the e-cash is exchanged among many cash holders. Cash holders do not need to maintain numbers of receipts either.

2. Environments and Requirements

Figure 1 shows entities involved in the proposed offline e-cash scheme, they are e-ash issuing authority A and cash holders P1, P2, ---, PM. Authority A issues e-cash to cash holders P1, P2, ---, PM, and each Pm makes its purchase while paying its e-cash C(Pm, t, h) to other cash holder Pk (Pm may simply give C(Pm, t, h) to Pk). Pm also asks A to exchange its e-cash for real cash.

About e-cash, C(Pm, t, h) means that Pm pays it to Pk as the h-th division of its t-th e-cash, and Pm obtains its t-th e-cash as C(A, i) that was issued by authority A or C(Pj, s, v) that was paid by other cash holder Pj. Where, C(A, i) represents e-cash that authority A had issued directly to Pm as the i-th e-cash. Also an expiration time is defined for each e-cash, and cash holders must exchange their e-cash for real cash at A before they expire.

An important thing is offline e-cash system schemes must satisfy the following requirements under conditions that cash holders Pm, Pj and Pk are anonymous and they pay or give their e-cash to other cash holders without the presence of authority A, and the proposed e-cash system scheme satisfies these requirements by exploiting anonymous tag based credentials and linear Mix-nets as explained in the following sections. The requirements are,

1. Unforgeability Only cash issuing authority can generate valid e-cash,

2. Anonymity honest cash holders can conceal correspondences between them and their spending e-cash,

3. Divisibility cash holders can divide their e-cash into e-cash with smaller cash values,

4. Transferability cash holders can use e-cash that were paid to them by others,

5. Unlinkability cash holders can conceal links among e-cash that they had spent, and

6. Security cash holders cannot use e-cash illegitimately.

But about the security, illegitimate e-cash uses include double spending and using of e-cash owned by others, and in environments where individual cash holders are anonymous and authority A does not exist when cash holders pay their e-cash, payees cannot confirm that their receiving e-cash were certainly owned by payers or payers did not use same e-cash at other places. Therefore, to satisfy the security requirements, the proposed scheme detect illegitimately used e-cash after they were used and identify liable entities as same as other existing schemes.

3. Security Components

3.1. Anonymous Tag based Credentials

Provided that B, TP, k and g are integers defined by authority A, R and w are secret integers defined by entity P, d1 and d2 are 2 secret signing keys of A and S(d1d2, x) is a pair of RSA signatures {S(d1, x) = xd1mod B, S(d2, x) = xd2mod B}, signature pair T(A, TP, R) = S(d1d2, TPR+1KwGwRmod B) is an anonymous tag based credential generated by A and given to P. Here, integers B, TP, k and g are publicly known and they are defined so that to know integers q1, q1*, q2, q2*, q3, q3* that satisfy relations TP = kq1mod B, TPq1*mod B = k, k = gq2mod B, kq2*mod B = g, g = TPq3mod B, gq3*mod B = TP is computationally infeasible for entities other than A. Different from B, k and g that are common to all credentials, TP and R are unique to T(A, TP, R), and P calculates Kw and Gw as Kw = kwmod B and Gw = gwmod B based on publicly known k, g and secret integer w. About signing keys d1 and d2, they can be maintained as secrets of A despite multiple verification keys are publicly disclosed because the signer is only A. Also it is easy to maintain uniqueness of P’s secret integer R as will be discussed in Sec. 4.1 [8, 9, 11]. In the remainder, notation mod B is omitted when confusions can be avoided.

Important things are, firstly P can prove that credential T(A, TP, R) is legitimate and it knows secret integer R in it by showing T(A, TP, R)W = S(d1d2, TPR+1KwGwRmod B)W without disclosing R itself, and secondly for given integer U, other entities can force P to calculate UR honestly as a used seal of T(A, TP, R) while using secret integer R. Here, W is P’s secret integer and entities that do not know W cannot know the correspondence between T(A, TP, R) and T(A, TP, R)W, i.e. to calculate W from T(A, TP, R) and T(A, TP, R)W is a discrete logarithm problem. Also, only P that knows R can calculate UR from U. Then, P can convince others that it is a legitimate owner of the credential without revealing its identity by showing T(A, TP, R)W. On the other hand, other entities can use used seal UR as an evidence that P had certainly shown credential T(A, TP, R). But it must be noted that UR and UR* may have a same value despite R ≠ R*. Therefore to make used seals unique to credentials, actually T(A, TP, R) is implemented as a set of values {S(d11d21, TPR+1KwGwRmod B1), S(d12d22, TPR+1KwGwRmod B2)} by using different integers B1 and B2. Namely, relation URmod B1 = UR*mod B1 does not holed even when relation URmod B2 = UR*mod B2 holds.

In conclusion, together with used seal UR credential T(A, TP, R) satisfies the following requirements. They are,

a) Unforgeability no one other than authority A can generate valid credentials,

b) Soundness entities that do not know integer R in credential T(A, TP, R) cannot prove the ownership of T(A, TP, R) to other entity Q. Also, when Q dishonestly accepts T(A, TP, R) shown by other credential holder P* possibly while conspiring with it, A can detect that and identify liable entities,

c) Anonymity anyone except P cannot identify P from credential form T(A, TP, R)W,

d) Unlinkability even if P shows credential T(A, TP, R) n-times in forms T(A, TP, R)W1, T(A, TP, R)W2, ---, T(A, TP, R)Wn while generating different secret integers W1, W2, ---, Wn, no one except P can know links between them,

e) Revocability A can invalidate credential T(A, TP, R) without knowing secrets of honest entities, if its holder P behaved dishonestly while showing T(A, TP, R)W or if A reissued new credential to P as a replacement of T(A, TP, R), and

f) Verifiability anyone can verify the validity of credential T(A, TP, R), in other words, entities can verify the validity of T(A, TP, R) without knowing any secret of A.

3.2. Linear Mix-net

Linear Mix-net L consists of a sequence of mutually independent mix-servers L1, L2, ---, LZ and enables authority A to calculate the sum of attribute values DP(1), DP(2), ---, DP(HP) owned by same data holder P without knowing the correspondence between P and each DP(h) or the calculated sum or links between individual attribute values DP(1), DP(2), ---, DP(HP) [10, 11].

Conceptually, P generates triplet {h, DP(h), U(h)R} that includes its h-th attribute value DP(h) for each h, puts triplets {1, DP(1), U(1)R}, {2, DP(2), U(2)R}, ---, {HP, DP(HP), U(HP)R} in L separately without revealing its identity, and mix-servers L1, L2, ---, LZ repeatedly encrypt each {h, DP(h), U(h)R} to {h, E(DP(h)), U(h)R∙V} by their secret encryption keys while shuffling their encryption results. After that, authority A gathers encrypted triplets {1, E(DP(1)), U(1)R∙V}, {2, E(DP(2)), U(2)R∙V}, ---, {HP, E(DP(HP)), U(HP)R∙V} that correspond to P and calculates sum E(DP(*)) = E(DP(1))+E(DP(2))+ --- + E(DP(HP)), constructs pair {E(DP(*)), U(*)RV}, and finally LZ, LZ-1, ---, L1 repeatedly decrypt each pair {E(DP(*)), U(*)RV} to {DP(*) = DP(1)+DP(2)+ --- +DP(HP), U(*)RV∙Y} by their secret decryption keys while shuffling their decryption results.

In detail, P convinces L of its eligibility by showing credential T(A, TP, R)W(P, h) while generating secret integer W(P, h) to put its h-th attribute value DP(h), and calculates used seal U(h)R of T(A, TP, R) from integer U(h) defined by L1, L2, ---, LZ. About encryptions and decryptions of U(h)R in {h, DP(h), U(h)R} and U(*)RV in {E(DP(*)), U(*)RV}, L1, L2, ---, LZ transform U(h)R and U(*)RV to U(h)R∙V = U(h)R∙V(1)∙V(2) ---V(Z) and U(*)R∙V∙Y = U(*)R∙V∙Y(Z)∙Y(Z-1) ---Y(1) by using their secret integers V(1), Y(1), V(2), Y(2), ---, V(Z), Y(Z).

Therefore, no one except P can know correspondences between P and each DP(h) or DP(*), or links between DP(1), DP(2), ---, DP(HP) unless all L1, L2, ---, LZ conspire (each Lz shuffles its encryption and decryption results). Nevertheless, A can identify triplets {1, E(DP(1)), U(1)R∙V}, ---, {NP, E(DP(HP)), U(HP)R∙V} that correspond to same data holder P, and P can know the sum of its attribute values{DP(*), U(*)RV∙Y}. To enable A to identify the triplets, provided that U(0) is a publicly known integer, L1, L2, ---, LZ defines their secret integers X(1, h), X(2, h), ---, X(Z, h) for each h and calculate U(1), U(2), ---, U(HP), as U(1) = U(0)X(1, 1)∙X(2, 1) --- X(Z, 1), U(2) = U(1)X(1, 2)∙X(2, 2) --- X(Z, 2), ---, U(HP) = U(HP-1)X(1, HP)∙X(2, HP) --- X(Z, HP). Then, L1, L2, ---, LZ calculate U(*)RV = U(h)RV∙X(1, h+1) --- X(Z, h+1)∙X(1, h+2) --- X(Z, h+2) --- X(1, HP) --- X(Z, HP) for each U(h)RV, and A identifies triplets {1, E(DP(1)), U(1)R∙V}, ---, {HP, E(DP(HP)), U(HP)R∙V} based on U(*)RV calculated from U(1)R∙V, ---, U(HP)R∙V. On the other hand, P calculates U(*)RV∙Y from U(*)V∙Y by using its secret integer R to identify {DP(*), U(*)RV∙Y}.

About calculation of DP(*) = DP(1)+DP(2)+ --- +DP(HP), L1, L2, ---, LZ encrypts each DP(h) by additive encryption functions, as a result, E(DP(1))+E(DP(2))+ --- +E(DP(HP)) is decrypted to DP(*). A and L1, L2, ---, LZ also can convince others of their honest handling of each triplet without disclosing their secret keys or integers provided that dishonesties bring losses to some entity.

4. Behaviors of the e-Cash Scheme

The proposed scheme of e-cash systems consists of 5 phases, i.e. registration, issuing, paying, reporting and verification phases. Here, authority A is accompanied by linear Mix-net L consists of mix-servers L1, L2, ---, LZ. Also provided that H is the maximum number of payments that a single cash holder makes within a service period, each mix-server Lz maintains its secret integers X(z, 1), X(z, 2), ---, X(z, H), and for each h (0 < h ≤ H), L1, L2, ---, LZ jointly calculates integer Uh as Uh = Uh-1X(h) = Uh-1X(1, h)∙X(2, h) --- X(Z, h) to be disclosed publicly, as in the previous section. Therefore, no one can know integer X(h) unless all L1, L2, ---, LZ conspire. Then, first 4 phases proceed as shown in Figure 2.

An important thing is, different from other e-cash schemes, validity of e-cash that each cash holder Pm pays is not ensured by authority A’s signature because in offline environments even A’s signature cannot disable cash holders to spend same e-cash multiple times. Instead, validity of e-cash Pm pays is ensured by the anonymous signature of Pm, in other words, the issuer of e-cash Pm pays is Pm itself. Here, anonymous signatures enable signers to conceal their identities.

4.1. Registration Phase

Each cash holder Pm registers itself and obtains its credential and cash-IDs while revealing its identity as below. In the following phases, Pm uses its credential and cash-IDs to show its eligibility and to divide its e-cash respectively of course without revealing its identity. Pm uses credentials also to generate its anonymous signatures. On the other hand, authority A uses anonymous signatures and cash-IDs to identify dishonest cash holders and to calculate total cash values of e-cash generated by dividing same e-cash, respectively.

1. Pm shows A its identity.

2. If Pm is eligible, A issues credential T(A, TPm, Rm) and cash-IDs T*(A, TPm(1), Rm(1)), T*(A, TPm(2), Rm(2)), ---, T*(A, TPm(H), Rm(H)) to Pm.

3. Pm calculates initial used seal U_Rm from publicly disclosed constant integer U_ by using T(A, TPm, Rm).

4. A registers Pm as an authorized member with initial used seal U_Rm.

Here, A uses initial used seal U_Rm to disable Pm to use credentials of other cash holders. In detail, at a time when A requests Pm to calculate a used seal of T(A, TPm, Rm) from integer λ while showing its identity, A asks Pm to calculate a used seal also from integer U_. Namely, if Pm calculated λR* by using a credential of other entity, Pm calculates U_R* from U_ that is different from initial used seal U_Rm. About cash-IDs, each T*(A, TPm(h), Rm(h)) has the same structure as credential T(A, TPm, Rm). But to discriminate credentials from cash-IDs A defines different signing keys, i.e. A uses keys pairs {d1, d2} and {d1*, d2*} to generate credentials and cash-IDs, respectively.

Secret unique integers Rm = Rm(0), Rm(1), Rm(2), ---, Rm(H) in the credential and cash-IDs are generated through the cooperation among L1, L2, ---, LZ. Namely provided that Ω is a publicly known integer, for each h (h = 0, 1, 2, ---, H), each mix-server Lz generates secret integer Rm(z, h) and calculates ΩRm(z*, h) = ΩRm((z-1)*, h)∙Rm(z, h) based on ΩRm((z-1)*, h) disclosed by Lz-1, and when finally disclosed ΩRm(Z*, h) did not appear before each Lz informs Pm of Rm(z, h) so that Pm can calculate unique secret integer Rm(h) as product Rm(h) = Rm(1, h)∙Rm(2, h) --- Rm(Z, h). When ΩRm(Z*, h) had appeared already, L1, L2, ---, LZ generate different secret integers [8, 11].

4.2, Issuing Phase

Authority A issues its i-th e-cash C(A, i) to cash holder Pm as t-th e-cash of Pm without knowing Pm as below.

1. Pm generates secret integers Vm(t) and V*m(t), and convinces A of its ownerships of credential T(A, TPm, Rm) and t-th cash-ID T*(A, TPm(t), Rm(t)) by showing T(A, TPm, Rm)Vm(t) and T*(A, TPm(t), Rm(t))V*m(t).

2A defines cash value e(i) and expiration time d(i).

3. Pm calculates source-ID part value U0Rm(t) and payee’s signature {U0Rm(t)+e(i)║d(i)}Rm from integer U0, e(i) and d(i) as used seals of T*(A, TPm(t), Rm(t)) and T(A, TPm, Rm). Here, notation ║ represents concatenation, and cash value e(i) and expiration time d(i) are integers.

4. If U0Rm(t) did not appear before, A constructs cash issuing record I(i) = <e(i), d(i), 0, U0Rm(t), {U0Rm(t)+e(i)║d(i)}Rm> shown in Figure 3 (a) and gives I(i) to Pm. A also discloses I(i) publicly in its database.

5. Pm pays cash value e(i) through its anonymous credit card, or it simply pays real cash of value e(i) to A.

In the above, Pm chooses its t-th cash-ID for obtaining its t-th e-cash (actually Pm can choose an arbitrary cash-ID but step 4 disables Pm to use same cash-IDs repeatedly), as a result, Pm uses different cash IDs for different e-cash. Also, it changes values of secret integers Vm(t) and V*m(t) every time when it accesses A, therefore A cannot identify Pm or know links between individual e-cash Pm had obtained. But to maintain its anonymity Pm must buy C(A, i) by its anonymous credit card or by paying real cash.

About the issuing record in Figure 3 (a), division-No. part value 0 represents that C(A, i) is the original e-cash directly issued by A (i.e. it is the 0-th division). Together with division-ID part values in cash paying records shown in Figure 3 (b), source-ID part value U0Rm(t) enables A to identify e-cash that are generated by dividing C(A, i) without knowing links between C(A, i) and individual divided e-cash. Payee’s signature {U0Rm(t)+e(i)║d(i)}Rm is used to identify dishonest cash holders without knowing secrets of honest entities, as will be discussed in Sec. 5.

Here, Pm calculates U0Rm(t) and {U0Rm(t)+e(i)║d(i)}Rm as used seals of T*(A, TPm(t), Rm(t)) and T(A, TPm, Rm), therefore although A does not know values of Rm(t) or Rm, it can convince itself that Pm calculates them honestly. Also {U0Rm(t)+e(i)║d(i)}Rm can be considered as an anonymous signature of Pm [11], i.e. no one except Pm can know Pm from credential form T(A, TPm, Rm)W, {U0Rm(t)+e(i)║d(i)}Rm can be calculated only by Pm that knows integer Rm, correct calculation of {U0Rm(t)+e(i)║d(i)}Rm is ensured despite Rm is unknown, and by calculating a used seal of T(A, TPm, Rm) from integer U0Rm(t)+e(i)║d(i), Pm can convince any entity that {U0Rm(t)+e(i)║d(i)}Rm was generated by it.

About the expiration time d(i) of C(A, i), because it may be used as a clue to identify Pm, all e-cash issued in a same service period have same expiration time. Also, C(A, i) and all e-cash generated by dividing C(A, i) have the same expiration time.

4.3. Paying Phase

Paying phase, in which Pm makes its purchase and pays e-cash C(Pm, t, h) to other cash holder Pk by dividing e-cash C(A, i) or C(Pj, s, v), proceeds as follow. Here, C(A, i) or C(Pj, s, v) is Pm’s t-th e-cash that it had received directly from issuing authority A or from other cash holder Pj respectively. Here as a special case, to exchange a part of C(A, i) or C(Pj, s, v) for real cash, Pm pays C(Pm, t, h) to itself. In the following, it is assumed that Pm generates C(Pm, t, h) as the h-th division of C(A, i) or C(Pj, s, v), and Pk receives C(Pm, t, h) as its q-th e-cash. About cash-IDs, although Pk below chooses its q-th cash-ID to receive its q-th e-cash, it can choose an arbitrary unused cash-ID.

1. Pm generates secret integers Wm(t, h) and W*m(t, h), shows credential T(A, TPm, Rm) and t-th cash-ID T*(A, Tm(t) Rm(t)) in forms T(A, TPm, Rm)Wm(t, h) and T*(A, TPm(t), Rm(t))W*m(t, h) and convinces Pk of its eligibility and the ownership of T*(A, TPm(t), Rm(t)).

2. Pk generates secret integers Vk(q) and V*k(q), chooses q-th cash-ID T*(A, Tk(q), Rk(q)), shows credential T(A, TPk Rk) and T*(A, Tk(q), Rk(q)) in forms T(A, TPk, Rk)Vk(q) and T*(A, TPk(q), Rk(q))V*k(q), and convinces Pm of its eligibility and the ownership of T*(A, TPk(q), Rk(q)).

3. Pm defines cash value e(Pm, t, h) and expiration time d(Pm, t, h), calculates division-ID part value UhRm(t) from integer Uh by using cash-ID T*(A, TPm(t), Rm(t)), and informs Pk of quadruplet <e(Pm, t, h), d(Pm, t, h), h, UhRm(t)>.

4. Pk calculates source-ID part value U0Rk(q) from U0 as a used seal of T*(A, TPk(q), Rk(q)).

5. Pm calculates payer’s signature S(Rm, G(Pm, t, h)) = G(Pm, t, h)Rm as a used seal of T(A, TPm, Rm), and constructs paying record P(Pm, t, h) = <e(Pm, t, h), d(Pm, t, h), h, UhRm(t), U0Rk(q), S(Rm, G(Pm, t, h))> to give Pk as shown in Figure 3 (b). Where, G(Pm, t, h) = UhRm(t)+U0Rk(q)+e(Pm, t, h)║d(Pm, t, h).

In the above, Pm and Pk show their credentials and cash-IDs while modifying them by their secret integers Wm(t, h), W*m(t, h), Vk(q) and V*k(q), therefore Pm and Pk can make them anonymous as same as in the issuing phase. Also Pm can conceal links among e-cash it generates from C(A, i) or C(Pj, s, v). Nevertheless, Pk can confirm correct calculations of division-ID part value UhRm(t) and payer’s signature S(Rm, G(Pm, t, h)) because Pm calculates them as used seals of its cash-ID and credential. In the same way, Pm can confirm Pk’s correct calculation of source-ID part value U0Rk(q).

Here as discussed in the previous subsection, together with the source-ID part value in issuing record I(i) and/or paying record P(Pj, s, v), division-ID part value UhRm(t) in P(Pm, t, h) enables A to confirm that Pm had honestly divided its t-th e-cash C(A, i) or C(Pj, s, v) without knowing Pm, C(A, i) or C(Pj, s, v). A can also identify dishonest entities by exploiting payer’s signatures in paying records together with payee’s signatures that are calculated at step 2 in the reporting phase.

About dishonesties of cash holders, because Pm and Pk interact under offline environments, both of Pm and Pk can forge paying records without being noticed by Pk or Pm, e.g. Pm may calculate the division-ID part value while using a cash-ID different from T*(A, Tm(t) Rm(t)), also Pk may modify the cash value, the expiration time or the division-ID part value in P(Pm, t, h) after it had received it from Pm. But these dishonesties are detected and liable entities are identified while exploiting division-ID and source-ID parts values and payer’s and payee’s signatures as will be discussed in Sec. 5.

4.4. Reporting Phase

In this phase, cash holder Pk that received its q-th e-cash C(Pm, t, h) from other cash holder Pm as paying record P(Pm, t, h) = <e(Pm, t, h), d(Pm, t, h), h, UhRm(t), U0Rk(q), S(Rm, G(Pm, t, h))>, reports P(Pm, t, h) to A by the expiration time of C(Pm, t, h). Also, A pays real cash of value e(Pm, t, h) to Pk, if Pk wants cashing of C(Pm, t, h). The reporting phase proceeds as below.

1. Pk generates secret integers Wk(q, 0) and W*k(q, 0), and shows its credential and q-th cash-ID in forms T(A, TPk, Rk)Wk(q, 0) and T*(A, Tk(q), Rk(q))W*k(q, 0) to convince A of its eligibility and the ownership of the cash-ID.

2. Pk shows paying record P(Pm, t, h) to A, and calculates source-ID part value U0Rk(q) from U0 and payee’s signature S(Rk, S(Rm, G(Pm, t, h))) = S(Rm, G(Pm, t, h))Rk = G(Pm, t, h)Rm∙Rk from S(Rm, G(Pm, t, h)) by its q-th cash-ID and credential, respectively.

3. If Pk calculates source-ID part value U0Rk(q) successfully and U0Rk(q) did not appear before, A accepts P(Pm, t, h) and discloses it publicly with the payee’s signature, provided that P(Pm, t, h) does not expire.

4. When Pk wants cashing and no one exchanged C(Pm, t, h) for real cash yet, A pays real cash of value e(Pm, t, h) to Pk. A also modifies source-ID part value in P(Pm, t, h) to 0. Where, source-ID part value 0 means Pk cannot generate new e-cash from C(Pm, t, h).

5. Pk calculates used seal of its q-th cash-ID from integer U_, i.e. U_Rk(q), as a receipt, and A discloses P(Pm, t, h) with the receipt publicly.

In the above, because source-ID part value U0Rk(q) can be calculated only by cash-ID T*(A, Tk(q), Rk(q)) and Pk must calculate it honestly, anyone except Pk cannot report P(Pm, t, h) or exchange C(Pm, t, h) for real cash unless it is conspiring with Pk. In the same way, receipt U_Rk(q) disables Pk to exchange C(Pm, t, h) for real cash repeatedly. Also, Pk can convince A of correct calculation of payee’s signature without revealing its identity or secret integer Rk, then it can maintain its anonymity as same as in the paying phase.

About dishonest cash holders, because A discloses paying record P(Pm, t, h) at step 3, cash holders become able to use division-ID part value UhRm(t) calculated by Pm to generate or modify their paying records. But it must be noted that step 3 disables cash holders to use same source-ID part values repeatedly. As a result, all paying records have different source-ID part values, and this means cash holders including Pk cannot forge paying records that include consistent payer’s signatures of Pm without the help of Pm (only Pm can generate consistent signatures of Pm on information that includes newly appearing source-ID part values). Therefore, when multiple paying records with consistent payer’s signatures and same division-ID part value UhRm(t) are detected, A can regard Pm as the liable entity. In other words, entities other than Pm cannot generate a paying record with division-ID part value UhRm(t) and consistent payer’s signature of Pm without the help of Pm despite UhRm(t) is disclosed.

5. Verification Phase

The verification phase that consists of dishonest record detection and dishonest entity identification stages detects dishonesties of entities and identifies entities that are liable for them.

In offline environments, payees cannot know whether payers are generating new e-cash so that their cash values do not exceed cash values of original e-cash or not. Authority A cannot sign on paying records that payers generate either. As a result, cash holders can behave dishonestly without being noticed by others. As shown below, there are 8 kinds of possibilities that entities involved behave dishonestly. Here in the following it is assumed that to pay Pk cash holder Pm generates e-cash C(Pm, t, h) and corresponding cash paying record P(Pm, t, h) from e-cash C(Pj, s, v) that Pm had obtained from Pj. But illegitimate paying records are detected and liable entities are identified in the same way also in cases where Pm generates C(Pm, t, h) from C(A, i) directly issued from A.

a. Pm generates e-cash from C(Pj, s, v) more than the cash value of C(Pj, s, v).

b. Pm generates paying record P(Pm, t, h) to give to Pk while forging the expiration time or calculating a division-ID part value by a cash-ID different from T*(A, TPm(t), Rm(t)) (but Pm must use its cash-ID if Pk is honest, because Pk examines the division-ID part value at step 3 in the paying phase).

c. Pm does not report paying record P(Pj, s, v) to A.

d. Pk reports paying record P(Pm, t, h) to A while modifying it, e.g. changing its cash value, expiration time or division-ID part value. Or to use e-cash C(Pm, t, h) repeatedly, it reports P(Pm, t, h) multiple times while changing source-ID part values (source-ID part values must be unique to individual e-cash).

e. Other cash holder Pj reports P(Pm, t, h) to A while changing the source-ID part value in it. Where, Pj can obtain P(Pm, t, h) because A discloses it at step 3 in the reporting phase, or Pj may steal it by eavesdropping on interactions between Pm and Pk. But Pj must calculate the source-ID part value by its cash-ID because A examines the consistency between the source-ID part value and the cash-ID of Pj.

f. Authority A arbitrarily forges paying records.

Namely, because Pm or Pk cannot know e-cash generated and used in other places in offline environments and A in the reporting phase can examine only source-ID part values and payee’s signatures in individual paying records, Pm can generate e-cash from C(Pj s, v) more than its cash value, can generate P(Pm, t, h) while using a cash-ID different from T*(A, Tm(t), Rm(t)) used to calculate the source-ID part value of P(Pj, s, v), or may not report P(Pj, s, v) to A. Also, Pk can report P(Pm, t, h) to A while modifying its cash value, expiration time and/or division-ID part value.

As the more vicious dishonesty, when other cash holder Pj steals P(Pm, t, h) given to Pk and reports it to A (of course while changing the source-ID part value), Pj becomes able to generate e-cash from Pk’s e-cash C(Pm, t, h). Also, when authority A is dishonest, it can forge paying records arbitrarily to be registered in its database. Where about conspiracy between Pm and Pk, although it enables them to forge consistent paying records, they cannot reap any benefit as a total, i.e. one of Pm and Pk must compensate losses caused by the forged e-cash.

But it must be noted that cash holders must report paying records while generating source-ID part values and payee’s signatures by their legitimate cash-IDs and credentials, i.e. A examines them at steps 2 and 3 in the reporting phase. In addition, all paying records must have different source-ID values, and once authority A had accepted paying records, anyone including A and mix-servers in Mix-net L must honestly handle them, i.e. all paying records are publicly disclosed, and honest encryptions and decryptions of L are ensured [10].

Then, without knowing secrets of honest entities, the dishonest record detection and the dishonest entity identification stages become able to detect above dishonesties and identify liable entities as in the following subsections.

5.1. Dishonest Record Detection Stage

The dishonest record detection stage detects dishonesties while exploiting division-ID and source-ID parts values in paying records and issuing records. Namely, although additional mechanisms are necessary so that Pm can conceal links between C(Pm, t, 1), C(Pm, t, 2), ---, C(Pm, t, H(m, t)) it had generated from same e-cash C(Pj, s, v) from others, while exploiting relation UhRm(t)∙X(h+1)X(h+2) --- X(H) = U0Rm(t)∙X(1)X(2) --- X(H) = U0Rm(t)∙X*, A can determine paying record P(Pm, t, h) accompanied by division-ID value UhRm(t) was generated from P(Pj, s, v) when its source-ID part value U0Rm(t) is converted to U0Rm(t)∙X*. Therefore, if A gathers P(Pm, t, 1), P(Pm, t, 2), ---, P(Pm, t, H(m, t)), and compares cash values of C(Pm, t, 1), C(Pm, t, 2), ---, C(Pm, t, H(m, t)) and C(Pj, s, v), A can examine whether all C(Pm, t, 1), C(Pm, t, 2), ---, C(Pm, t, H(m, t)) were honestly generated and handled or not. Here, if Pm did not report P(Pj, s, v) to A or P(Pj, s, v) had expired already, A cannot use relation UhRm(t)∙X(h+1) --- X(H) = U0Rm(t)∙X* to find C(Pj, s, v) from which C(Pm, t, h) was generated. But in this case, A identifies each C(Pm, t, h) as an orphan paying record that cannot be corresponded to any paying or issuing record. As a result, every kind of dishonesties at the beginning of this section can be detected as inconsistent division-IDs and source-ID pairs or orphan paying records.

Figure 4. Expenditure, new-cash and total expenditure records

To implement the above strategies, authority A constructs expenditure record D(Pm, t, h) = <e(Pm, t, h), h, UhRm(t), G(Pm, t, h), S(Rm, G(Pm, t, h)), S(Rk, S(Rm, G(Pm, t, h)))> and new-cash record N(Pm, t, h) = <e(Pm, t, h), U0Rk(q)> from paying record P(Pm, t, h) = <e(Pm, t, h), d(Pm, t, h), h, UhRm(t), U0Rk(q), S(Rm, G(Pm, t, h))> as shown in Figure 4 (a) and (b). Here, record characterizer part value G(Pm, t, h) and payer’s signature S(Rm, G(Pm, t, h)) are UhRm(t)+U0Rk(q)+e(Pm, t, h)║d(Pm, t, h) and G(Pm, t, h)Rm respectively, and payee’s signature S(Rk, S(Rm,G(Pm, t, h))) = G(Pm, t, h)RmRk is calculated when Pk reports P(Pm, t, h) to A. In addition to the above records, total expenditure records are defined as shown in Figure 4 (c).

Authority A detects inconsistent division-IDs and source-ID pairs and orphan paying records without knowing secrets of honest entities while exploiting linear Mix-net L = {L1, L2, ---, LZ} as follows.

1. For each paying record P(Pm, t, h) = <e(Pm, t, h), d(Pm, t, h), h, UhRm(t), U0Rk(q), S(Rm, G(Pm, t, h))>, which is valid in a considering service period, A constructs expenditure record D(Pm, t, h) = <e(Pm, t, h), h, UhRm(t), G(Pm, t, h), S(Rm, G(Pm, t, h)), S(Rk, S(Rm, G(Pm, t, h)))> and new-cash record N(Pm, t, h) = <e(Pm, t, h), U0Rk(q)>, and put D(Pm, t, h) in linear Mix-net L. Here, S(Rk, S(Rm, G(Pm, t, h))) is the payee’s signature accompanying P(Pm, t, h).

2. Mix-servers L1, L2, ---, LZ repeatedly encrypt expenditure records put by A while shuffling their encryption results. Here, value part e(Pm, t, h) in each D(Pm, t, h) is encrypted to E(e(Pm, t, h)) by additive encryption functions of L1, L2, ---, LZ, but L does not encrypt division-No. part value h as the attribute No. in Sec. 3.2. About division-ID part value UhRm(t), provided that λ(1), λ(2), ---,λ(Z) are secret integers of L1, L2, ---, LZ, λ* =λ(1)∙λ(2) --- λ(Z), X*(z, h) = X(z, h)∙X(z, h+1) --- X(z, H) and X* = X(1)∙X(2) --- X(H), each Lz transforms (encrypts) UhRm(t)∙{X*(1, h+1)∙λ(1)}∙{X*(2, h+1)∙λ(2)}---{X*(z-1, h+1)∙λ(z-1)} calculated by Lz-1 to UhRm(t)∙{X*(1, h+1)∙λ(1)}∙{X*(2, h+1)∙λ(2)}---{X*(z-1, h+1)∙λ(z-1)}∙{X*(z, h+1)∙λ(z)}, while referring to division No. part value h. As a result UhRm(t) is transformed to UhRm(t)∙X(h+1)∙X(h+2) ---X(H)∙λ(1)∙λ(2)---∙λ(z) = U0Rm(t)∙X*∙λ* (as shown in Sec. 4, X(h) = X(1, h)∙X(2, h) --- X(Z, h)). In the same way, L1, L2, ---, LZ transform record characterizer part value G(Pm, t, h), payer’s signature S(Rm, G(Pm, t, h)) and payee’s signature S(Rk, S(Rm, G(Pm, t, h))) to G(Pm, t, h)λ*, S(Rm, G(Pm, t, h))λ* and S(Rk, S(Rm, G(Pm, t, h)))λ*. In conclusion, D(Pm, t, h) is encrypted to E(D(Pm, t, h)) = <E(e(Pm, t, h)), h, U0Rm(t)∙X*∙λ*, G(Pm, t, h)λ*, S(Rm, G(Pm, t, h))λ*, S(Rk, S(Rm,G(Pm, t, h)))λ*>.

3. A gathers encrypted expenditure records E(D(Pm, t, 1)), E(D(Pm, t, 2)), ---, E(D(Pm, t, H(m, t)) that include same division-ID part value U0Rm(t)∙X*∙λ*, calculates E(e(Pm, t, 1))+E(e(Pm, t, 2))+ --- +E(e(Pm, t, H(m, t))) = E(e(Pm, t, 1)+e(Pm, t, 2)+ --- +e(Pm, t, H(m, t))) =E(e*(Pm, t)), and constructs encrypted total expenditure record E(Sum(Pm, t)) = <E(e*(Pm, t)), U0Rm(t)∙X*∙λ*, G(Pm, t, 1)λ*, S(Rm, G(Pm, t, 1))λ*> to put in L. Where, H(m, t) is the largest division No. part value generated from C(Pj, s, v).

4. LZ, LZ-1, ---, L1 repeatedly decrypt each encrypted total expenditure record E(Sum(Pm, t)) put by A while shuffling their decryption results, and as a result E(Sum(Pm, t)) is decrypted to total expenditure record Sum(Pm, t) = <e*(Pm, t) = e(Pm, t, 1)+e(Pm, t, 2)+ --- +e(Pm, t, H(m, t)), U0Rm(t)∙X*∙λ*∙μ*, G(Pm, t, 1)λ*∙μ*, S(Rm, G(Pm, t, 1))λ*∙μ*>. Here mix-servers must shuffle also their decryption results to protect their additive encryption functions which are usually weak against plain text attacks. About the division-ID part value, provided that μ(1), μ(2), ---, μ(Z) are secret integers of L1, L2, ---, LZ and μ* = μ(1)∙μ(2) --- μ(Z), each Lz transforms (decrypts) U0Rm(t)∙X*∙λ*∙μ(Z)∙μ(Z-1)---μ(z+1) calculated by Lz+1 to U0Rm(t)∙X*∙λ*∙μ(Z)∙μ(Z-1)---μ(z+1)∙μ(z), and as a result U0Rm(t)∙X*∙λ* is transformed to U0Rm(t)∙X*∙λ*∙μ*. In the same way G(Pm, t, 1)λ* and S(Rm, G(Pm, t, 1))λ* are transformed to G(Pm, t, 1)λ*∙μ* and S(Rm, G(Pm, t, 1))λ*∙μ*.

5. For each issuing record I(i) = <e(i), d(i), 0, U0Rm(t), {U0Rm(t)+e(i)║d(i)}Rm> which does not expire, A constructs new-cash record N(A, i, 0) = <e(i), U0Rm(t)> and put it in L together with new cash records generated at step 1.

6. By using integers λ(1), λ(2), ---,λ(Z), X(1), X(2), ---, X(H), and μ(1), μ(2), ---, μ(Z), mix-servers L1, L2, ---, LZ calculate U0Rk(q)∙X*∙λ*∙μ* or U0Rm(t)∙X*∙λ*∙μ* from U0Rk(q) or U0Rm(t) in each N(Pj, s, v) or N(A, i, 0) to transform it to N*(Pj, s, v) = <e(Pm, t, h), U0Rk(q)∙X*∙λ*∙μ*> or N*(A, i, 0) = <e(i), U0Rm(t)∙X*∙λ*∙μ*>.

7. For each total expenditure record Sum(Pm, t), A finds a transformed new-cash record that includes U0Rm(t)∙X*∙λ*∙μ* as its source-ID part value. Where, because all paying records have different source-ID part values, A can find at most one transformed new-cash record.

8. Provided that N*(Pj, s, v) = <e(Pj, s, v), U0Rm(t)∙X*∙λ*∙μ*> is the found transformed new-cash record, A examines whether relation e*(Pm, t) ≤ e(Pj, s, v) holds or not, and when the relation does not hold it determines that Sum(Pm, t) is an illegitimate total expenditure record. When no new-cash record that corresponds to Sum(Pm, t) is found, A determines Sum(Pm, t) is an orphan record.

In the above steps, because U1, U2, ---, UH are calculated as U1 = U0X(1), U2 = U0X(1)∙X(2),---, UH = U0X(1)∙X(2) --- X(H), division-ID part values of all expenditure records that correspond to e-cash generated from e-cash C(Pj, s, v) and source-ID part value U0Rm(t) of N(Pj, s, v) are transformed to same value U0Rm(t)∙X*∙λ*∙μ*. Therefore A can identify expenditure records generated from C(Pj, s, v) as the ones that are accompanied by division-ID part value U0Rm(t)∙X*∙λ*∙μ*. Also, because linear Mix-net L encrypts e(Pm, t, 1), e(Pm, t, 2), ---, e(Pm, t, H(m, t)) in expenditure records by additive encryption functions, E(e(Pm, t, 1))+E(e(Pm, t, 2))+ --- +E(e(Pm, t, H(m, t))) is decrypted to e*(Pm, t) = e(Pm, t, 1)+e(Pm, t, 2)+ --- +e(Pm, t, H(m, t)), i.e. the sum of cash values generated from C(Pj, s, v). As a result, A can determine that cash holder Pm had honestly divided its e-cash C(Pj, s, v) when e*(Pm, t) does not exceed e(Pj, s, v).

Nevertheless, cash holder Pm can conceal its payments and links between its individual payments from others. Because integers Rm, Rm(t) are Pm’s secrets, other entities including A cannot know Pm from issuing record I(i) or paying record P(Pm, t, h). About links between C(Pm, t, 1), C(Pm, t, 2), ---, C(Pm, t, H(m, t)), to calculate X(h) from Uh-1Rm(t) and Uh-1Rm(t)∙X(h) is a discrete logarithm problem, and entities other than Pm cannot identify sequence U0Rm(t), U1Rm(t), U2Rm(t), ---, UHRm(t).

5.2. Dishonest Entity Identification Stage

As in the previous subsection dishonestly handled paying records are detected as inconsistent total expenditure and new-cash records pairs or orphan total expenditure records, and once dishonesties are detected, A identifies liable entities without knowing secrets of honest entities by the procedure below. In the following it is assumed that total expenditure record Sum(Pm, t) = <e*(Pm, t), U0Rm(t)∙X*∙λ*∙μ*, G(Pm, t, 1)λ*∙μ*, S(Rm, G(Pm, t, 1))λ*∙μ*> that corresponds to cash holder Pm is illegitimate, i.e. e*(Pm, t) in Sum(Pm, t) is greater than e(Pj, s, v) in transformed new-cash record N*(Pj, s, v) = <e(Pj, s, v), U0Rm(t)∙X*∙λ*∙μ*>, or Sum(Pm, t) is an orphan record.

Although additional steps are required to protect secret information of honest entities, conceptually, after detecting illegitimate total expenditure record Sum(Pm, t), A discloses Sum(Pm, t) and asks all cash holders to calculate used seals of their credentials from record characterizer part value G(Pm, t, 1)λ*∙μ* in Sum(Pm, t) while revealing their identities. Then, Pm that calculates S(Rm, G(Pm, t, 1))λ*∙μ* = G(Pm, t, 1)Rm∙λ*∙μ* is liable, i.e. only Pm that knows integer Rm can calculate S(Rm, G(Pm, t, 1))λ*∙μ* from G(Pm, t, 1)λ*∙μ* and Pm must honestly calculate S(Rm, G(Pm, t, 1))λ*∙μ* from G(Pm, t, 1)λ*∙μ* as a used seal of its own credential.

However, if record characterizer and payers’ signature pair {G1, G2} in P(Pm, t, 1) is the one forged by Pm or someone else no one calculates G2λ*∙μ* from G1λ*∙μ*. Therefore in this case, A finds encrypted expenditure record E(D(Pm, t, 1)) that was used to calculate E(Sum(Pm, t)) at step 3 in the dishonest record detection stage, and asks all cash holders to calculate used seals of their credentials from payer’s signature G2λ*, and determines Pk is liable when it calculates G2λ*∙Rk that is equal to the payee’s signature G2Rk∙λ* in E(D(Pm, t, 1)).

Namely, authority A examines payee’s signature G2Rk when it accepts paying record P(Pm, t, h), and Pk must honestly calculate it as a used seal of its credential. Also, Pk verifies the consistency of pair {G1, G2} at a time when Pm paid C(Pm, t, h) to it. In addition, anyone including A and mix-servers cannot handle paying records dishonestly after they are disclosed. Then, regardless that entities other than Pk itself had forged {G1, G2} or not, A can determine Pk is liable, i.e. Pk had accepted P(Pm, t, h) that includes inconsistent {G1, G2}. As an exception if it is conspiring with A, Pk does not need to calculate G2Rk honestly by using its credential when it reports P(Pm, t, h). But even in this case A cannot impute the liability to honest cash holders, i.e. A cannot forge payee’s signatures of honest cash holders and must compensate corresponding losses by itself.

In detail, the dishonest entity identification stage proceeds as follow.

1. A asks mix-servers LZ, LZ-1, ---, L1 to trace (partial) encryption forms of illegitimate total expenditure record Sum(Pm, t) = <e*(Pm, t), U0Rm(t)∙X*∙λ*∙μ*, G(Pm, t, 1)λ*∙μ*, S(Rm, G(Pm, t, 1))λ*∙μ*> calculated at step 4 in Sec. 5.1 back to E(Sum(Pm, t)) = <E(e*(Pm, t)), U0Rm(t)∙X*∙λ*, G(Pm, t, 1)λ*, S(Rm, G(Pm, t, 1))λ*>, and finds encrypted expenditure records E(D(Pm, t, 1)) = <E(e(Pm, t, 1)), 1, U0Rm(t)∙X*∙λ*, G(Pm, t, 1)λ*, S(Rm, G(Pm, t, 1))λ*, S(Rk, S(Rm, G(Pm, t, 1)))λ*>, E(D(Pm, t, 2)), ---, E(D(Pm, t, H(m, t))) that constitute E(Sum(Pm, t)).

2. A discloses illegitimate total expenditure record Sum(Pm, t) with individual encrypted expenditure records E(D(Pm, t, 1)), E(D(Pm, t, 2)), ---, E(D(Pm, t, H(m, t))) publicly.

3. For each illegitimate Sum(Pm, t) = <e*(Pm, t), U0Rm(t)∙X*∙λ*∙μ*, G(Pm, t, 1)λ*∙μ*, S(Rm, G(Pm, t, 1))λ*∙μ*>, each Pr calculates G(Pm, t, 1)λ*∙μ*∙Rr from G(Pm, t, 1)λ*∙μ* by using its credential T(A, TPr, Rr).

4. When Pm calculates G(Pm, t, 1)λ*∙μ*∙Rm that coincides with S(Rm, G(Pm, t, 1))λ*∙μ*, and Pm admits e*(Pm, t) in Sum(Pm, t) is its correct total expenditure or expenditure records included in orphan record Sum(Pm, t) had already expired, Pm pays cash of value {e*(Pm, t) - e(Pj, s, v)} to A possibly with arrears but without revealing its identity. In a case where Sum(Pm, t) is an orphan record Pm pays e*(Pm, t).

5. On the other hand when Pm does not believe that e*(Pm, t) is its correct total expenditure or expenditure records included in Sum(Pm, t) had expired, it examines payer’s signatures in disclosed individual encrypted expenditure records. In detail, for each encrypted record E(D(Pm, t, h)), Pm extracts pair {G(Pm, t, h)λ*, S(Rm, G(Pm, t, h))λ*} to examine whether relation G(Pm, t, h)λ*∙Rm = S(Rm, G(Pm, t, h))λ* holds or not. After that when relation G(Pm, t, h)λ*∙Rm = S(Rm, G(Pm, t, h))λ* does not hold, Pm without revealing its identity claims that E(D(Pm, t, h)) is not its record while convincing A that S(Rm, G(Pm, t, h))λ* is not calculated by its credential (A receives this claim at step 9).

6. In a case where relation G(Pm, t, h)λ*∙Rm = S(Rm, G(Pm, t, h))λ* holds but Pm does not believe that E(D(Pm, t, h)) had expired, Pm picks P(Pj, s, v) from which it had generated P(Pm, t, h), and claims that the expiration time in P(Pj, s, v) is incorrect without revealing its identity.

7. When Pm claims that the expiration time in P(Pj, s, v) = <e(Pj, s, v), d(Pj, s, v), v, UvRj(s), U0Rm(t), S(Rj, G(Pj, s, v))> is incorrect, A requests all cash holders to calculate used seal of G(Pj, s, v) while revealing their identities.

8. A determines cash holder Pj that calculates payer’s signature S(Rj, G(Pj, s, v)) from G(Pj, s, v) had included a wrong value as the expiration time in P(Pj, s, v) to give to Pm, and Pj pays e(Pj, s, v) to A with penalty fine. But A determines Pm had accepted incorrect P(Pj, s, v) intentionally when no one calculates S(Rj, G(Pj, s, v)), and to identify Pm proceeds to step 11.

9. When anonymous Pm claims that E(D(Pm, t, h)) is not its expenditure record, A requests all cash holders to calculate used seals of their credentials from payer’s signature S(Rm, G(Pm, t, h))λ* while revealing their identities.

10. A determines Pk that calculates payee’s signature S(Rk, S(Rm, G(Pm, t, h)))λ* = S(Rm, G(Pm, t, h))λ*∙Rk from S(Rm, G(Pm, t, h))λ* is liable and forces Pk to pay cash of value e(Pm, t, h)} with penalty fine.

11. If no one paid for illegitimate expenditure records corresponding to Sum(Pm, t) or claimed they were incorrect, or no one calculates payer’s signature S(Rj, G(Pj, s, v)) at step 8, firstly, A requests all cash holders to calculate used seals of their credentials from record characterizer value G(Pm, t, 1)λ* while revealing their identities. After that, A determines Pm that calculated S(Rm, G(Pm, t, 1))λ* is liable, and forces Pm to pay cash of value {e*(Pm, t) - e(Pj, s, v)} with penalty fine. When Sum(Pm, t) is an orphan record Pm pays e*(Pm, t).

12. If no one calculates S(Rm, G(Pm, t, 1))λ* in the previous step, A picks encrypted expenditure record E(D(Pm. t, 1)) = <E(e(Pm, t, 1)), 1, U0Rm(t)∙X*∙λ*, G(Pm, t, 1)λ*, S(Rm, G(Pm, t, 1))λ*, S(Rk, S(Rm, G(Pm, t, 1)))λ*> that constitutes Sum(Pm, t), and requests all cash holders to calculate used seals of their credentials from payer’s signature S(Rm, G(Pm, t, 1))λ* while revealing their identities.

13. A forces Pk that calculates payee’s signature S(Rk, S(Rm, G(Pm, t, 1)))λ* = S(Rm, G(Pm, t, 1))Rk∙λ* from S(Rm, G(Pm, t, 1))λ* to pay {e*(Pm, t) - e(Pj, s, v)} with penalty fine, but in a case where Sum(Pm, t) is an orphan record, Pk pays e*(Pm, t).

If cash holders honestly use their e-cash and handle their paying records, in other words, if cash values, expiration times, division-ID and source-ID parts values and payer’s signatures in individual paying records are honestly generated, reported and disclosed, apparently the above procedure successfully identifies dishonest entities while maintaining sensitive data as their secrets provided that authority A is honest (about payee’s signatures, cash holders must calculate them honestly as discussed before). When cash holder Pm generated new e-cash from its e-cash C(Pj, s, v) excessively by mistake, firstly at step 3, Pm knows that disclosed illegitimate total expenditure record Sum(Pm, t) corresponds to it, i.e. payer’s signature S(Rm, G(Pm, t, 1))λ*∙μ* in Sum(Pm, t) is calculated from record characterizer G(Pm, t, 1)λ*∙μ* only by using its credential, and at step 4, Pm pays the difference between its actual expenditure and the original cash value e*(Pm, t) - e(Pj, s, v) to A. Here, Pm is not requested to reveal its identity when it calculates S(Rm, G(Pm, t, 1))λ*∙μ*, and still can conceal the correspondence between it and its e-cash regardless that its mistake is intentional or not.

The procedure also identifies dishonest entities even when paying records are dishonestly generated and/or handled. Namely, if payee Pk is honest, because Pk examines the division-ID part value and the payer’s signature in paying record P(Pm, t, h) when payer Pm pays C(Pm, t, h), Pm must generate the payer’s signature honestly while using its credential. Therefore, A can determine that Pm is dishonest by examining payer’s signatures at step 11 even when P(Pm, t, h) was forged by Pm. On the other hand, in a case where Pk modified P(Pm, t, h) after having received it from Pm, Pk cannot include consistent payer’s signature of Pm in P(Pm, t, h) because all paying records must have different source-ID part values despite Pk does not know integer Rm. Then Pm claims that P(Pm, t, h) is incorrect at step 5, and because Pk must calculate its payee’s signature honestly when it reports P(Pm, t, h), A can determine that Pk is dishonest at steps 9 and 10, i.e. Pk had received an inconsistent paying record regardless that other entities are conspiring with it or not. In the same way, A can identify also other entities when they forge P(Pm, t, h), i.e. anyone other than Pm cannot forge paying record P(Pm, t, h) so that it becomes consistent with Pm’s credential.

About a case where Pm does not report paying record P(Pj, s, v) to A, each P(Pm, t, h) becomes an orphan record, and if Pk is honest, Pm that calculates payer’s signature S(Rm, G(Pm, t, 1))λ* is determined as liable, i.e. only Pm can calculate S(Rm, G(Pm, t, 1))λ* at step 11 as same as in the above. On the other hand when Pk is dishonest, Pm does not calculate S(Rm, G(Pm, t, 1))λ* because Pk cannot generate Pm’s payer’s signature consistently, and Pk is identified as an entity that had accepted inconsistent payer’s signature at step 12. In the same way, Pj that had paid expired e-cash C(Pj, s, v) to Pm while modifying the expiration time is identified at step 8. Lastly in a case where authority A is dishonest, even A cannot forge payer’s or payee’s signatures of honest cash holders consistently. Then, it cannot identify any liable entity and must compensate the corresponding losses by itself.

About the anonymity of cash holders, cash holders in Step 5 do not reveal their identities. Although each cash holder calculates used seals of its credential from G(Pm, t, h)λ* or S(Rm, G(Pm, t, h))λ* while revealing its identity at Steps 7, 9, 11 and 12, it did not calculate G(Pm, t, h)λ*∙Rj, G(Pm, t, h)λ*∙Rm, G(Pm, t, h)λ*∙Rk or S(Rm, G(Pm, t, h))λ*∙Rk before if it is honest. Therefore no one including A can identify payments of honest cash holders.

As another type of dishonesty although protection of this dishonesty is out of the scope of the proposed scheme, cash holders may disappear during interactions between them, e.g. a payee can disappear after it receives e-cash despite a payer does not complete its purchase yet. But these threats also can be removed easily by the secure object exchange scheme [11].

6. Conclusion

As discussed in previous sections the proposed scheme successfully satisfy anonymity, divisibility and transferability of e-cash in offline environments. Namely, honest cash holders can conceal correspondences between them and their e-cash and links between e-cash they had spent. Nevertheless, cash issuing authority A can identify liable entities when e-cash were illegitimately generated or used.

In addition, Pm can generate new e-cash C(Pm, t, 1), C(Pm, t, 2), ---, C(Pm, t, H(m, t)) of any values from its e-cash C(Pj, s, v) that it had received from other cash holder Pj provided that the total cash value of them does not exceed the cash value of C(Pj, s, v) as above, i.e. C(Pj, s, v) is divisible and transferable. But different from in other schemes, volume of information included in each e-cash does not increase even when it is transferred multiple times. Cash holders do not need to maintain receipts for transferring their e-cash either. In addition, an honest e-cash holder can conceal the correspondence between it and its e-cash even when the e-cash is a dishonestly transferred one. About divisibility, authority A does not need to define the minimum cash value unit in advance, and as a result, costs for handling e-cash can be decreased (the costs do not increase with the minimum cash value unit).

Drawbacks of the scheme are, firstly when cash holder Pk receives e-cash C(Pm, t, h) from Pm, it must report paying record P(Pm, t, h) to authority A through online communication channels, and secondly to generate new e-cash from existing e-cash each Pm must obtain numbers of cash-IDs in advance. But Pk is not required to report P(Pm, t, h) immediately, i.e. it can report it together with other paying records at its convenient time. Therefore, inconvenience caused by the reporting can be mitigated. Also, although cash holder Pm obtains all cash-IDs in the registration phase in Sec.4, it can obtain convenient number of cash-IDs anytime, e.g. at a time when it reports paying records.

As other drawbacks, each cash holder is required to examine individual illegitimate records even if it is honest, and different from real cash, cash holders must use their e-cash before they expire. About these drawbacks, numbers of illegitimate records can be decreased by high penalty fines. Also, although the proposed scheme defines expiration time of e-cash C(Pm, t, h) as that of C(Pj, s, v) from which C(Pm, t, h) was generated, it is possible to make C(Pm, t, h) valid during a fixed duration after C(Pm, t, h) was generated.

References

[1]  T. Okamoto, “An efficient divisible electronic cash scheme,” Crypto’95, 438-451. 1995.
In article      View Article
 
[2]  J. Camenisch, S. Hohenberger and A. Lysyanskaya, “Compact e-cash,” Eurocrypt’05, 302-321. 2005.
In article      View Article
 
[3]  S. Canard and A. Gouget, Divisible e-cash systems can be truly anonymous,” Eurocrypt’07, 482-497. 2007.
In article      View Article
 
[4]  S. Canard, A. Gouget and J. Traore, Improvement of efficiency in (unconditional) anonymous transferable e-cash,” Financial Cryptography 2008, 202-214. 2008.
In article      View Article
 
[5]  G. Fuchsbauer, D. Pointcheval and D. Vergnaud, “Transferable constant-size fair e-cash,” Proceedings of the 8th International Conference on Cryptology and Network Security, 226-247. 2009.
In article      View Article
 
[6]  S. Canard and A. Gouget, Multiple denominations in e-cash with compact transaction data,” Financial Cryptography 2010, 82-97. 2010.
In article      View Article
 
[7]  M. Izabachene and B, Libert, “Divisible e-cash in the standard model,” Pairing'12, 314-332. 2012.
In article      
 
[8]  S. Tamura, “Anonymous Security Systems and Applications: Requirements and Solutions,” Information Science Reference, 2012.
In article      View Article
 
[9]  S. Tamura and S. Taniguchi, “Enhancement of anonymous tag based credentials,” Information Security and Computer Fraud, Vol. 2, No. 1, 10-20, 2014.
In article      
 
[10]  S. Tamura and S. Taniguchi, “Linear mix-net and a scheme for collecting data from anonymous data holders,” Information Security and Computer Fraud, Vol. 2, No. 3, 39-47, 2014.
In article      
 
[11]  S. Tamura, “Elements of Schemes for Preserving Privacies in e-society Systems,” Lambert Academic Publishing, 2015.
In article      
 
  • CiteULikeCiteULike
  • MendeleyMendeley
  • StumbleUponStumbleUpon
  • Add to DeliciousDelicious
  • FacebookFacebook
  • TwitterTwitter
  • LinkedInLinkedIn