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)

Label_Title

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)

Enhanced Anonymous Tag Based Credentials

Shinsuke Tamura*, Shuji Taniguchi

Graduate School of Engineering, University of Fukui, Fukui, Japan

Abstract: A scheme for anonymous tag based anonymous credentials is enhanced. Different from existing zero knowledge proof based anonymous credential schemes that require numbers of challenges and responses between verifiers and credential holders, the anonymous tag based scheme requires only small number of challenges and responses between verifiers and credential holders. This is because the scheme in this paper can be easily made sound even in environments where verifiers also may behave dishonestly. However, the original scheme has probabilistic features, i.e. verifiers must generate dummy fake challenges; therefore overheads for managing anonymous systems cannot be reduced to the minimum. The enhanced anonymous tag based scheme excludes these probabilistic features from interactions between verifiers and credential holders. The scheme also corrects several design errors included in the original scheme.

Keywords: information security, privacy, anonymous services

Received January 20, 2014; Revised March 09, 2014; Accepted March 17, 2014

Citation: Shinsuke Tamura, Shuji Taniguchi, Enhanced Anonymous Tag Based Credentials. Information Security and Computer Fraud, 2 (1). 10-20. January 2014. doi:10.12691/iscf-2-1-3

1. Introduction

Credentials are ones that maintain attribute values and enable their holders to convince others that they are eligible for receiving services corresponding to the attribute values. If a credential, which includes the age of a holder as its attribute value, is issued to a person by the government agency, the person can buy whisky from a liquor shop provided that the age in the credential is over 19 for example. Here, an anonymous credential includes a secret of its holder, and only an entity that knows the secret can show the ownership of the credential. In addition, the holder can prove that it knows the secret in the credential without disclosing the secret itself; also the validity of the credential can be verified even if its forms are changed from the one that the authority had issued. Therefore, if the authority gives an anonymous credential to an entity after confirming its eligibility, the entity can convince verifiers which provide services that it is eligible without disclosing its identity by proving that it knows the secret in the credential, i.e. anonymous credential holders can receive services from verifiers while preserving their privacies.

To implement the above anonymous credentials various schemes had been proposed already, and although schemes based on blind signature [1] have limitations, schemes based on zero knowledge proof (ZKP) [2,3] successfully satisfy all primary requirements of anonymous credentials [4-12], e.g. they enable verifiers also to identify dishonest entities while preserving privacies of honest credential holders. However, existing ZKP based anonymous credentials are not practical enough because numbers of challenges and responses between verifiers and credential holders are required to verify validities of credentials.

In detail, in existing ZKP based anonymous credential schemes, provided that the secret in credential T is R, firstly credential holder P imbeds f(R) instead of R in credential T to conceal R from others. Then at a time when verifier V verifies T, P calculates g(r) while generating its secret integer r to show it with T that includes f(R), and V generates its secret integer q as a challenge. After that, P calculates response h(R, r, q) based on R, r and challenge q, and finally V, which knows f(R) in T and had received g(r) from P, examines whether relation F(f(R), g(r), q) = G(h(R, r, q)) holds or not. Here, functions f(R), g(r), h(R, r, q), F(f(R), g(r), q) and G(h(R, r, q)) are defined so that V cannot know R or r from f(R), g(r) or h(R, r, q). On the other hand, P cannot calculate h(R, r, q) that makes F(f(R), g(r), q) and G(h(R, r, q)) equal without knowing R. Therefore P can convince V that it knows R if F(f(R), g(r), q) coincides with G(h(R, r, q)) without disclosing R itself.

But, to disable others to link responses that P calculated at its different verification requests of same credential T, integer r in h(R, r, q) is defined by credential holder P. Therefore, if P successfully estimates integer q, it can find pair {R*, r*} that satisfies relation F(f(R), g(r*), q) = G(h(R*, r*, q)) even if it does not know R, also P can easily estimate q if it is conspiring with V. Then, to disable conspiring entities and verifiers to legitimately carry out credential verification procedures without knowing secrets in credentials, V must generate numbers of challenges, i.e. P must calculate a lot of responses based on its secret information each time when it requests services.

To make anonymous credentials practical enough while reducing the number of challenges and responses between verifiers and credential holders, this paper proposes an enhanced anonymous tag based credential scheme that disables entities to legitimately carry out credential verification procedures without knowing secrets in credentials even if they are conspiring with verifiers. Here, although the original anonymous tag based credential scheme had reduced numbers of challenges and responses [13], several parts of the scheme include probabilistic features, i.e. a credential holder must respond to several dummy fake challenges made by a verifier to generate evidences that the holder had certainly used the credential. Therefore, overheads for handling anonymous information cannot be reduced to the minimum. The enhanced scheme excludes these probabilistic features from interactions between verifiers and credential holders, and it also corrects several design errors included in the original scheme. As a consequence, the enhanced scheme becomes an efficient and secure component for developing anonymous service systems. For example, more efficient and secure anonymous payment, procurement, voting systems, etc. can be developed based on the proposed scheme.

2. Requirements for Anonymous Credentials

In the remainder, S, V and P represent a credential issuer, a verifier, and a credential holder respectively, namely S issues credentials to credential holders, V verifies validities of credentials shown by credential holders, and P shows its credential to receive services from V. Then, by showing anonymous credential T issued by issuer S, credential holder P can convince any entity (verifier) that it is eligible while preserving its privacy, i.e. anonymous credential T satisfies the following requirements [10].

R1. Unforgeability No one other than issuer S can generate valid credentials, in other words, credential holder P can obtain credential T only from S.

R2. Soundness and non-transferability Credential T is sound, namely entities that do not know secrets imbedded in T cannot prove their ownership of T. Here, it must be noted that this soundness must be satisfied even when the entities are conspiring with verifiers. Also this soundness does not automatically mean that the entity that can prove the ownership is only credential holder P, i.e. entities other than P also can prove the ownership if P informs them of the secrets in T. Non-transferability is the intensified notion of the soundness. Namely, P cannot inform others of secrets in its non-transferable credential T, but it seems impossible to disable P to leak its secrets to others. Therefore this requirement is restated as T can discourage P from informing others of its secrets, and the proposed scheme satisfies this requirement by limiting the number of times that entities can use same credential T.

R3. Anonymity No one except P can identify P from forms of credential T that P shows.

R4. Unlinkability Even if P uses its credential T repeatedly, no one except P can link repeatedly used T.

R5. Revocability S can invalidate credential T, if its holder P behaves or behaved dishonestly while showing T or if S reissued a new credential to P as a replacement of T (because P had forgotten its secrets necessary for using T for example). The proposed scheme satisfies this requirement while preserving privacies of other credential holders by 2 mechanisms. The 1st mechanism identifies credential holders that had received services while using invalid credentials later, and the 2nd one denies service requests accompanied by invalid credentials.

In addition to the above, to enable any entity to verify the validity of credentials and to maintain attribute values as secrets of credential holders, anonymous credentials must satisfy the following 2 requirements also.

R6. Verifier V can verify the validity of credential T without knowing any secret of S.

R7. No one except P can know exact values of attributes in P’s credential T from its forms shown by P.

Enhanced anonymous tag based credential scheme proposed in this paper successfully and efficiently satisfies all of these requirements as discussed in the following sections.

3. Anonymous Tag Based Credentials

3.1. Anonymous Tags

An anonymous tag consists of a pair of a tag and an associate tag parts as shown in Figure 1 [14], i.e. tag holder P defines integer TP and put TP mod B and TPRmod B in the tag part and the associate tag part respectively. Here, integer R is a secret of P, and B is an appropriate integer common to all tags and large enough. Under these settings, tag {TP mod B, TPRmod B} is transformed by multiple entities S₁, S₂, --- as below. In the remainder notation mod B is omitted when confusions can be avoided.

Figure 1. Anonymous tag

1. P generates its secret integer W and transforms tag {TP, TPR} to {TPW, TPRW} to forward it to other entity S₁.

2. Sh that receives tag {TPWK*(h-1), TPRWK*(h-1)} from Sh-1 generates its secret integer Kh and transforms it to {TPWK*(h-1)⁽Kh⁾, TPRWK*(h-1)⁽Kh⁾} = {TPWK*(h), TPRWK*(h)} to forward the result to other entity Sh+1 (here, K*(h) represents product K₁K₂---Kh, and as an exception S₁ receives {TPW, TPRW} form P).

Namely, anonymous tag {TP, TPR} changes its form as {TPW, TPRW}, {TPW(K1), TPRW(K1)}, {TPW(K1)(K2), TPRW(K1)(K2)} and {TPW(K1)(K2)(K3), TPRW(K1)(K2)(K3)} in this order when it is transformed by integers K₁, K₂ and K₃ that are secrets of 3 entities S₁, S₂ and S₃. Then, Proposition 1 ensures that anonymous tag {TP, TPR} satisfies the following 3 conditions.

