Enhanced Anonymous Tag Based Credentials

Shinsuke Tamura, Shuji Taniguchi

  Open Access OPEN ACCESS  Peer Reviewed PEER-REVIEWED

Enhanced Anonymous Tag Based Credentials

Shinsuke Tamura1,, Shuji Taniguchi1

1Graduate 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.

At a glance: Figures

Cite this article:

  • Tamura, Shinsuke, and Shuji Taniguchi. "Enhanced Anonymous Tag Based Credentials." Information Security and Computer Fraud 2.1 (2014): 10-20.
  • Tamura, S. , & Taniguchi, S. (2014). Enhanced Anonymous Tag Based Credentials. Information Security and Computer Fraud, 2(1), 10-20.
  • Tamura, Shinsuke, and Shuji Taniguchi. "Enhanced Anonymous Tag Based Credentials." Information Security and Computer Fraud 2, no. 1 (2014): 10-20.

Import into BibTeX Import into EndNote Import into RefMan Import into RefWorks
comments powered by Disqus

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][4], 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 S1, S2, --- as below. In the remainder notation mod B is omitted when confusions can be avoided.

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

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 K1K2---Kh, and as an exception S1 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 K1, K2 and K3 that are secrets of 3 entities S1, S2 and S3. 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 K1, K2, ---, 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 K1, K2, ---, 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.

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, d1 and d2 are 2 secret signing keys of S and S(d1d2, x) is a pair of RSA signatures {S(d1, x) = xd1mod B, S(d2, x) = xd2mod B}, signature pair S(d1d2, 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 q1, q1*, q2, q2*, q3, 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(d1d2, TPR+1KwCwR), and TP and TP* that are assigned to different credential holders P and P* are defined so that knowing integers q4 and q4* that satisfy TP = TP*q4, TPq4* = 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║d2, TPR+1KwCwR) is valid when S(d1, TPR+1KwCwR) and S(d2, TPR+1KwCwR) are consistent signatures on same value Lu+1kvcvu for some integers {L, u, v}. Here, credentials must be defined as signature pairs; if they are constituted as simple signatures, anyone can calculate Q1 = S(d1*, Lv+1kucuv) (d1* is a publicly known verification key) while generating integers L, u and v arbitrarily, and claim that Lv+1kucuv is a consistent signature, i.e. it is a signature on Q1 = (L(v+1)kucuv)d1*mod B = (Ld1*)(v+1)(kd1*)u(cd1*)uvmod B (in other words, S(d1, Q1) = S(d1, S(d1*, Lv+1kucuv)) = Lv+1kucuv). Signature pairs disable entities to dishonestly construct credentials in this way. About signing keys d1 and d2, their confidentialities can be maintained despite 2 verification keys d1* and d2* 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-1, Kw*, Cw*y-1} (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-1)}y* so that relation T*(y-1)+1Kw*Cw*y-1 = {TPR+1KwCwR/(Kw*Cw*y-1)}y*y(Kw*Cw*y-1) = TPR+1KwCwR holds and pairs {Kw*, Cw*} and {T*y-1, Cw*y-1} 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 S1, S2, ---, SH to generate their secret integers r1, r2, ---, 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 = r1+r2+ --- +rH, but when ZR appeared already, S1, S2, ---, 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 S1, S2, ---, 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(d1d2, 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(d1d2, 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 {Γ1, Γ2, Γ3} and {Ψ1, Ψ2, Ψ3} to calculate triplets {kΓ1, cΓ2, (kc3}, {KwΓ1, CwΓ2, (KwCw3}, {TPΨ1, CwΨ2, (TPCw3} and {(TPR1, (CwR2, ((TPCw)R3} and shows {kΓ1, cΓ2, (kc3} and {TPΨ1, CwΨ2, (TPCw3} to P.

4. P calculates β1 = (kΓ1)w, β2 = (cΓ2)w, β3 = ((kc3)w, δ1 = (TPΨ1)R, δ2 = (CwΨ2)R and δ3 = ((TPCw3)R.

5. If relations β1 = KwΓ1, β2 = CwΓ2, β3 = (KwCw3, δ1 = (TPR1, δ2 = (CwR2 and δ3 = ((TPCw)R3 hold, S generates credential S(d1d2, TPR+1KwCwR) and gives it to P.

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 Γ3, it can define arbitrarily and calculate γ and β3 as γ = (kc)w/ and β3 = ((kc3)w respectively to consistently report and γ as values of Kw and Cw instead of kw and cw, i.e. relation (γ)Γ3 = ((kc)w3 = ((kc3)w = β3 holds. However P, which does not know q2 nor q2* that satisfy relations k = cq2 and kq2* = c, cannot know at least one of integers σ1 and σ2 that satisfy = kσ1 and γ = cσ2. As a consequence, P cannot calculate β1 = (kΓ11 and β2 = (cΓ22 so that both relations β1 = Γ1 and β2 = γΓ2 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(d1d2, 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 d1 and d2. 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 {Q1 = S(d1*, Q*), Q2 = S(d2*, Q*)}, namely anyone knows public verification key pair d1* and d2*, and relations Q* = S(d1, S(d1*, Q*)) and Q* = S(d2, S(d2*, Q*)) hold. Also, from S(d1d2, TPR+1KwCwR) and S(d1d2, 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(d1d2, TPR+1KwCwR)S(d1d2, TP*R*+1Kw*Cw*R*) = S(d1d2, 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 {d1, d2} cannot make Q1 and Q2 equal. About the latter case, consistent credentials must be decrypted to forms that are decomposed into the product of {Lv+1, ku, cuv} for some integers L, u and v according to proposition 2. But anyone except S cannot know q1, q1*, q2, q2*, q3, q3*, g1, g1*, g3, g3*, q4 nor q4* even if P and P* conspire (here, relations TP = kq1, TPq1* = k, k = cq2, kq2* = c, c = TPq3, cq3* = TP, TP* = kg1, TP*g1* = k, c = TP*g3, cg3* = TP*, TP = TP*q4 and TPq4* = 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+1cuv = 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+1, ku, cuv}, either.Q.E.D.

After having obtained anonymous credential S(d1d2, 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(d1d2, TPR+1KwCwR)W = S(d1d2, (TPR+1KwCwR)W) to show it to verifier V together with TPW, KwW, CwW and CwRW.

2. V examines whether S(d1d2, 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 {Θ1, Θ2, Θ3} and {Λ1, Λ2, Λ3}, calculates triplets {kΘ1, cΘ2, (kc)Θ3}, {KwWΘ1, CwWΘ2, (KwWCwW)Θ3}, {(TPW)Λ1, (CwW)Λ2, (TPWCwW)Λ3} and {(TPRW)Λ1, (CwRW)Λ2, (TPRWCwRW)Λ3} and shows {kΘ1, cΘ2, (kc)Θ3} and {TPWΛ1, CwWΛ2, (TPWCwW)Λ3} to P.

4. P calculates ζ1 = (kΘ1)wW, ζ2 = (cΘ2)wW, ζ3 = ((kc)Θ3)wW, D = (TPWΛ1)R, ρ1 = (CwWΛ2)R and ρ2 = ((TPWCwW)Λ3)R.

5. If relations ζ1 = KwWΘ1, ζ2 = CwWΘ2, ζ3 = (KwWCwW)Θ3, D = (TPRW)Λ1, ρ1 = (CwRW)Λ2 and ρ2 = (TPRWCwRW)Λ3 hold, V determines that P is an eligible entity that knows R.

Proposition 4 (Soundness)

Under the strong RSA assumption, only entities that know integers w, W and R can prove the ownership of S(d1d2, 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 ζ1, ζ2, ζ3, D, ρ1 and ρ2 that coincide with (kwW)Θ1, (cwW)Θ2, ((kc)wW)Θ3, (TPRW)Λ1, (CwRW)Λ2 and (TPRWCwRW)Λ3 from triplets {kΘ1, cΘ2, (kc)Θ3} and {(TPW)Λ1, (CwW)Λ2, (TPWCwW)Λ3} without knowing Θ1, Θ2, Θ3, Λ1, Λ2 or Λ3. On the other hand under the strong RSA assumption, any entity except ones that know w, W and R and verifier V that knows Θ1, Θ2, Θ3, Λ1, Λ2 and Λ3 cannot calculate at least one of ζ1, ζ2, ζ3, D, ρ1 and ρ2 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(d1d2, TPR+1KwCwR)W1. Provided that W1, W2, W3, --- are integers secrets of P, no one other than P can know S(d1d2, TPR+1KwCwR)W1, S(d1d2, TPR+1KwCwR)W2, S(d1d2, 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(d1d2, TPR+1KwCwR)W1, S(d1d2, TPR+1KwCwR)W2, S(d1d2, 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(d1d2, TPR+1KwCwR), S(d1d2, TPR+1KwCwR)W1, S(d1d2, TPR+1KwCwR)W2, S(d1d2, TPR+1KwCwR)W3, ---, provided that W1, W2, W3, --- are secrets of P. Q.E.D.

Proposition 6

Under the strong RSA assumption, entity P that shows credential S(d1d2, 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 ζ1 = K*W1, ζ2 = C*W2, ζ3 = (K*W*C*W*)Θ3, D = (T*R*W*)Λ1, ρ1 = (C*R*W*)Λ2 and ρ2 = (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+1)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 q1, q1*, q2, q2*, q3 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(d1d2, 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(d1d2, 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(d1d2, TPR+1KwCwR), namely it cannot disable other entity P* to use S(d1d2, TPR+1KwCwR) as below.

Threat-1 P* that steals S(d1d2, 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 Θ1, Θ2, Θ3, Λ1, Λ2 and Λ3, it is easy for P* to calculateζ1, ζ2, ζ3, D, ρ1 and ρ2 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(d1d2, TPR+1KwCwR)W at its past visit to V.

Threat-3 P* can use S(d1d2, TPR+1KwCwR) if P informs it of secret R, i.e. S(d1d2, 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(d1d2, TPR+1KwCwR)W and S(d1d2, 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(d1d2, TPR+1KwCwR)W.

3.3. Used Seals of Anonymous Credentials

A used seal of anonymous credential S(d1d2, 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(d1d2, 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Λ1 and P calculates D = (TPWΛ1)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(d1d2, 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)Λ1Ω in addition to TPWΛ1 and TPRWΛ1, and shows it with U and TPWΛ1 to P, where U is the base of the used seal and Λ1 is the secret integer V generates at step 3 in the credential verification procedure.

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

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

Proposition 7

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

Proof

Proposition 6 ensures that P calculates D as (TPWΛ1)R based on its secret R, because P cannot prove the ownership of S(d1d2, TPR+1KwCwR) if D ≠ (TPWΛ1)R. About U*, if P calculates U* as UQ instead of UR (Q ≠ R), because relation D = (TPRW)Λ1 is ensured, P must calculate B as (UQ)Λ1ΩDΩ. But to calculate (UQ)Λ1ΩDΩ, P must decompose (UTPW)Λ1Ω into UΛ1Ω and (TPW)Λ1Ω, which is computationally infeasible for an entity that does not know Λ1 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(d1d2, 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 U1(i), U2(i), ---, UH(i) defined by independent authorities S1, S2, ---, 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(d1d2, TPR+1KwCwR)W at its past visit to verifier V, can easily use credential S(d1d2, TPR+1KwCwR) while changing its form to S(d1d2, TPR+1KwCwR)WW* = S(d1d2, (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(d1d2, TPR+1KwCwR)WW* instead of S(d1d2, TPR+1KwCwR)W so that V* will not be accused of having accepted same credential forms repeatedly even when the dishonest use of S(d1d2, 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(d1d2, 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(d1d2, 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(d1d2, 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(d1d2, TPR+1KwCwR) from threat-3, the enhanced anonymous tag based credential scheme limits the number of times that entities can use same credential S(d1d2, 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(d1d2, 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(d1d2, 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(d1d2, 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(d1d2, 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(d1d2, 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(d1d2, 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(d1d2, 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 U0R in addition to U(V, m)R, where S asks all credential holders to calculate their initial used seals based on U0 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(d1d2, TP*R*+1Kw*Cw*R*)W*, calculates Ur(P*) = U(n)r(P*), UR = U(n)Rr(P*), L1 = TP*W*r(P*) and L2 = TP*R*W*r(P*).

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

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

5. S determines P* is liable when one of relations D* = L2τ 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* = L2τ and B* = UR*τξD*ξ correspond to D = (TPRW)Λ1 and B = U*Λ1Ω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π, L1 = TP*W*π, and L2 = 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(d1d2, TP*R*+1Kw*Cw*R*) and S(d1d2, 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(d1d2, TPR+1KwCwR), S constructs record {U(n), U(n)R} in the invalid credential list from initial used seal {U0, U0R} that P had left when S issued S(d1d2, TPR+1KwCwR). Then at a time when entity P* shows its credential S(d1d2, 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(d1d2, TP*R*+1Kw*Cw*R*) in form S(d1d2, TP*R*+1Kw*Cw*R*)W* calculates Ur(P*) = U(n)r(P*), UR = U(n)Rr(P*), L1 = TP*W*r(P*) and L2 = 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π, L1 = TP*W*π and L2 = TP*R*W hold for same unknown π or not, and generates its secret integer τ and ξ to calculate L1τ and (Ur(P*)L1)τξ.

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

4. V* accepts P*’s request when relations D* = L2τ 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 ζ1 = (kΘ1)wW, ζ2 = (cΘ2)wW, ζ3 = ((kc)Θ3)wW, D = (TPWΛ1)R, ρ1 = (CwWΛ2)R, ρ2 = (TPWCwW)Λ3R, U* = U(n)R and B = {U(n)TPW}Λ1Ώ}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(d1d2, TPR+1KwCwR)W, to honestly calculate used seal UR, verifier V in the original scheme generates multiple secret integers X1, X2, ---, 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 X1, X2, ---, 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(d1d2, 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(d1d2, TPR+1KwCwR)W disable P to dishonestly calculate used seals as shown in Proposition 7. Also, signature pair S(d1d2, 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(d1d2, TPR+1KwCwRTAwa+1)W based on credential S(d1d2, 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 v1, v1*, v2, v2*, v3, 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.

The identity part in S(d1d2, TPR+1KwCwRTAwa+1) plays the same roles as credential S(d1d2, 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(d1d2, 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(d1d2, 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(d1d2, 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(d1d2, 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(d1d2, 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(d1d2, 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(d1d2, 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(d1d2, TPR+1KwCwRTAwa+1) instead of S(d1d2, 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(e1e2, TPReKwCwReTAwQ1+1) that includes integer Q1 as below, where the reference credential enables P to convince others that relation max/2 < Q1 < max holds while concealing Q1 itself, and e1 and e2 in it are singing keys of S that are different from d1 and d2, 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(e1e2, 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’ < Q1, and calculates TAwa, TAwa, TAwQ1 and TAwQ1-a to show them together with TAwQ1, a and Q1 - a’ to S.

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

4. S calculates TAwa+1 = TAwaTAwaTAw = TAwa+a+1 to include it in credential S(d1d2, TPR+1KwCwRTAwa+1).

In the above, S issues credential S(d1d2, TPR+1KwCwRTAwa+1) while identifying P, therefore P can show reference credential S(e1e2, TPRe+1KwCwReTAwQ1+1) without changing its form. Also P in step 3 can convince others that TAwQ1 is certainly included in reference credential S(e1e2, 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 Q1 that satisfies relation max/2 < Q1 < max although Q1 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’ < Q1 < max holds, apparently (Q1 - a’) becomes less than max/2 because max/2 < Q1 < max is ensured, but when a’ > max (this means a’ > Q1), (Q1 - a’)mod B is calculated as (Q1 - a’)mod B = B + (Q1 - a’) = Q1 + (B - a’), i.e. (Q1 - a’)mod B becomes greater than max/2 because Q1 > max/2 and B - a’ > 0. On the other hand, S cannot know the value of a’, because P discloses a’ in the forms (Q1 - 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(d1d2, TPR+1KwCwRTAwa+1) is greater than b that is designated by V, under the condition that all integers a, b, Q and a2, b2, Q2 are less than B/2, and although Q is P’s secret integer, P can convince V relations Q < B/2 and Q2 < B/2 by reference credential S(e1e2, 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(d1d2, TPR+1KwCwRTAwa+1) and reference credential S(e1e2, TPRe+1KwCwReTAwQ+1) calculates S(d1d2, TPR+1KwCwRTAwa+1)W and S(e1e2, 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(d1d2, TPR+1KwCwRTAwa+1)W to (TPR+1KwCwRTAwa+1)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(e1e2, TPRe+1KwCwReTAwQ+1)W* to (TPRe+1KwCwReTAwQ+1)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(d1d2, TPR+1KwCwRTAwa+1)W* to calculate Ua/Ub = Ua-b. P also calculates used seal U(a-b)Q from pair {TAwW*, TAwQW*} in S(e1e2, 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, a2 < B/2, b2 < B/2 and Q2 < B/2 are ensured, where, S can confirm that a < B/2 and a2 < 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(e1e2, 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(d1d2, TPR+1KwCwRTAwa+1TEwe+1)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 Q2 < B/2 without disclosing Q by obtaining reference credential S(e1e2, 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 e1 and e2 that are different from d1 and d2 to discriminate reference credentials from usual ones. Now P obtains reference credential S(e1e2, 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 = G1, TAu2 = G2, ---, TAuN = GN while generating a set of secret integers {u1, ---, uN} and shows G1, G2, ---, GN to S.

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

3. P discloses each uj except uq.

4. For each disclosed uj, S examines relations uj < B/2, uj2 < 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(e1e2, 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 uq2 < B/2 with probability (N-1)/N. P can generate reference credential S(e1e2, 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.
In article      CrossRef
 
[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.
In article      
 
[3]  Goldwasser, S., Micali, S. and Rackoff, C., “The knowledge complexity of interactive proof system,” SIAM Journal on Computing, 18 (1), 291-304. 1989.
In article      CrossRef
 
[4]  Damgard, I. B., “Payment systems and credential mechanism with provable security against abuse by individuals,” in CRYPTO'88, 328-335. 1990.
In article      
 
[5]  Camenisch, J. and Lysyanskaya, A., “An efficient system for non-transferable anonymous credential with optimal anonymity revocation,” in EUROCRYPT01, 93-118. 2001.
In article      
 
[6]  Camenisch, J. and Lysyanskaya, A., “Efficient non-transferable anonymous multi-show credential system with optional anonymity revocation,” in EUROCRYPT 2001, 93-118. 2001.
In article      
 
[7]  Camenisch, J. and Lysyanskaya, A., “Dynamic accumulators and application to efficient revocation of anonymous credentials,” in CRYPTO 2002, 61-76. 2002.
In article      
 
[8]  Camenisch, J. and Lysyanskaya, A., “Signature schemes and anonymous credentials from bilinear maps,” in CRYPTO 2004, 56-72. 2004.
In article      
 
[9]  Belenkiy, M., Chase, M., Kohlweiss, M. and Lysyanskaya, A., “P-signatures and noninteractive anonymous credentials,” in Theory of Cryptography Conference, 356-374. 2008.
In article      
 
[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.
In article      
 
[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.
In article      
 
[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.
In article      
 
[13]  Tamura, S., Anonymous security systems and applications: requirements and solutions, Information Science Reference, 2012.
In article      CrossRef
 
[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.
In article      
 
[15]  Diffie, W. and Hellman, M. E., “New directions in cryptography,” IEEE Trans. on Information Theory, IT-22 (6), 644-654. 1976.
In article      CrossRef
 
[16]  Chaum, D., Fiat, A. and Naor, M., “Untraceable electronic cash,” in CRYPTO88, 319-327. 1988.
In article      
 
[17]  Tamura, S. and Taniguchi, S., “A scheme for collecting anonymous data,” in IEEE-ICIT, 1210-1215. 2013.
In article      
 
  • CiteULikeCiteULike
  • Digg ThisDigg
  • MendeleyMendeley
  • RedditReddit
  • Google+Google+
  • StumbleUponStumbleUpon
  • Add to DeliciousDelicious
  • FacebookFacebook
  • TwitterTwitter
  • LinkedInLinkedIn