Dear Label_Name,

Greetings! I hope you are well.

I am writing on behalf of an international publishing house, Science and Education Publishing, USA (http://www.sciepub.com).

Science and Education Publishing (SciEP) is a multidisciplinary open access publisher of Journals covering the fields of Science, Technology and Medicine. All SciEP publications are subject to high-quality peer review, editorial and production processes and are freely available online.

Welcome to the April, 2013 edition of SciEP newsletter, providing monthly summaries of articles on science & education related topics of interest to scientist and professionals. The mission of our journals is to provide an open access forum for publishing new findings on issues pertinent to scientific and academic field. We also invite you to submit original research papers, review articles, short reports, or case studies are considered for publication in our Multidisciplinary Journals.

American Journal of Public Health Research
DOI: 10.12691/ajphr-1-1-3

The Implementation of a Tele-Homecare System with Service Oriented Architecture and HL7 Message Transmission Standard
Ching-Sung Wang

American Journal of Medical and Biological Research
DOI: 10.12691/ajmbr-1-1-2

The Influence of Ethanol on Pyruvate Kinases Activity in Vivo, in Vitro, in Silico
Lelevich Sergey Vladimirovich, Khrustalev Vladislav Victorovich, Barkovsky Eugene Victorovich, Shedogubova Tatyana Aleksandrovna

American Journal of Medical Sciences and Medicine
DOI: 10.12691/ajmsm-1-1-1

Clinical and Histological Features in Wegener Granulomatosis
Li Cavoli Gioacchino, Passantino Rita, Bono Luisa, Tortorici Calogera, Ferrantelli Angelo, Giammarresi Carlo, Rotolo Ugo

American Journal of Infectious Diseases and Microbiology
DOI: 10.12691/ajidm-1-1-2

The Curse of Lymphatic Filariasis: Would the Continual Use of Diethylcarbamazine Eliminate this Scourge in Papua New Guinea?
Anne Lanham, Lillian Mwanri

We have released issues of some journals on February 2013.
American Journal of Public Health Research
American Journal of Medical Sciences and Medicine
American Journal of Medical and Biological Research
American Journal of Pharmacological Sciences
American Journal of Clinical Medicine Research
American Journal of Nursing Research
American Journal of Cancer Prevention
American Journal of Medicine Studies
American Journal of Infectious Diseases and Microbiology
American Journal of Cardiovascular Disease Research
American Journal of Biomedical Research
American Journal of Mechanical Engineering
American Journal of Microbiological Research
Journal of Preventive Medicine
American Journal of Food and Nutrition
American Journal of Hypertension Research
American Journal of Sports Science and Medicine
Journal of Cancer Research and Treatment
American Journal of Zoological Research
Journal of Biomedical Engineering and Technology
American Journal of Microbiological Research
Biomedical Science and Engineering

We are pleased to announce that submissions are now being accepted for peer review for all the journals across all our subject areas in SciEP.

Please submit your manuscript via our online submission system:
http://www.sciepub.com/author/signin

To unsubscribe from our mailing list, please click on the following link: unsubscribe

I am looking forward to hearing from you.

Kind regards,

David Rain
Email:join@sciepub.com
Science and Education Publishing (http://www.sciepub.com)

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

Shinsuke Tamura*, Hazim A. Haddad

School 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.

Keywords: privacy, anonymous tags, anonymous credentials, linear mix-nets

Received July 23, 2015; Revised August 19, 2015; Accepted August 23, 2015

Citation: Shinsuke Tamura, Hazim A. Haddad, Development of Self-Issuable (Divisible and Transferable) Offline Electronic Cash. Information Security and Computer Fraud, 3 (1). 15-24. January 2015. doi:10.12691/iscf-3-1-3

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]. 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 P₁, P₂, ---, PM. Authority A issues e-cash to cash holders P₁, P₂, ---, 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.

Figure 1. Entities in the proposed e-cash scheme

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, d₁ and d₂ are 2 secret signing keys of A and S(d₁║d₂, x) is a pair of RSA signatures {S(d₁, x) = xd1mod B, S(d₂, x) = xd2mod B}, signature pair T(A, TP, R) = S(d₁║d₂, 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 q₁, q1*, q₂, q2*, q₃, 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 d₁ and d₂, 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(d₁║d₂, 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(d₁₁║d₂₁, TPR+1KwGwRmod B₁), S(d₁₂║d₂₂, TPR+1KwGwRmod B₂)} by using different integers B₁ and B₂. Namely, relation URmod B₁ = UR*mod B₁ does not holed even when relation URmod B₂ = UR*mod B₂ 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)W², ---, T(A, TP, R)Wn while generating different secret integers W₁, W₂, ---, 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 L₁, L₂, ---, 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 L₁, L₂, ---, 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(*)R∙V}, and finally LZ, LZ-1, ---, L₁ repeatedly decrypt each pair {E(DP(*)), U(*)R∙V} to {DP(*) = DP(1)+DP(2)+ --- +DP(HP), U(*)R∙V∙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 L₁, L₂, ---, LZ. About encryptions and decryptions of U(h)R in {h, DP(h), U(h)R} and U(*)R∙V in {E(DP(*)), U(*)R∙V}, L₁, L₂, ---, LZ transform U(h)R and U(*)R∙V 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 L₁, L₂, ---, 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(*)R∙V∙Y}. To enable A to identify the triplets, provided that U(0) is a publicly known integer, L₁, L₂, ---, 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(², ¹) --- X(Z, ¹⁾, U(2) = U(1)X(¹, ²)∙X(2, ²) --- X(Z, ²⁾, ---, U(HP) = U(HP-1)X(1, HP)∙X(2, HP) --- X(Z, HP⁾. Then, L₁, L₂, ---, LZ calculate U(*)R∙V = U(h)R∙V∙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)R∙V, and A identifies triplets {1, E(DP(1)), U(1)R∙V}, ---, {HP, E(DP(HP)), U(HP)R∙V} based on U(*)R∙V calculated from U(1)R∙V, ---, U(HP)R∙V. On the other hand, P calculates U(*)R∙V∙Y from U(*)V∙Y by using its secret integer R to identify {DP(*), U(*)R∙V∙Y}.

About calculation of DP(*) = DP(1)+DP(2)+ --- +DP(HP), L₁, L₂, ---, 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 L₁, L₂, ---, 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 L₁, L₂, ---, 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), L₁, L₂, ---, LZ jointly calculates integer Uh as Uh = Uh₋₁X(h⁾ = Uh₋₁X(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 L₁, L₂, ---, 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.

Figure 2. First 4 phases of the proposed e-cash scheme

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 {d₁, d₂} and {d₁*, d₂*} 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 L₁, L₂, ---, 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, L₁, L₂, ---, 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).

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

3. Pm calculates source-ID part value U₀Rm(t) and payee’s signature {U₀Rm(t)+e(i)║d(i)}Rm from integer U₀, 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 U₀Rm(t) did not appear before, A constructs cash issuing record I(i) = <e(i), d(i), 0, U₀Rm(t), {U₀Rm(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 U₀Rm(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 {U₀Rm(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.

Figure 3. Configurations of cash records

Here, Pm calculates U₀Rm(t) and {U₀Rm(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 {U₀Rm(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, {U₀Rm(t)+e(i)║d(i)}Rm can be calculated only by Pm that knows integer Rm, correct calculation of {U₀Rm(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 U₀Rm(t)+e(i)║d(i), Pm can convince any entity that {U₀Rm(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 U₀Rk⁽q⁾ from U₀ 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⁾, U₀Rk⁽q⁾, S(Rm, G(Pm, t, h))> to give Pk as shown in Figure 3 (b). Where, G(Pm, t, h) = UhRm⁽t⁾+U₀Rk⁽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 U₀Rk(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⁾, U₀Rk⁽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, ⁰⁾ and T*(A, Tk(q), Rk(q))W*k⁽q, ⁰⁾ 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 U₀Rk⁽q⁾ from U₀ 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 U₀Rk⁽q⁾ successfully and U₀Rk⁽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 U₀Rk⁽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) = U₀Rm(t)∙X(1)∙X(2) --- X(H) = U₀Rm(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 U₀Rm(t) is converted to U₀Rm(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) = U₀Rm(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), U₀Rk⁽q)> from paying record P(Pm, t, h) = <e(Pm, t, h), d(Pm, t, h), h, UhRm(t⁾, U₀Rk⁽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⁾+U₀Rk⁽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)Rm∙Rk 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 = {L₁, L₂, ---, LZ} as follows.

1. For each paying record P(Pm, t, h) = <e(Pm, t, h), d(Pm, t, h), h, UhRm(t⁾, U₀Rk⁽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), U₀Rk⁽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 L₁, L₂, ---, 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 L₁, L₂, ---, 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 L₁, L₂, ---, 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) = U₀Rm(t⁾∙X*∙λ* (as shown in Sec. 4, X(h) = X(1, h)∙X(2, h) --- X(Z, h)). In the same way, L₁, L₂, ---, 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, U₀Rm(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 U₀Rm(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)), U₀Rm(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, ---, L₁ 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)), U₀Rm(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 L₁, L₂, ---, LZ and μ* = μ(1)∙μ(2) --- μ(Z), each Lz transforms (decrypts) U₀Rm(t⁾∙X*∙λ*∙μ(Z)∙μ(Z-1)---μ(z+1) calculated by Lz+1 to U₀Rm(t⁾∙X*∙λ*∙μ(Z)∙μ(Z-1)---μ(z+1)∙μ(z), and as a result U₀Rm(t⁾∙X*∙λ* is transformed to U₀Rm(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, U₀Rm(t), {U₀Rm(t)+e(i)║d(i)}Rm> which does not expire, A constructs new-cash record N(A, i, 0) = <e(i), U₀Rm(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 L₁, L₂, ---, LZ calculate U₀Rk⁽q⁾∙X*∙λ*∙μ* or U₀Rm(t)∙X*∙λ*∙μ* from U₀Rk⁽q) or U₀Rm(t) in each N(Pj, s, v) or N(A, i, 0) to transform it to N*(Pj, s, v) = <e(Pm, t, h), U₀Rk⁽q⁾∙X*∙λ*∙μ*> or N*(A, i, 0) = <e(i), U₀Rm(t)∙X*∙λ*∙μ*>.

7. For each total expenditure record Sum(Pm, t), A finds a transformed new-cash record that includes U₀Rm(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), U₀Rm(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 U₁, U₂, ---, UH are calculated as U₁ = U₀X(1), U₂ = U₀X(1)∙X(2),---, UH = U₀X(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 U₀Rm(t⁾ of N(Pj, s, v) are transformed to same value U₀Rm(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 U₀Rm(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 U₀Rm(t⁾, U₁Rm(t⁾, U₂Rm(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), U₀Rm(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), U₀Rm⁽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 {G₁, G₂} in P(Pm, t, 1) is the one forged by Pm or someone else no one calculates G₂λ*∙μ* from G₁λ*∙μ*. 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 G₂λ*, and determines Pk is liable when it calculates G₂λ*∙Rk that is equal to the payee’s signature G₂Rk∙λ* in E(D(Pm, t, 1)).

Namely, authority A examines payee’s signature G₂Rk 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 {G₁, G₂} 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 {G₁, G₂} or not, A can determine Pk is liable, i.e. Pk had accepted P(Pm, t, h) that includes inconsistent {G₁, G₂}. As an exception if it is conspiring with A, Pk does not need to calculate G₂Rk 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, ---, L₁ to trace (partial) encryption forms of illegitimate total expenditure record Sum(Pm, t) = <e*(Pm, t), U₀Rm(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)), U₀Rm(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, U₀Rm⁽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), U₀Rm(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⁾, U₀Rm⁽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, U₀Rm(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.
[2]   | J. Camenisch, S. Hohenberger and A. Lysyanskaya, “Compact e-cash,” Eurocrypt’05, 302-321. 2005.
[3]   | S. Canard and A. Gouget, “Divisible e-cash systems can be truly anonymous,” Eurocrypt’07, 482-497. 2007.
[4]   | S. Canard, A. Gouget and J. Traore, “Improvement of efficiency in (unconditional) anonymous transferable e-cash,” Financial Cryptography 2008, 202-214. 2008.
[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.
[6]   | S. Canard and A. Gouget, “Multiple denominations in e-cash with compact transaction data,” Financial Cryptography 2010, 82-97. 2010.
[7]   | M. Izabachene and B, Libert, “Divisible e-cash in the standard model,” Pairing'12, 314-332. 2012.
[8]   | S. Tamura, “Anonymous Security Systems and Applications: Requirements and Solutions,” Information Science Reference, 2012.
[9]   | S. Tamura and S. Taniguchi, “Enhancement of anonymous tag based credentials,” Information Security and Computer Fraud, Vol. 2, No. 1, 10-20, 2014.
[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.
[11]   | S. Tamura, “Elements of Schemes for Preserving Privacies in e-society Systems,” Lambert Academic Publishing, 2015.