C1. Anyone except tag owner P cannot identify P from tag forms {TPW, TPRW} or {TPWK*(h), TPRWK*(h)}.

C2. Anyone except P cannot know that {TPW, TPRW}, {TPWK*(1), TPRWK*(1)}, {TPWK*(2), TPRWK*(2)}, --- are the ones transformed from the same tag, unless all relevant entities conspire with each other.

C3. P can identify that {TPWK*(h), TPRWK*(h)} is generated from its tag {TP, TPR}.

Proposition 1

Under the strong RSA and the decisional Diffie-Hellman (DDH) assumptions, only entities that know R or W can identify the correspondence between {TP, TPR} and {TPW, TPRW} provided that integer B is sufficiently large. Under the same assumptions, only entities that know R or all K₁, K₂, ---, Kh can identify the correspondence between {TPW, TPRW} and {TPWK*(h), TPRWK*(h)}.

Proof

An entity that knows W can identify the correspondence between {TP, TPR} and {TPW, TPRW} by simply calculating {TPW, TPRW} from {TP, TPR} by using W, also if an entity knows R, it is easy to know that {TPW, TPRW} and {TPWK*(h), TPRWK*(h)} are generated from {TP, TPR}, i.e. associate tag part values TPRW and TPRWK*(h) in {TPW, TPRW} and {TPWK*(h), TPRWK*(h)} are calculated as TPW and TPWK*(h) to the power of R.

On the other hand, under the strong RSA and DDH assumptions, it is computationally infeasible to calculate R or W from TPRmod B or TPWmod B even if Tp is known. Therefore, entities that do not know R or W cannot know that {TPW, TPRW} is generated from {TP, TPR}. In the same way, an entity that does not know one of K₁, K₂, ---, Kh cannot know that {TPWK*(h), TPRWK*(h)} is generated from {TPW, TPRW} without knowing R. Q.E.D.

3.2. Anonymous Credentials Based on Anonymous Tags

Despite tag {TPW, TPRW} is anonymous, entity P in the above can convince any entity V that P is the holder of {TPW, TPRW} without disclosing its secret integer R along the scheme of Diffie and Hellman [15] as below.

1. V generates its secret integer X and calculates (TPW)X and (TPRW)X and shows (TPW)X to P.

2. P calculates α = (TPWX)R by using its secret integer R.

3. V convinces itself that P is the holder of {TPW, TPRW} if α = (TPRW)X.

Table 1. List of Symbols

Namely, when (TPW)X is given P that knows R can easily calculate α that coincides with (TPRW)X, i.e. (TPWX)R = (TPRW)X. On the other hand as in the previous section, for an entity that does not know R it is computationally infeasible to know R from TPW, TPRW and TPWX, as a consequence an entity that does not know R or X cannot calculate α that coincides with (TPRW)X from (TPW)X or TPRW. Therefore, if attribute values are not considered, anonymous credentials can be constructed from anonymous tags when mechanisms that disable entities to forge or modify tags are established as discussed in the remainder of this subsection. Table 1 shows symbols used in this section for constructing enhanced anonymous tag based credentials (some of the symbols will be used in later sections).

Let TP, k and c be integers defined by issuer S, and R and w be secret integers defined by credential holder P. Then, provided that B is a publicly known integer that is constructed as a product of sufficiently large S’s secret 2 prime numbers, d₁ and d₂ are 2 secret signing keys of S and S(d₁║d₂, x) is a pair of RSA signatures {S(d₁, x) = xd1mod B, S(d₂, x) = xd2mod B}, signature pair S(d₁║d₂, TPR+1KwCwRmod B) is an anonymous tag based anonymous credential generated by S and given to P. Where, TP, k and c are publicly known and they are defined so that to know integers q₁, q1*, q₂, q2*, q₃, q3* that satisfy relations TP = kq1, TPq1* = k, k = cq2, kq2* = c, c = TPq3, cq3* = TP is computationally infeasible for entities other than S. Also, different from k and c that are common to all credentials, TP and R are unique to credential S(d₁║d₂, TPR+1KwCwR), and TP and TP* that are assigned to different credential holders P and P* are defined so that knowing integers q₄ and q4* that satisfy TP = TP*q⁴, TPq⁴* = TP* is computationally infeasible for entities other than S. Regarding Kw and Cw, P calculates them as Kw = kwmod B and Cw = cwmod B based on publicly known k, c and same secret integer w.

Then, credential S(d1║d₂, TPR+1KwCwR) is valid when S(d₁, TPR+1KwCwR) and S(d₂, TPR+1KwCwR) are consistent signatures on same value Lu⁺¹kvcvu for some integers {L, u, v}. Here, credentials must be defined as signature pairs; if they are constituted as simple signatures, anyone can calculate Q₁ = S(d1*, Lv⁺¹kucuv) (d1* is a publicly known verification key) while generating integers L, u and v arbitrarily, and claim that Lv⁺¹kucuv is a consistent signature, i.e. it is a signature on Q₁ = (L⁽v⁺¹⁾kucuv)d1*mod B = (Ld1*)⁽v⁺¹⁾(kd1*)u(cd1*)uvmod B (in other words, S(d₁, Q₁) = S(d₁, S(d1*, Lv⁺¹kucuv)) = Lv⁺¹kucuv). Signature pairs disable entities to dishonestly construct credentials in this way. About signing keys d₁ and d₂, their confidentialities can be maintained despite 2 verification keys d1* and d₂* are disclosed because the signer is only S, i.e. other entities do not know any signing key.

Also, because integer B is a product of S’s 2 secret large prime numbers, anyone other than S cannot find integer pair {y, y*} that satisfies relation Tyy*mod B = Tmod B for a given integer T. Therefore, P cannot decompose TPR+1KwCwR into {T*, T*y⁻¹, Kw*, Cw*y⁻¹} (T* ≠ TP) while choosing integer X arbitrarily, calculating Kw* and Cw* as Kw* = kX and Cw* = cX and defining T* = {TPR+1KwCwR/(Kw*Cw*y⁻¹)}y* so that relation T*⁽y⁻¹⁾⁺¹Kw*Cw*y⁻¹ = {TPR+1KwCwR/(Kw*Cw*y⁻¹)}y*y(Kw*Cw*y⁻¹) = TPR+1KwCwR holds and pairs {Kw*, Cw*} and {T*y⁻¹, Cw*y⁻¹} are calculated as k and c to the power of same X and T* and Cw* to the power of same (y-1) respectively.

Uniqueness of P’s secret integer R can be maintained as below. Namely to generate integer R, firstly P asks multiple mutually independent authorities S₁, S₂, ---, SH to generate their secret integers r₁, r₂, ---, rH and calculate Zr1mod B, Zr2mod B, ---, ZrHmod B to inform issuer S of them, where Z is a publicly known integer that is common to all credentials. After that, S calculates Zr1Zr2---ZrH = Zr1+r2+ --- +rH = ZR, and if ZR did not appear before, each Sh informs P of its secret integer rh so that P can calculate R = r₁+r₂+ --- +rH, but when ZR appeared already, S₁, S₂, ---, SH generate other secret integers. Then, because Z is common to all credentials, different integers are assigned to different credentials. On the other hand, P can make R confidential unless all S₁, S₂, ---, SH conspire, because any entity other than Sh cannot calculate rh from Zrh.

By using the above ZR, S can also confirm that P had honestly included R in credential S(d₁║d₂, TPR+1KwCrwR) at a time when it issues the credential. Namely, if S asks P to calculate ZR again P can calculate it correctly only when the credential includes R as will be discussed in Sec. 3.3 where credential holders are forced to honestly calculate used seals of their anonymous credentials. Here, R must be constructed by multiple independent entities as above. If P itself generates secret integer R and discloses ZR to make R unique, issuer S can know R when other entity P* shows same value ZR by chance after P had disclosed it, provided that S and P* are conspiring and P* informs S of R.

S issues anonymous credential S(d₁║d₂, TPR+1KwCwR) to credential holder P through the following procedure, and Figure 2 depicts the procedure.

Credential issuing procedure

1. After verifying eligibility of P based on P’s identity, S generates integer TP to inform P of it together with integers k and c that are common to all credentials.

2. P generates its secret integers w and R, and calculates Kw = kw, Cw = cw and pair TPR and CwR to send them to S, where {TP, TPR} constitutes an anonymous tag.

3. S generates its secret integers {Γ₁, Γ₂, Γ₃} and {Ψ₁, Ψ₂, Ψ₃} to calculate triplets {kΓ¹, cΓ², (kc)Γ³}, {KwΓ¹, CwΓ², (KwCw)Γ³}, {TPΨ¹, CwΨ², (TPCw)Ψ³} and {(TPR)Ψ¹, (CwR)Ψ², ((TPCw)R)Ψ³} and shows {kΓ¹, cΓ², (kc)Γ³} and {TPΨ¹, CwΨ², (TPCw)Ψ³} to P.

4. P calculates β₁ = (kΓ¹)w, β₂ = (cΓ²)w, β₃ = ((kc)Γ³)w, δ₁ = (TPΨ¹)R, δ₂ = (CwΨ²)R and δ₃ = ((TPCw)Ψ³)R.

5. If relations β₁ = KwΓ¹, β₂ = CwΓ², β₃ = (KwCw)Γ³, δ₁ = (TPR)Ψ¹, δ₂ = (CwR)Ψ² and δ₃ = ((TPCw)R)Ψ³ hold, S generates credential S(d₁║d₂, TPR+1KwCwR) and gives it to P.

Figure 2. Issuing anonymous credentials

Here, it must be noted that although P discloses TPR, kw, cw and CwR, S cannot know R or w under the strong RSA assumption. Nevertheless, S can force P to calculated Kw and Cw as k and c to the power of same w through the scheme of Diffie and Hellman [15], i.e. Proposition 2 holds. In the same way, S can confirm that TPR and CwR are integers that coincide with TP and Cw to the power of same unknown integer R. Lastly as stated in Proposition 3, the above credential issuing procedure ensures that entities can obtain consistent credentials only from issuer S when they are eligible provided that S is honest. Of course S can issue credentials to even ineligible entities at its will, but these credentials bring losses only to S itself.

Proposition 2

In the credential issuing procedure, P must calculate pairs {Kw, Cw} and {TPR, CwR} as k and c and TP and Cw to the power of same integers w and R respectively, although w and R are secrets of P.

Proof

Although P does not know Γ₃, it can define arbitrarily and calculate γ and β₃ as γ = (kc)w/ and β₃ = ((kc)Γ³)w respectively to consistently report and γ as values of Kw and Cw instead of kw and cw, i.e. relation (γ)Γ³ = ((kc)w)Γ³ = ((kc)Γ³)w = β₃ holds. However P, which does not know q₂ nor q2* that satisfy relations k = cq2 and kq2* = c, cannot know at least one of integers σ₁ and σ₂ that satisfy = kσ¹ and γ = cσ². As a consequence, P cannot calculate β₁ = (kΓ¹)σ¹ and β₂ = (cΓ²)σ² so that both relations β₁ = Γ¹ and β₂ = γΓ² hold. In the same way, P must calculate TPR and CwR as TP and Cw to the power of same integer R. Q.E.D.

Proposition 3 (Unforgeability)

Under the strong RSA assumption, entity P can obtain consistent credential S(d₁║d₂, TPR+1KwCwR) only from issuer S when it is eligible.

Proof

Firstly, S examines eligibility of P before entering the procedure, and signs on TPR+1KwCwR by using its secret keys d₁ and d₂. Then through the legitimate way, P can obtain its credential only from S when it is eligible. On the other hand through illegitimate ways, P can declare any integer Q* as the signature on pair {Q₁ = S(d1*, Q*), Q₂ = S(d2*, Q*)}, namely anyone knows public verification key pair d1* and d2*, and relations Q* = S(d₁, S(d1*, Q*)) and Q* = S(d₂, S(d2*, Q*)) hold. Also, from S(d₁║d₂, TPR+1KwCwR) and S(d₁║d₂, TP*R*+1Kw*Cw*R*) issued to P and P*, anyone can generate signature pair on TPR+1TP*R*+1KwKw*CwRCw*R* as product S(d₁║d₂, TPR+1KwCwR)S(d₁║d₂, TP*R*+1Kw*Cw*R*) = S(d₁║d₂, TPR+1TP*R*+1KwKw*CwRCw*R*) (it must be noted that S(dj, x)S(dj, y) = S(dj, xy), i.e. RSA signing functions are multiplicative).

However, in the former case P that does not know signing key pair {d₁, d₂} cannot make Q₁ and Q₂ equal. About the latter case, consistent credentials must be decrypted to forms that are decomposed into the product of {Lv⁺¹, ku, cuv} for some integers L, u and v according to proposition 2. But anyone except S cannot know q₁, q1*, q₂, q2*, q₃, q3*, g₁, g1*, g₃, g3*, q₄ nor q₄* even if P and P* conspire (here, relations TP = kq1, TPq1* = k, k = cq2, kq2* = c, c = TPq3, cq3* = TP, TP* = kg¹, TP*g1* = k, c = TP*g³, cg3* = TP*, TP = TP*q⁴ and TPq⁴* = TP* are assumed). Therefore, under the strong RSA assumption and a condition where to find integer pair {y, y*} that satisfies relation Lyy* = L for a given integer L is computationally infeasible, P or P* cannot calculate pair {L, v} that satisfies relation Lv⁺¹cuv = TPR+1TP*R*+1KwKw*CwRCw*R*/ku for given u to make TPR+1TP*R*+1KwKw*CwRCw*R* consistent, in other words to decompose TPR+1TP*R*+1KwKw*CwRCw*R* into {Lv⁺¹, ku, cuv}, either.Q.E.D.

After having obtained anonymous credential S(d₁║d₂, TPR+1KwCwR), the credential verification procedure shown in Figure 3 enables P to convince anyone that it is an eligible entity ensured by S without disclosing its identity nor linkages among its contiguous credential verification requests. Namely, Propositions 4-6 ensure that the procedure accepts P only when it knows integer R, and P can conceal R from others.

Credential verification procedure

1. P generates its secret integer W and calculates S(d₁║d₂, TPR+1KwCwR)W = S(d₁║d₂, (TPR+1KwCwR)W) to show it to verifier V together with TPW, KwW, CwW and CwRW.

2. V examines whether S(d₁║d₂, TPR+1KwCwR)W is the consistent signature pair on (TPR+1KwCwR)W or not by using public verification key pair d1* and d2*. After that, V decomposes it into TPW, TPRW, KwW and CwRW based on the information given by P.

3. To confirm that P had calculated pairs {KwW = kwW, CwW = cwW} and {TPRW, CwRW} from integer pairs {k, c} and {TPW, CwW} while using P’s same secret integers wW and R respectively, V generates its secret integers {Θ₁, Θ₂, Θ₃} and {Λ₁, Λ₂, Λ₃}, calculates triplets {kΘ¹, cΘ², (kc)Θ³}, {KwWΘ¹, CwWΘ², (KwWCwW)Θ³}, {(TPW)Λ¹, (CwW)Λ², (TPWCwW)Λ³} and {(TPRW)Λ¹, (CwRW)Λ², (TPRWCwRW)Λ³} and shows {kΘ¹, cΘ², (kc)Θ³} and {TPWΛ¹, CwWΛ², (TPWCwW)Λ³} to P.

4. P calculates ζ₁ = (kΘ¹)wW, ζ₂ = (cΘ²)wW, ζ₃ = ((kc)Θ³)wW, D = (TPWΛ¹)R, ρ₁ = (CwWΛ²)R and ρ₂ = ((TPWCwW)Λ³)R.

5. If relations ζ₁ = KwWΘ¹, ζ₂ = CwWΘ², ζ₃ = (KwWCwW)Θ³, D = (TPRW)Λ¹, ρ₁ = (CwRW)Λ² and ρ₂ = (TPRWCwRW)Λ³ hold, V determines that P is an eligible entity that knows R.

Figure 3. Verifying anonymous credentials

Proposition 4 (Soundness)

Under the strong RSA assumption, only entities that know integers w, W and R can prove the ownership of S(d₁║d₂, TPR+1KwCwR)W to verifier V provided that V is honest.

Proof

It is apparent that entities that know w, W and R can calculate ζ₁, ζ₂, ζ₃, D, ρ₁ and ρ₂ that coincide with (kwW)Θ¹, (cwW)Θ², ((kc)wW)Θ³, (TPRW)Λ¹, (CwRW)Λ² and (TPRWCwRW)Λ³ from triplets {kΘ¹, cΘ², (kc)Θ³} and {(TPW)Λ¹, (CwW)Λ², (TPWCwW)Λ³} without knowing Θ₁, Θ₂, Θ₃, Λ₁, Λ₂ or Λ₃. On the other hand under the strong RSA assumption, any entity except ones that know w, W and R and verifier V that knows Θ₁, Θ₂, Θ₃, Λ₁, Λ₂ and Λ₃ cannot calculate at least one of ζ₁, ζ₂, ζ₃, D, ρ₁ and ρ₂ consistently. Here, Proposition 6 ensures P decomposes (TPR+1KwCwR)W into exactly TPW, TPRW, KwW and CwRW.Q.E.D.

Proposition 5 (Anonymity and unlinkability)

Under the strong RSA and DDH assumptions, no one except P can identify P from its showing credential S(d₁║d₂, TPR+1KwCwR)W1. Provided that W₁, W₂, W₃, --- are integers secrets of P, no one other than P can know S(d₁║d₂, TPR+1KwCwR)W1, S(d₁║d₂, TPR+1KwCwR)W2, S(d₁║d₂, TPR+1KwCwR)W3, --- are different forms of a same credential either.

Proof

Under the strong RSA assumption, anyone except P cannot know TP, TPR or R from any of S(d₁║d₂, TPR+1KwCwR)W1, S(d₁║d₂, TPR+1KwCwR)W2, S(d₁║d₂, TPR+1KwCwR)W3 ---, i.e. no one other than P itself can identify P from them. Also under DDH assumption, it is computationally infeasible to know correspondences among S(d₁║d₂, TPR+1KwCwR), S(d₁║d₂, TPR+1KwCwR)W1, S(d₁║d₂, TPR+1KwCwR)W2, S(d₁║d₂, TPR+1KwCwR)W3, ---, provided that W₁, W₂, W₃, --- are secrets of P. Q.E.D.

Proposition 6

Under the strong RSA assumption, entity P that shows credential S(d₁║d₂, TPR+1KwCwR)W can prove its ownership only when it calculates D = (TPWΛ1)R as TPWΛ1 to the power of exactly R.

Proof

To use R* instead of R (R* ≠ R) while satisfying relations ζ₁ = K*W*Θ¹, ζ₂ = C*W*Θ², ζ₃ = (K*W*C*W*)Θ³, D = (T*R*W*)Λ1, ρ₁ = (C*R*W*)Λ2 and ρ₂ = (T*R*W*C*R*W*)Λ3, P must decompose (TPR+1KwCwR)W into {T*W*, T*R*W*, K*W*, C*R*W*}. In addition, pair {K*W*, C*W*} must be calculated as k and c to the power of same integer w*W*. This means T*W*(R*+1) = (TPR+1KwCwR)W/kw*W*cw*W*R*= TP(R⁺¹)WkwW-w*W*cwWR-w*W*R* = L. But because R ≠ R*, L becomes a function of at least TP and k or TP and c (i.e. L is a function of at least TP and k if wW ≠ w*W*, and it is a function of TP and c if wW = w*W*). Then, under the strong RSA assumption and in a condition where to find integer pair {y, y*} which satisfies relation Lyy* = L is computationally infeasible, P that does not know q₁, q1*, q₂, q2*, q₃ nor q3* (it is assumed that TP = kq1, TPq1* = k, k = cq2, kq2* = c, c = TPq3 and cq3* = TP) cannot find integers T* and W* that satisfy relation T*W*(R*+1) = L.Q.E.D.

Then, it is concluded that anonymous credential S(d₁║d₂, TPR+1KwCwR) satisfies the 1st requirement (unforgeability), a part of the 2nd requirement (soundness), and the 3rd and the 4th requirements (anonymity and unlinkability). Also verifier V does not need to know any secret of issuer S for verifying S(d₁║d₂, TPR+1KwCwR)W because verification keys d1* and d2* are publicly known and (TPR+1KwCwR)W is decomposed into TPW, TPRW, KwW and CwRW by credential holder P itself, i.e. the 6th requirement is also satisfied.

But it must be noted that Proposition 4 does not ensure the complete soundness of P’s credential S(d₁║d₂, TPR+1KwCwR), namely it cannot disable other entity P* to use S(d₁║d₂, TPR+1KwCwR) as below.

Threat-1 P* that steals S(d₁║d₂, TPR+1KwCwR) can legitimately carry out the verification procedure without knowing secret R when it is conspiring with verifier V, i.e. if V informs P* of integers Θ₁, Θ₂, Θ₃, Λ₁, Λ₂ and Λ₃, it is easy for P* to calculateζ₁, ζ₂, ζ₃, D, ρ₁ and ρ₂ consistently.

Threat-2 P* that is conspiring with other verifier V* can impersonate P by exploiting decomposition {TPW, KwW, CwW, CwRW} that P had shown with S(d₁║d₂, TPR+1KwCwR)W at its past visit to V.

Threat-3 P* can use S(d₁║d₂, TPR+1KwCwR) if P informs it of secret R, i.e. S(d₁║d₂, TPR+1KwCwR) is transferable.

Used seals constructed in the next subsection based on Proposition 6 enable developments of simple mechanisms that remove the above 3 threats and that make credentials also revocable. In addition, mechanisms in Sec. 7 enable credential holders to maintain attribute values as their secrets. Namely, the enhanced anonymous tag based scheme satisfies all requirements in Sec. 2.

About anonymity of credentials, when 2 entities P and P* use their credentials S(d₁║d₂, TPR+1KwCwR)W and S(d₁║d₂, TP*R*+1Kw*Cw*R*)W* while defining integer pairs {w, W} and {w*, W*} in the way relation wW = w*W* holds by chance, issuer S can detect this fact by duplicated appearances of KwW = Kw*W* (= kwW) and if S is conspiring with P*, it can know wW (= w*W*) by asking it to P*. But S cannot identify P from wW, i.e. S cannot extract W from wW to calculate TjW for each Tj it had generated so that it can compare TjW with TPW that P shows together with S(d₁║d₂, TPR+1KwCwR)W.

3.3. Used Seals of Anonymous Credentials

A used seal of anonymous credential S(d₁║d₂, TPR+1KwCwR) owned by credential holder P is defined as UR, where verifier V defines base integer U and P calculates used seal UR by using its secret R. Then, because R is unique and known only to P, verifier V or issuer S can use UR as an evidence that P had certainly used S(d₁║d₂, TPR+1KwCwR) to receive services from V. Here, V cannot calculate R from UR of course. In addition, although V does not know R, it can force P to honestly calculate UR by extending the interactions in the credential verification procedure where V shows TPWΛ¹ and P calculates D = (TPWΛ¹)R as below, i.e. by adding operations 3*, 4* and 5* to steps 3, 4 and 5 in the credential verification procedure.

Then as a direct result of additions of 3*, 4* and 5*, threat-1 about the soundness in the previous subsection can be excluded. Namely, even if entity P* and verifier V are conspiring they cannot calculate used seal UR that is consistent with S(d₁║d₂, TPR+1KwCwR), and V itself must compensate accompanying losses as will be discussed in Sec. 4.

Proposition 7 ensures this extension forces P to calculate used seal UR honestly.

Used seal generation procedure

3*. V generates its secret integer Ω, to calculate (UTPW)Λ¹Ω in addition to TPWΛ¹ and TPRWΛ¹, and shows it with U and TPWΛ¹ to P, where U is the base of the used seal and Λ₁ is the secret integer V generates at step 3 in the credential verification procedure.

4*. P calculates U* = UR and B = {(UTPW)Λ¹Ω}R in addition to D = (TPWΛ¹)R.

5*. V examines whether relations D = (TPRW)Λ¹ and B = U*Λ¹ΩDΩ hold or not.

Proposition 7

Under the strong RSA assumption, P that uses credential S(d₁║d₂, TPR+1KwCwR) in the used seal generation procedure must calculate U*, D and B honestly as U* = UR, D = (TPWΛ¹)R and B = {(UTPW)Λ¹Ω}R, respectively from U, TPWΛ¹ and (UTPW)Λ¹Ω shown by verifier V, provided that V is honest.

Proof

Proposition 6 ensures that P calculates D as (TPWΛ¹)R based on its secret R, because P cannot prove the ownership of S(d₁║d₂, TPR+1KwCwR) if D ≠ (TPWΛ¹)R. About U*, if P calculates U* as UQ instead of UR (Q ≠ R), because relation D = (TPRW)Λ¹ is ensured, P must calculate B as (UQ)Λ¹ΩDΩ. But to calculate (UQ)Λ¹ΩDΩ, P must decompose (UTPW)Λ¹Ω into UΛ¹Ω and (TPW)Λ¹Ω, which is computationally infeasible for an entity that does not know Λ₁ or Ω under the strong RSA assumption. Q.E.D.

Here, P can calculate used seal UQ instead of UR dishonestly when it conspires with verifier V, but as will be discussed in the next section UQ becomes inconsistent with any credential, as a result, V must compensate accompanying losses by itself.

As discussed in the following sections P calculates used seals of same credential S(d₁║d₂, TPR+1KwCwR) every time it shows the credential based on different base values U(1), U(2), U(3), ---. But if S or V defines U(i) as U(j)G, S or V that knows G can have clues to identify the linkage between U(i)R and U(j)R, i.e. relation U(i)R = U(j)RG holds. This threat can be removed when bases of used seals are defined through cooperation among multiple independent authorities. Namely, when base U(i) is defined as the sum or product of U₁(i), U₂(i), ---, UH(i) defined by independent authorities S₁, S₂, ---, SH, S or V cannot define U(i) at its will without conspiring with all authorities.

4. Non-Transferability and Revocability

Used seals discussed in the previous section endow anonymous tag based credentials with non-transferability and revocability.

4.1. Mechanisms for Satisfying Non-Transferability

As same as threat-1 at the end of Sec. 3.2, threat -2 and 3 also can be excluded by using used seals. About threat-2, entity P*, which is conspiring with verifier V* and steals CwW and decomposition {TPW, TPRW, KwW, CwRW} that P had shown with S(d₁║d₂, TPR+1KwCwR)W at its past visit to verifier V, can easily use credential S(d₁║d₂, TPR+1KwCwR) while changing its form to S(d₁║d₂, TPR+1KwCwR)WW* = S(d₁║d₂, (TPR+1KwCwR)WW*). Namely, P* that generates W* and knows {TPW, TPRW, KwW, CwW, CwRW} can extract CwWW* and consistently decompose (TPR+1KwCwR)WW* into {TPWW*, TPRWW*, KwWW*, CwRWW*}, and based on them, conspiring P* and V* can carry out the credential verification procedure legitimately. Here, P* shows S(d₁║d₂, TPR+1KwCwR)WW* instead of S(d₁║d₂, TPR+1KwCwR)W so that V* will not be accused of having accepted same credential forms repeatedly even when the dishonest use of S(d₁║d₂, TPR+1KwCwR) is detected.

However, if P was required to calculate used seal U(V, m)R as an evidence that it had used credential S(d₁║d₂, TPR+1KwCwR)W for receiving V’s m-th service, at a time when P* requests V*’s m*-th service, either P* or V* cannot calculate used seal U(V*, m*)R, because R is known only to P and P did not calculate U(V*, m*)R before. Here, issuer S defines U(V, m) as an integer unique to V’s m-th service in advance. Then, threat-2 is removed. In detail, at a time when P* uses P’s credential S(d₁║d₂, TPR+1KwCwR), it calculates an inconsistent value as the used seal or uses U(V, m)R that was calculated by P already, and in the former case V* cannot identify the liable entity based on the inconsistent used seal as discussed in the next subsection (this means V* cannot impute the liability to P). In the latter case, although U(V, m)R becomes consistent if V* = V, V that had accepted the same used seal repeatedly is regarded as dishonest. As a consequence, dishonest V* or V is forced to compensate corresponding losses by itself.

In environments where all verifiers are connected to issuer S through online communication channels, the above U(V, m) that is bound to verifier V can be replaced with integer U(n) that is common to n-th service requests of all credential holders. Namely, provided that U(n)R is a used seal that P had calculated at its past visit to V, although P* can show U(n)R to V* as a consistent used seal even if V* and V are not same because U(n) is not bound to V, V* can detect the multiple appearance of U(n)R by examining records in S’s database. In other words, if V* accepts P*’s showing U(n)R, it is regarded as an entity responsible for the illegitimate use of S(d₁║d₂, TPR+1KwCwR) that had accepted same used seal U(n)R repeatedly. This integer U(n) can be used also for limiting the number of times that an entity can show a same credential as below.

To protect credential S(d₁║d₂, TPR+1KwCwR) from threat-3, the enhanced anonymous tag based credential scheme limits the number of times that entities can use same credential S(d₁║d₂, TPR+1KwCwR) so that credential holder P is discouraged from informing others of its secret R. Namely, in the credential verification procedure, P is requested also to declare n, the number of service requests that it had made before by using same credential S(d₁║d₂, TPR+1KwCwR), and verifier V informs P of U(n) so that P can calculate used seal U(n)R, where U(n) is an integer mentioned in the above. Then, because U(n)R is unique to pair {P, n}, V can disable P to use S(d₁║d₂, TPR+1KwCwR) more than N-times, i.e. the multi-show restriction procedure shown below can be constructed.

Multi-show restriction procedure

1. P requests services from V while showing credential S(d₁║d₂, TPR+1KwCwR)Wn together with integer n.

2. V examines whether n ≤ N or not, and rejects P’s request when n > N. If n ≤ N, V shows U(n) to P as a base of a credential used seal.

3. P calculates used seal U(n)R to report it to V.

4. V examines whether pair {n, U(n)R} exists in issuer S’s database already or not, and rejects P’s request if it exists. If {n, U(n)R} does not exist V accepts P’s request and registers pair {n, U(n)R} in S’s database.

Here, entities other than P cannot extract a sequence of used seals U(1)R, U(2)R, U(3)R -- that P had calculated of course because they do not know R. But if some verifiers are not connected to issuer S through online channels, V cannot know used seals memorized by other verifiers immediately, as a consequence, V or S detects excessive uses of credentials only later after used seals of all credential holders have been gathered from distributed verifiers. Nevertheless, S can identify credential holders liable for excessive uses as discussed just below.

Now, when discussions about threat-1, 2 and 3 are combined, V must ask P to calculate used seal U(n)R in online environments and 2 used seals U(n)R and U(V, m)R in offline environments at a time when P uses S(d₁║d₂, TPR+1KwCwR) for its n-th time as a request for V’s m-th service.

4.2. Mechanisms for Satisfying Revocability

Anonymous tag based credentials can be endowed with revocability in 2 ways. In the 1st way, issuer S identifies entities that behave or behaved dishonestly (e.g. entities that do not pay fees for services) later after they had successfully authenticated, of course while preserving privacy of honest entities, and in the 2nd way, S rejects service requests from entities that behaved dishonestly in the past or that are using credentials replaced with new ones.

To identify dishonest entities, when credential holder P requests the m-th service of verifier V while showing credential S(d₁║d₂, TPR+1KwCwR)W for its n-th time, V memorizes {U(n), U(n)R} or {U(V, m), U(V, m)R} as a part of a service record. Here U(n) and U(V, m) are integers defined in the previous subsection, and U(n)R and U(V, m)R are used seals of credential S(d₁║d₂, TPR+1KwCwR)W calculated by P. Under these settings, issuer S can identify P if any dishonesty is detected later in the service record that includes {U(n), U(n)R} or {U(V, m), U(V, m)R} by the following procedures. The procedure below is for offline environments, i.e. for a case where a service record includes pair {U(V, m), U(V, m)R}.

Dishonest entity identification procedure (for offline environments)

1. S informs each entity P* of U(V, m) in pair {U(V, m), U(V, m)R} included in the dishonest service record.

2. P* calculates used seal U(V, m)R* from U(V, m) and its credential S(d₁║d₂, TP*R*+1Kw*Cw*R*).

3. S identifies P* as the entity that is liable for the dishonest service record when U(V, m)R* coincides with U(V, m)R (i.e. when R = R*).

In the above, P* is forced to calculate U(V, m)R* honestly as discussed in Sec. 3.3. On the other hand, S cannot identify P* or P*’s past service requests from U(V, m)R* if P* is honest, because P* did not calculate U(V, m)R* before, i.e. different values are assigned to different service requests as bases of used seals. Here, although P can calculate a used seal that is different from U(V, m)R while showing a credential of other entity, S can detect this dishonesty if it asks P to calculate initial used seal U₀R in addition to U(V, m)R, where S asks all credential holders to calculate their initial used seals based on U₀ when it issues credentials. Also, S can reduce inconveniences that P* must calculate used seals every time when dishonest records are detected by asking all credential holders to calculate used seals related to dishonest records at each end of its service period.

In a case where a dishonest service record includes pair {U(n), U(n)R}, credential holder P* is asked to calculate U(n)R*. But P* had calculated U(n)R* already if it made more than n requests before, therefore S can identify P* as the credential holder that corresponds to the service record accompanied by {U(n), U(n)R*} despite P* is honest. Random integer r(P*) that is secret of P* copes with this inconvenience.

Dishonest entity identification procedure (for online environments)

1. S informs each entity P* of U(n) in pair {U(n), U(n)R} included in the dishonest service record.

2. P* generate random secret integer r(P*), and provided that P* shows its credential in form S(d₁║d₂, TP*R*+1Kw*Cw*R*)W*, calculates Ur(P*) = U(n)r(P*), UR = U(n)Rr⁽P*⁾, L₁ = TP*W*r(P*) and L₂ = TP*R*W*r(P*).

3. S examines whether relations Ur(P*) = U(n)π, UR = U(n)Rπ, L₁ = TP*W*π and L₂ = TP*R*W*π hold for same unknown π or not, and generates its secret integers τ and ξ to calculate L₁τ and (Ur(P*)L₁)τξ.

4. P* calculates D* = (L₁τ)R* and B* = {(Ur(P*)L₁)τξ}R* together with UR* = Ur(P*)R*.

5. S determines P* is liable when one of relations D* = L₂τ and B* = UR*τξD*ξ does not hold or UR* = U(n)R*r(P*⁾ coincides with UR = U(n)Rr⁽P*⁾ (i.e. R* = R).

In the above, relations D* = L₂τ and B* = UR*τξD*ξ correspond to D = (TPRW)Λ¹ and B = U*Λ¹ΩDΩ in the used seal generation procedure, therefore P* is forced to calculate UR* = Ur(P*)R* = U(n)R*r(P*) honestly. Also, S can verify relations Ur(P*) = U(n)π, UR = U(n)Rπ, L₁ = TP*W*π, and L₂ = TP*R*W*π in the same way as pair {Kw, Cw} in Sec. 3.2 was examined, and this means P* calculates UR as U(n)Rr(P*). Then, S can conclude that P* is liable for the dishonest record when UR* coincides with UR, namely used seals U(n)R*r(P*⁾ and U(n)Rr⁽P*⁾ of credentials S(d₁║d₂, TP*R*+1Kw*Cw*R*) and S(d₁║d₂, TPR+1KwCwR) are same. On the other hand, P* can disable others to identify its service requests, because r(P*) is secret of P* and used seal U(n)R*r(P*⁾ does not coincide with U(n)R* even if P* had calculated U(n)R* at its past request.

In environments where online channels between issuer S and verifiers are available, S can also reject service requests from credential holder P that had behaved dishonestly in the past or that is using a credential replaced with a new one. Firstly, issuer S registers pair {U(n), U(n)R} in its invalid credential list when dishonesties are detected in the service record corresponding to {U(n), U(n)R}. In a case where P had obtained a new credential as the replacement of S(d₁║d₂, TPR+1KwCwR), S constructs record {U(n), U(n)R} in the invalid credential list from initial used seal {U₀, U₀R} that P had left when S issued S(d₁║d₂, TPR+1KwCwR). Then at a time when entity P* shows its credential S(d₁║d₂, TP*R*+1Kw*Cw*R*)W* to verifier V*, the following procedure enables V* to reject P*’s request if P* = P in the same way as the previous procedure identified dishonest entities.

Invalid credential rejection procedure

1. P* that requests V*’s service by showing credential S(d₁║d₂, TP*R*+1Kw*Cw*R*) in form S(d₁║d₂, TP*R*+1Kw*Cw*R*)W* calculates Ur(P*) = U(n)r(P*), UR = U(n)Rr⁽P*⁾, L₁ = TP*W*r(P*) and L₂ = TP*R*W*r(P*). Here, r(P*) is a secret integer generated by P*.

2. V* examines whether relations Ur(P*) = U(n)π, UR = U(n)Rπ, L₁ = TP*W*π and L₂ = TP*R*W*π hold for same unknown π or not, and generates its secret integer τ and ξ to calculate L₁τ and (Ur(P*)L₁)τξ.

3. P* calculates D* = (L₁τ)R* and B* = {(Ur(P*)L₁)τξ}R* together with UR* = Ur(P*)R*.

4. V* accepts P*’s request when relations D* = L₂τ and B* = UR*τξD*ξ hold and UR* = U(n)R*r(P*⁾ does not coincide with UR = U(n)Rr⁽P*⁾ (i.e. R* and R do not match).

Because P* must calculate used seals U(n)R*r(P*) for each {U(n), U(n)R} in the invalid credential list at its every service request, overheads accompanying the procedure cannot be ignored when the number of dishonest or secret forgetting entities is large. Therefore, the above procedure is practical only when the number of dishonest or secret forgetting credential holders is small. An example that satisfies this condition is the authentication of clients in cloud computing systems.

5. Features of Anonymous Tag Based Credentials

As discussed already, the proposed enhanced anonymous tag based anonymous credential scheme satisfies all requirements shown in Section 2 except the 7th one (the performance about this requirement will be discussed in Sec.7). A distinctive property of the scheme is it can easily satisfy the complete soundness of credentials even in environments where verifiers also may behave dishonestly. As a consequence when compared with existing ZKP based schemes, which require numbers of interactive or non-interactive challenges and responses between verifiers and credential holders, procedures in the proposed scheme require credential holder P to calculate only values ζ₁ = (kΘ¹)wW, ζ₂ = (cΘ²)wW, ζ₃ = ((kc)Θ³)wW, D = (TPWΛ¹)R, ρ₁ = (CwWΛ²)R, ρ₂ = (TPWCwW)Λ³R, U* = U(n)R and B = {U(n)TPW}Λ¹Ώ}R, i.e. only 8 challenges and responses are necessary if all verifiers are connected to issuer S through online communication channels (when online channels are not available 10 challenges and responses are necessary because verifiers must ask P to calculate 2 used seals U(n)R and U(V, m)R). Here, the number of interactions between verifiers and credential holders is limited to 1.5 rounds, i.e. verification requests from credential holders, challenges from verifiers and responses from credential holders. Therefore, anonymous tag based credentials enable developments of highly efficient and secure anonymous service systems.

When compared with the original scheme [13], probabilistic features in generating used seals are excluded in the enhanced anonymous tag based scheme. To force P, a holder of credential S(d₁║d₂, TPR+1KwCwR)W, to honestly calculate used seal UR, verifier V in the original scheme generates multiple secret integers X₁, X₂, ---, XM, and calculates (TPCw)W(X1), (TPCw)W(X2), ---, (TPCw)W(XM) to ask P to calculate (TPCw)W(X1)R, (TPCw)W(X2)R, ---, (TPCw)W(XM)R and {U(TPCw)WXY}R by showing {(TPCw)W(X1), (TPCw)W(X2), ---, (TPCw)W(XM), U(TPCw)WXY} while randomly changing their positions. Namely, if P honestly calculates {U(TPCw)WXY}R, V can know UR as {U(TPCw)WXY}R/(TPCw)WXYR. On the other hand if P tries to calculate it dishonestly, it may calculate (TPCw)W(Xq) inconsistently because it cannot identify U(TPCw)WXY in {(TPCw)W(X1), ---, (TPCw)W(XM), U(TPCw)WXY} and its requests is rejected as discussed in Sec. 3.2. But this means P can calculate the used seal dishonestly with probability 1/M. As a consequence, V must generate a large number of integers X₁, X₂, ---, XM to make the probability 1/M small enough, which reduces the efficiency. Different from the original scheme, in the proposed scheme, the above probabilistic feature is excluded completely from interactions between verifiers and credential holders.

About the configuration of credentials, S(d₁║d₂, TPR+1KwCwR)W in the proposed scheme is configured as S(d, TPR+Gg+G+1)W in the original scheme, where integers G and g are defined by issuer S and common to all credentials, and G is publicly known and g is a secret of S. But S(d, TPR+Gg+G+1)W cannot disable P to calculate used seal as UR* instead of UR while using integer R* (≠ R). In the enhanced scheme, KwW and CwRW included in credential S(d₁║d₂, TPR+1KwCwR)W disable P to dishonestly calculate used seals as shown in Proposition 7. Also, signature pair S(d₁║d₂, x) completely disables entities to forge credentials.

6. Adding Attribute Values to Credentials

Attribute values can be attached to credentials discussed in Sec. 3 by simply constructing them with identity and attribute parts pairs as shown in Figure 4. Namely, provided that a is an value of attribute A, and TA is a publicly known integer corresponding to attribute A, entity P can prove that it deserves attribute value a without disclosing its identity by calculating S(d₁║d₂, TPR+1KwCwRTAwa+1)W based on credential S(d₁║d₂, TPR+1KwCwRTAwa+1) given from S and its secret integer W, and by showing it together with TPW, KwW, CwW, CwRW, TAwW and TAwaW. Here, TPR+1KwCwR constitutes the identity part and TP, Kw =kw, Cw = cw and R are defined as in Sec. 3.2. On the other hand, TAwa+1 constitutes the attribute part, and TA is defined by S so that no one other than S can know integers v₁, v1*, v₂, v2*, v₃, v3* that satisfy relations TA = TPv1, TAv1* = TP, TA = kv2, TAv2* = k, TA = cv3, TAv3* = c, and P calculates TAw as TAw while using its secret integer w that it had used for calculating Kw = kw and Cw = cw.

Figure 4. Identity and attribute parts

The identity part in S(d₁║d₂, TPR+1KwCwRTAwa+1) plays the same roles as credential S(d₁║d₂, TPR+1KwCwR) in previous sections did, i.e. the identity part conceals the identity of credential holder P while ensuring P is eligible, therefore identity part TPR+1KwCwR must conceal R from anyone except P. On the other hand the purpose of attribute part TAwa+1 at this stage is not to conceal attribute value a, instead, the role of TAwa+1 is to disable P to use attribute value a illegitimately, i.e. it disables P to claim a* that is different from a as the attribute value. Therefore different from integer R, attribute value a in this section is made publicly known.

Credential verification procedure that enables entities to determine whether P deserves attribute value a or not without knowing P can be constructed as below.

Attribute value verification procedure 1

1. P shows credential S(d₁║d₂, TPR+1KwCwRTAwa+1)W with TPW, Kw W, CwW, CwRW, TAwW, TAwaW and attribute value a to verifier V (W is P’s secret integer as same as in the credential verification procedure in Sec. 3.2).

2. V verifies signature pair S(d₁║d₂, TPR+1KwCwRTAwa+1)W and decomposes (TPR+1KwCwRTAwa+1)W into TPW, TPRW, Kw W, CwRW, TAwW and TAwaW based on the information given by P.

3. To determine whether P is an eligible holder of S(d₁║d₂, TPR+1KwCwRTAwa+1)W or not, V examines the consistency of decomposition {TPW, TPRW, Kw W, CwRW} as in steps 3-5 of the credential verification procedure.

4. V confirms that P had calculated TAwW as TA to the power of unknown wW that was used for calculating KwW = kwW and CwW = cwW, and determines that P deserves a when relation TAwaW = (TAwW)a holds.

From discussions in previous sections, it is apparent that the above procedure ensures P is the eligible holder of S(d₁║d₂, TPR+1KwCwRTAwa+1)W, i.e. only P that knows R can use the credential. In addition, attribute part (TAwa+1)W disables P to declare attribute value a dishonestly as follow, i.e. when P decomposes TAw(a+1)W into TAww* and TAwa*w* while finding integers a* and W* that are different from a and W, although relation TAwa*w*TAww* = TAw(a+1)W may hold, V detects the dishonesty because TAww* and KwW are TA and k to the power of different integers.

Credential S(d₁║d₂, TPR+1KwCwR) can have also multiple attribute values. For example, to add an expiration time as new attribute E to the above credential, S defines new integer TE, P calculates TEw = TEw and TEwe+1 based on attribute value e to construct the credential as S(d₁║d₂, TPR+1KwCwRTAwa+1TEwe+1). But it must be noted that verifier V must examine all attribute values included in a credential even when it does not require all attribute values. If attribute value e in S(d₁║d₂, TPR+1KwCwRTAwa+1TEwe+1)W is not examined for example, P that possesses an illegitimate credential can declare the value of TEw(e+1)W arbitrarily to make other parts of the credential consistent.

7. Concealing Attribute Values

In the previous attribute value verification procedure, credential holder P must disclose attribute value a to convince verifier V that it deserves a. However, attribute values may include clues to identify P, or in face to face environments, P may not want to disclose attribute values even if it is anonymous. Therefore sometimes anonymous credentials are required to conceal also attribute values. To conceal attribute values, this section constructs a mechanism which enables verifier V to confirm that relation b < a (or b > a) holds for some value b it defines, of course without knowing a itself.

Before constructing the attribute value verification procedure in which credential holder P can conceal its attribute value a, it must be noted that P cannot show even pair {TAwW, TAwaW}, because usually relatively small number of values are assigned to an attribute (e.g. if an attribute is the age of a person, only about 100 values are effective), and V can know a from the pair by calculating TAwWa* from TAwW for every possible attribute value a* to compare the result with TAwaW. To disable V to know a in this way, P constructs attribute values as pairs of real values and large dummy secret random values as shown in Figure 5. In the figure real attribute value a and large dummy value a’ are located at the upper and the lower digits of attribute value a, i.e. a’ is defined so that relation a’ < max holds for some integer max. As a consequence, issuer S issues credential S(d₁║d₂, TPR+1KwCwRTAwa⁺¹) instead of S(d₁║d₂, TPR+1KwCwRTAwa+1) in the remainder.

Here, value a also must be concealed from S, because if S knows a, later it can identify a even from pair {TAwW, TAwaW} by calculating TAwWa* from TAwW for every a* it had issued. P can conceal a from others while convincing them that a in it is correct and a’ in it is less than max by using reference credential S(e₁║e₂, TPReKwCwReTAwQ1+1) that includes integer Q₁ as below, where the reference credential enables P to convince others that relation max/2 < Q₁ < max holds while concealing Q₁ itself, and e₁ and e₂ in it are singing keys of S that are different from d₁ and d₂, as will be discussed at the end of this section.

Figure 5. Real and dummy parts in an attribute value

Attribute value generation procedure

1. P shows reference credential S(e₁║e₂, TPRe+1KwCwReTAwQ1+1) with {TPRe, Kw, Cw, CwRe, TAw, TAwQ1} to S, and convinces S that decomposition {TP, Kw, Cw, CwRe, TAw, TAwQ1} of TPRe+1KwCwReTAwQ1+1 is consistent.

2. P generates random integer a’ that satisfies relations max/2 < a’ < max and a’ < Q₁, and calculates TAwa, TAwa’, TAwQ1 and TAwQ1-a’ to show them together with TAwQ1, a and Q₁ - a’ to S.

3. S confirms that Q₁ - a’ is less than max/2, TAwQ1 is certainly calculated from reference credential S(e₁║e₂, TPRe+1KwCwReTAwQ1+1), TAwQ1-a’ equals to TAwQ1/TAwa’, and TAwa and TAwQ1-a’ are TAw to the power of a and (Q₁ - a’), respectively.

4. S calculates TAwa⁺¹ = TAwaTAwa’TAw = TAwa+a’⁺¹ to include it in credential S(d₁║d₂, TPR+1KwCwRTAwa⁺¹).

In the above, S issues credential S(d₁║d₂, TPR+1KwCwRTAwa⁺¹) while identifying P, therefore P can show reference credential S(e₁║e₂, TPRe+1KwCwReTAwQ1+1) without changing its form. Also P in step 3 can convince others that TAwQ1 is certainly included in reference credential S(e₁║e₂, TPRe+1KwCwReTAwQ1+1) because TAw, Kw and Cw are calculated as TAw = TAw, Kw = kw, Cw = cw by same unknown integer w, and this ensures that TAwQ1 is calculated as TAw to the power of integer Q₁ that satisfies relation max/2 < Q₁ < max although Q₁ is P’s secret as will be discussed later. Then, S can confirm that a’ < max without knowing a’ as follows.

Namely, if relation max/2 < a’ < Q₁ < max holds, apparently (Q₁ - a’) becomes less than max/2 because max/2 < Q₁ < max is ensured, but when a’ > max (this means a’ > Q₁), (Q₁ - a’)mod B is calculated as (Q₁ - a’)mod B = B + (Q₁ - a’) = Q₁ + (B - a’), i.e. (Q₁ - a’)mod B becomes greater than max/2 because Q₁ > max/2 and B - a’ > 0. On the other hand, S cannot know the value of a’, because P discloses a’ in the forms (Q₁ - a’), TAwa’ and TAwQ1-a’. But it must be noted that P cannot assign a value that is less than max/2 to a’ although relation a’ < max holds.

While using attribute values constructed by the above procedure, the following procedure enables entities to convince others that their attribute values are greater (or less) than given values without disclosing the attribute values themselves. In the procedure, P convinces V that attribute value a in credential S(d₁║d₂, TPR+1KwCwRTAwa⁺¹) is greater than b that is designated by V, under the condition that all integers a, b, Q and a², b², Q² are less than B/2, and although Q is P’s secret integer, P can convince V relations Q < B/2 and Q² < B/2 by reference credential S(e₁║e₂, TPRe+1KwCwReTAwQ+1). Here, V defines b from b in the same way as P constructs a from a, but b is not a secret value different from a.

Attribute value verification procedure 2

1. P generates its secret integers W and W*, and from its credential S(d₁║d₂, TPR+1KwCwRTAwa⁺¹) and reference credential S(e₁║e₂, TPRe+1KwCwReTAwQ+1) calculates S(d₁║d₂, TPR+1KwCwRTAwa⁺¹)W and S(e₁║e₂, TPRe+1KwCwReTAwQ+1)W* to show them to V, with {TPW, KwW, CwW, CwRW, TAwW, TAwaW} and {TPW*, KwW*, CwW*, CwReW*, TAwW*, TAwQW*}.

2. V decrypts S(d₁║d₂, TPR+1KwCwRTAwa⁺¹)W to (TPR+1KwCwRTAwa⁺¹)W, decomposes the result to TPW, TPRW, KwW, CwRW, TAwW and TAwaW, and confirms that the decomposition is consistent. In the same way, it decrypts S(e₁║e₂, TPRe⁺¹KwCwReTAwQ+¹)W* to (TPRe⁺¹KwCwReTAwQ+¹)W*, decomposes the result to TPW*, TPReW*, KwW*, CwReW*, TAwW* and TAwQW*, and confirms the decomposition is consistent.

3. V generates b and calculate Ub, where U is the base of used seals.

4. P generates used seals Ua from pair {TAwW, TAwaW} in S(d₁║d₂, TPR+1KwCwRTAwa⁺¹)W* to calculate Ua/Ub = Ua⁻b. P also calculates used seal U⁽a⁻b)Q from pair {TAwW*, TAwQW*} in S(e₁║e₂, TPRe+1KwCwReTAwQ+1)W* and base value U⁽a⁻b⁾, and discloses Ua, U⁽a⁻b)Q and (a-b)Q.

5. V confirms that U⁽a⁻b)Q is certainly U to the power of (a-b)Q, and determines that a > b when (a-b)Q is less than B/2.

At step 4 in the above procedure, V can force P to honestly calculate used seals Ua and U⁽a⁻b)Q as shown in Proposition 7. In addition, relations a < B/2, b < B/2, Q < B/2, a² < B/2, b² < B/2 and Q² < B/2 are ensured, where, S can confirm that a < B/2 and a² < B/2 at a time when it had issued the credential because P discloses a and relation a’ < max is ensured, and b is generated by S itself. Conditions about Q are also ensured by reference credential S(e₁║e₂, TPRe+1KwCwReTAwQ+1) as shown later. Therefore, (a-b)Qmod B becomes less than B/2 if a is greater than b. On the other hand if a is less than b, (a-b)Q is calculated as (a-b)Qmod B = B + (a-b)Q, as a consequence, (a-b)Qmod B becomes greater than B/2. Then by relation (a-b)Q < B/2, V can confirm that a > b and as a consequence a > b.

Regarding the discussion at the end of Sec. 6 that verifier V must examine consistencies of all attribute values, based on Proposition 4, V can confirm consistencies of irrelevant attribute values without executing the above procedure. For example, in a case where V does not need to examine attribute value e in credential S(d₁║d₂, TPR+1KwCwRTAwa⁺¹TEwe⁺¹)W owned by P, V can confirm that P honestly extracts TEw⁽e+1)W from the credential by asking P to prove that it knows e included in TEw⁽e+1)W. Here according to Proposition 5, P can maintain attribute value e as its secret of course.

P can convince V that Q < B/2 and Q² < B/2 without disclosing Q by obtaining reference credential S(e₁║e₂, TPRe+1KwCwReTAwQ+1) in the course of member registration procedure, in which issuer S accepts P as an eligible entity. Here, S uses signing key e₁ and e₂ that are different from d₁ and d₂ to discriminate reference credentials from usual ones. Now P obtains reference credential S(e₁║e₂, TPRe+1KwCwReTAwQ+1) without disclosing Q while convincing S that Q satisfies the above conditions thorough cut and choose protocol [16].

Reference credential issuing procedure

1. P calculates TAu1 = G₁, TAu2 = G₂, ---, TAuN = GN while generating a set of secret integers {u₁, ---, uN} and shows G₁, G₂, ---, GN to S.

2. S chooses single integer Gq from {G₁, ---, GN}.

3. P discloses each uj except uq.

4. For each disclosed uj, S examines relations uj < B/2, uj² < B/2 and TAuj = Gj, and when the relations are satisfied, as the value of TAwQ+1 it includes TAuq+1 in reference credential S(e₁║e₂, TPRe+1KwCwReTAwQ+1).

In the above, apparently P can conceal uq ( = Q) from S. On the other hand, although P can define uq illegitimately, it must disclose uq if S does not choose it, and this means S can convince itself that uq satisfies the conditions uq < B/2 and uq² < B/2 with probability (N-1)/N. P can generate reference credential S(e₁║e₂, TPRe+1KwCwReTAwQ1+1) in the attribute value generation procedure in the same way. Here, although S must ask P to calculate a large number of integers {TAu1, ---, TAuN} to make the above probability large enough, this probabilistic feature appears only in member registration procedures, i.e. probabilistic features are excluded from credential verification processes. Then, the enhanced anonymous tag based credential scheme can maintain its efficiency because member registration procedures are carried out only once for each entity. Here, the above cut and choose protocol can be replaced by other ZKP protocols of course.

8. Conclusion

A scheme for anonymous credentials based on anonymous tags was enhanced to make it more secure and efficient. Namely, design errors in the original scheme were corrected, and probabilistic features were excluded from interactions between verifiers and credential holders. Although probabilistic features remain in member registration procedures when credential holders want to conceal their attribute values, the scheme still can maintain its efficiency because member registration procedures are required only once for individual entities. Therefore, developments of secure and efficient anonymous service systems e.g. e-cash systems [13], anonymous data collection systems [17], etc. become possible.

References

[1]   | Chaum, D., “Untraceable electronic mail, return address and digital pseudonyms,” Communications of the ACM, 24 (2), 84-88. 1981.
[2]   | Blum, M., Feldman, P. and Micali, S., “Non-interactive zero-knowledge and its applications,” in 20th Annual ACM Symposium on Theory of Computing, 103-112. 1988.
[3]   | Goldwasser, S., Micali, S. and Rackoff, C., “The knowledge complexity of interactive proof system,” SIAM Journal on Computing, 18 (1), 291-304. 1989.
[4]   | Damgard, I. B., “Payment systems and credential mechanism with provable security against abuse by individuals,” in CRYPTO'88, 328-335. 1990.
[5]   | Camenisch, J. and Lysyanskaya, A., “An efficient system for non-transferable anonymous credential with optimal anonymity revocation,” in EUROCRYPT’01, 93-118. 2001.
[6]   | Camenisch, J. and Lysyanskaya, A., “Efficient non-transferable anonymous multi-show credential system with optional anonymity revocation,” in EUROCRYPT 2001, 93-118. 2001.
[7]   | Camenisch, J. and Lysyanskaya, A., “Dynamic accumulators and application to efficient revocation of anonymous credentials,” in CRYPTO 2002, 61-76. 2002.
[8]   | Camenisch, J. and Lysyanskaya, A., “Signature schemes and anonymous credentials from bilinear maps,” in CRYPTO 2004, 56-72. 2004.
[9]   | Belenkiy, M., Chase, M., Kohlweiss, M. and Lysyanskaya, A., “P-signatures and noninteractive anonymous credentials,” in Theory of Cryptography Conference, 356-374. 2008.
[10]   | Belenkiy, M., Camenisch, J., Chase, M., Kohlweiss, M., Lysyanskaya, A. and Shacham, H., “Randomizable proofs and delegatable anonymous credentials,” in 29th Annual International Cryptology Conference on Advances in Cryptology, 108-125. 2009.
[11]   | Shahandashti, S. F. and Safavi-Naini, R., “Threshold attribute-based signatures and their application to anonymous credential systems,” in 2nd International Conference on Cryptology in Africa: Progress in Cryptology, 198-216. 2009.
[12]   | Sudarsono, A., Nakanishi, T. and Funabiki, N., “Efficient proofs of attributes in pairing-based anonymous credential system,” Springer Lecture Notes in Computer Science 6794/2011, 246-263. 2011.
[13]   | Tamura, S., Anonymous security systems and applications: requirements and solutions, Information Science Reference, 2012.
[14]   | Tamura, S., Haddad, H. A., Kouro, K., Tsurugi, H., Md. Rokibul Alam, K., Yanase, T. and Taniguchi, S., “An information system platform for anonymous product recycling,” Journal of Software, 3 (3), 46-56. 2008.
[15]   | Diffie, W. and Hellman, M. E., “New directions in cryptography,” IEEE Trans. on Information Theory, IT-22 (6), 644-654. 1976.
[16]   | Chaum, D., Fiat, A. and Naor, M., “Untraceable electronic cash,” in CRYPTO’88, 319-327. 1988.
[17]   | Tamura, S. and Taniguchi, S., “A scheme for collecting anonymous data,” in IEEE-ICIT, 1210-1215. 2013.