## Enhanced Anonymous Tag Based Credentials

**Shinsuke Tamura**^{1,}, **Shuji Taniguchi**^{1}

^{1}Graduate School of Engineering, University of Fukui, Fukui, Japan

2. Requirements for Anonymous Credentials

3. Anonymous Tag Based Credentials

4. Non-Transferability and Revocability

5. Features of Anonymous Tag Based Credentials

6. Adding Attribute Values to Credentials

### 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

**Keywords:** information security, privacy, anonymous services

*Information Security and Computer Fraud*, 2014 2 (1),
pp 10-20.

DOI: 10.12691/iscf-2-1-3

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

**Copyright:**© 2014 Science and Education Publishing. All Rights Reserved.

### 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 |

### 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.* **A**nonymity* 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 T_{P} and put T_{P mod B} and T_{P}^{R}_{mod 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 {T_{P mod B}, T_{P}^{R}_{mod B}} is transformed by multiple entities *S*_{1}, *S*_{2}, --- as below. In the remainder notation _{mod B} is omitted when confusions can be avoided.

**Fig**

**ure**

**1.**Anonymous tag

1.* **P *generates its secret integer W and transforms tag {T_{P}, T_{P}^{R}} to {T_{P}^{W}, T_{P}^{RW}} to forward it to other entity *S*_{1}.

2.* **S*_{h} that receives tag {T_{P}^{WK*(h-1)}, T_{P}^{RWK*(h-1)}} from *S*_{h-1} generates its secret integer K_{h} and transforms it to {T_{P}^{WK*(h-1)}^{(}^{Kh}^{)}, T_{P}^{RWK*(h-1)}^{(}^{Kh}^{)}} = {T_{P}^{WK*(h)}, T_{P}^{RWK*(h)}} to forward the result to other entity *S*_{h+1} (here, K_{*}(h) represents product K_{1}K_{2}---K_{h}, and as an exception *S*_{1} receives {T_{P}^{W}, T_{P}^{RW}} form *P*).

Namely, anonymous tag {T_{P}, T_{P}^{R}} changes its form as {T_{P}^{W}, T_{P}^{RW}}, {T_{P}^{W(K1)}, T_{P}^{RW(K1)}}, {T_{P}^{W(K1)(K2)}, T_{P}^{RW(K1)(K2)}} and {T_{P}^{W(K1)(K2)(K3)}, T_{P}^{RW(K1)(K2)(K3)}} in this order when it is transformed by integers K_{1}, K_{2} and K_{3} that are secrets of 3 entities *S*_{1}, *S*_{2} and *S*_{3}. Then, Proposition 1 ensures that anonymous tag {T_{P}, T_{P}^{R}} satisfies the following 3 conditions.

C1. Anyone except tag owner *P* cannot identify *P* from tag forms {T_{P}^{W}, T_{P}^{RW}} or {T_{P}^{WK*(h)}, T_{P}^{RWK*(h)}}.

C2. Anyone except *P* cannot know that {T_{P}^{W}, T_{P}^{RW}}, {T_{P}^{WK*(1)}, T_{P}^{RWK*(1)}}, {T_{P}^{WK*(2)}, T_{P}^{RWK*(2)}}, --- are the ones transformed from the same tag, unless all relevant entities conspire with each other.

C3.* P* can identify that {T_{P}^{WK*(h)}, T_{P}^{RWK*(h)}} is generated from its tag {T_{P}, T_{P}^{R}}.

**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 {T_{P}, T_{P}^{R}} and {T_{P}^{W}, T_{P}^{RW}} provided that integer B is sufficiently large. Under the same assumptions, only entities that know R or all K_{1}, K_{2}, ---, K_{h} can identify the correspondence between {T_{P}^{W}, T_{P}^{RW}} and {T_{P}^{WK*(h)}, T_{P}^{RWK*(h)}}.

*Proof *

An entity that knows W can identify the correspondence between {T_{P}, T_{P}^{R}} and {T_{P}^{W}, T_{P}^{RW}} by simply calculating {T_{P}^{W}, T_{P}^{RW}} from {T_{P}, T_{P}^{R}} by using W, also if an entity knows R, it is easy to know that {T_{P}^{W}, T_{P}^{RW}} and {T_{P}^{WK*(h)}, T_{P}^{RWK*(h)}} are generated from {T_{P}, T_{P}^{R}}, i.e. associate tag part values T_{P}^{RW} and T_{P}^{RWK*(h)} in {T_{P}^{W}, T_{P}^{RW}} and {T_{P}^{WK*(h)}, T_{P}^{RWK*(h)}} are calculated as T_{P}^{W} and T_{P}^{WK*(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 T_{P}^{R}_{mod B} or T_{P}^{W}_{mod B} even if T_{p} is known. Therefore, entities that do not know R or W cannot know that {T_{P}^{W}, T_{P}^{RW}} is generated from {T_{P}, T_{P}^{R}}. In the same way, an entity that does not know one of K_{1}, K_{2}, ---, K_{h} cannot know that {T_{P}^{WK*(h)}, T_{P}^{RWK*(h)}} is generated from {T_{P}^{W}, T_{P}^{RW}} without knowing R. Q.E.D.

**3.2. Anonymous Credentials Based on Anonymous Tags**

Despite tag {T_{P}^{W}, T_{P}^{RW}} is anonymous, entity *P* in the above can convince any entity *V* that *P* is the holder of {T_{P}^{W}, T_{P}^{RW}} 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 (T_{P}^{W})^{X} and (T_{P}^{RW})^{X} and shows (T_{P}^{W})^{X} to *P*.

2.* P* calculates α = (T_{P}^{WX})^{R} by using its secret integer R.

3. *V* convinces itself that *P* is the holder of {T_{P}^{W}, T_{P}^{RW}} if α = (T_{P}^{RW})^{X}.

Namely, when (T_{P}^{W})^{X} is given *P* that knows R can easily calculate α that coincides with (T_{P}^{RW})^{X}, i.e. (T_{P}^{WX})^{R} = (T_{P}^{RW})^{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 T_{P}^{W}, T_{P}^{RW} and T_{P}^{WX}, as a consequence an entity that does not know R or X cannot calculate α that coincides with (T_{P}^{RW})^{X} from (T_{P}^{W})^{X} or T_{P}^{RW}. 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 T_{P},* 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_{1} and d_{2} are 2 secret signing keys of *S* and S(d_{1}_{║}d_{2}, *x*) is a pair of RSA signatures {S(d_{1}, *x*) = *x*^{d1}_{mod B}, S(d_{2}, *x*) = *x*^{d2}_{mod B}}, signature pair S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}_{mod B}) is an anonymous tag based anonymous credential generated by *S* and given to *P*. Where, T_{P}, *k* and *c* are publicly known and they are defined so that to know integers q_{1}, q_{1*}, q_{2}, q_{2*}, q_{3}, q_{3*} that satisfy relations T_{P} = *k*^{q1}, T_{P}^{q1*} = *k*, *k* = *c*^{q2}, *k*^{q2*} = *c*, *c* = T_{P}^{q3},* c*^{q3*} = T_{P} is computationally infeasible for entities other than *S*. Also, different from *k* and *c* that are common to all credentials, T_{P} and R are unique to credential S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}), and T_{P} and T_{P*} that are assigned to different credential holders *P* and *P*_{*} are defined so that knowing integers q_{4} and q_{4*} that satisfy T_{P} = T_{P*}^{q}^{4}, T_{P}^{q}^{4}^{*} = T_{P*} is computationally infeasible for entities other than *S*. Regarding K_{w} and C_{w}, *P* calculates them as K_{w} = *k*^{w}_{mod B} and C_{w} = *c*^{w}_{mod B} based on publicly known *k*, *c* and same secret integer *w*.

Then, credential S(d_{1║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}) is valid when S(d_{1}, T_{P}^{R+1}K_{w}C_{w}^{R}) and S(d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}) are consistent signatures on same value L^{u}^{+1}*k*^{v}*c*^{vu} 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_{1} = S(d_{1*}, L^{v}^{+1}*k*^{u}*c*^{uv}) (d_{1*} is a publicly known verification key) while generating integers L, *u* and *v* arbitrarily, and claim that L^{v}^{+1}*k*^{u}*c*^{uv} is a consistent signature, i.e. it is a signature on Q_{1} = (L^{(}^{v}^{+1}^{)}*k*^{u}*c*^{uv})^{d1*}_{mod B} = (L^{d1*})^{(}^{v}^{+1)}(*k*^{d1*})^{u}(*c*^{d1*})^{uv}_{mod B} (in other words, S(d_{1}, Q_{1}) = S(d_{1}, S(d_{1*}, L^{v}^{+1}*k*^{u}*c*^{uv})) = L^{v}^{+1}*k*^{u}*c*^{uv}). Signature pairs disable entities to dishonestly construct credentials in this way. About signing keys d_{1} and d_{2}, their confidentialities can be maintained despite 2 verification keys d_{1*} and d_{2}_{*} 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 T^{yy}^{*}_{mod B} = T_{mod B} for a given integer T. Therefore, *P* cannot decompose T_{P}^{R+1}K_{w}C_{w}^{R} into {T_{*}, T_{*}^{y}^{-1}, K_{w}_{*}, C_{w}_{*}^{y}^{-1}} (T_{*} ≠ T_{P}) while choosing integer X arbitrarily, calculating K_{w}_{*} and C_{w}_{*} as K_{w}_{*} = *k*^{X} and C_{w}_{*} = *c*^{X} and defining T_{*} = {T_{P}^{R+1}K_{w}C_{w}^{R}/(K_{w}_{*}C_{w}_{*}^{y}^{-1})}^{y}^{*} so that relation T_{*}^{(}^{y}^{-1)+1}K_{w}_{*}C_{w}_{*}^{y}^{-1} = {T_{P}^{R+1}K_{w}C_{w}^{R}/(K_{w}_{*}C_{w}_{*}^{y}^{-1})}^{y}^{*}^{y}(K_{w}_{*}C_{w}_{*}^{y}^{-1}) = T_{P}^{R+1}K_{w}C_{w}^{R} holds and pairs {K_{w}_{*}, C_{w}_{*}} and {T_{*}^{y}^{-1}, C_{w}_{*}^{y}^{-1}} are calculated as *k* and *c* to the power of same X and T_{*} and C_{w}_{*} 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*_{1}, *S*_{2}, ---, *S*_{H} to generate their secret integers r_{1}, r_{2}, ---, r_{H} and calculate *Z*^{r1}_{mod B}, *Z*^{r2}_{mod B}, ---, *Z*^{rH}_{mod B} to inform issuer *S* of them, where Z is a publicly known integer that is common to all credentials. After that, *S* calculates *Z*^{r1}*Z*^{r2}---*Z*^{rH} = *Z*^{r1+r2+ --- }^{+rH} = *Z*^{R}, and if *Z*^{R} did not appear before, each *S*_{h} informs *P* of its secret integer r_{h} so that *P* can calculate R = r_{1}+r_{2}+ --- +r_{H}, but when *Z*^{R} appeared already, *S*_{1}, *S*_{2}, ---, *S*_{H} 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*_{1}, *S*_{2}, ---, *S*_{H} conspire, because any entity other than *S*_{h} cannot calculate r_{h} from *Z*^{rh}.

By using the above Z^{R}, *S* can also confirm that *P* had honestly included R in credential S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{rw}^{R}) at a time when it issues the credential. Namely, if *S* asks *P* to calculate *Z*^{R} 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 *Z*^{R} to make R unique, issuer *S* can know R when other entity *P*_{*} shows same value *Z*^{R} 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_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}) 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 T_{P} 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 K_{w} = *k*^{w}, C_{w} = *c*^{w} and pair T_{P}^{R} and C_{w}^{R} to send them to *S*, where {T_{P}, T_{P}^{R}} constitutes an anonymous tag.

3.* S* generates its secret integers {Γ_{1}, Γ_{2}, Γ_{3}} and {Ψ_{1}, Ψ_{2}, Ψ_{3}} to calculate triplets {*k*Γ^{1}, *c*Γ^{2}, (*kc*)Γ^{3}}, {K_{w}Γ^{1}, C_{w}Γ^{2}, (K_{w}C_{w})Γ^{3}}, {T_{P}Ψ^{1}, C_{w}Ψ^{2}, (T_{P}C_{w})Ψ^{3}} and {(T_{P}^{R})Ψ^{1}, (C_{w}^{R})Ψ^{2}, ((T_{P}C_{w})^{R})Ψ^{3}} and shows {*k*Γ^{1}, *c*Γ^{2}, (*kc*)Γ^{3}} and {T_{P}Ψ^{1}, C_{w}Ψ^{2}, (T_{P}C_{w})Ψ^{3}} to *P*.

4.* P* calculates β_{1} = (*k*Γ^{1})^{w}, β_{2} = (*c*Γ^{2})^{w}, β_{3} = ((*kc*)Γ^{3})^{w}, δ_{1} = (T_{P}Ψ^{1})^{R}, δ_{2} = (C_{w}Ψ^{2})^{R} and δ_{3} = ((T_{P}C_{w})Ψ^{3})^{R}.

5. If relations β_{1} = K_{w}Γ^{1}, β_{2} = C_{w}Γ^{2}, β_{3} = (K_{w}C_{w})Γ^{3}, δ_{1} = (T_{P}^{R})Ψ^{1}, δ_{2} = (C_{w}^{R})Ψ^{2} and δ_{3} = ((T_{P}C_{w})^{R})Ψ^{3} hold, *S* generates credential S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}) and gives it to *P*.

**Fig**

**ure**

**2.**Issuing anonymous credentials

Here, it must be noted that although *P* discloses T_{P}^{R}, *k*^{w}, *c*^{w} and C_{w}^{R}, *S* cannot know R or *w* under the strong RSA assumption. Nevertheless, *S* can force *P* to calculated K_{w} and C_{w} 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 T_{P}^{R} and C_{w}^{R} are integers that coincide with T_{P} and C_{w} 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 {K_{w}, C_{w}} and {T_{P}^{R}, C_{w}^{R}} as *k* and *c* and T_{P} and C_{w} 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} = ((*kc*)Γ^{3})^{w} respectively to consistently report and γ as values of K_{w} and C_{w} instead of *k*^{w} and *c*^{w}, i.e. relation (γ)Γ^{3} = ((*kc*)^{w})Γ^{3} = ((*kc*)Γ^{3})^{w} = β_{3} holds. However *P*, which does not know q_{2} nor q_{2*} that satisfy relations *k* = *c*^{q2} and *k*^{q2*} = *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*Γ^{1})σ^{1} and β_{2} = (*c*Γ^{2})σ^{2} so that both relations β_{1} = Γ^{1} and β_{2} = γΓ^{2} hold. In the same way, *P* must calculate T_{P}^{R} and C_{w}^{R} as T_{P} and C_{w} 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_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}) only from issuer *S* when it is eligible.

*Proof*

Firstly, *S* examines eligibility of *P* before entering the procedure, and signs on T_{P}^{R+1}K_{w}C_{w}^{R} by using its secret keys d_{1} and d_{2}. 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*_{1} = S(d_{1*}, *Q*_{*}), *Q*_{2} = S(d_{2*}, *Q*_{*})}, namely anyone knows public verification key pair d_{1*} and d_{2*}, and relations *Q*_{*} = S(d_{1}, S(d_{1*}, *Q*_{*})) and* Q*_{*} = S(d_{2}, S(d_{2*}, *Q*_{*})) hold. Also, from S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}) and S(d_{1}_{║}d_{2}, T_{P*}^{R*+1}K_{w}_{*}C_{w}_{*}^{R*}) issued to *P* and *P*_{*}, anyone can generate signature pair on T_{P}^{R+1}T_{P*}^{R*+1}K_{w}K_{w}_{*}C_{w}^{R}C_{w}_{*}^{R*} as product S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R})S(d_{1}_{║}d_{2}, T_{P*}^{R*+1}K_{w}_{*}C_{w}_{*}^{R*}) = S(d_{1}_{║}d_{2}, T_{P}^{R+1}T_{P*}^{R*+1}K_{w}K_{w}_{*}C_{w}^{R}C_{w}_{*}^{R*}) (it must be noted that S(d_{j}, *x*)S(d_{j}, *y*) = S(d_{j}, *xy*), i.e. RSA signing functions are multiplicative).

However, in the former case *P* that does not know signing key pair {d_{1}, d_{2}} cannot make *Q*_{1} and *Q*_{2} equal. About the latter case, consistent credentials must be decrypted to forms that are decomposed into the product of {L^{v}^{+1}, *k*^{u}, *c*^{uv}} for some integers L, *u* and *v* according to proposition 2. But anyone except *S* cannot know q_{1}, q_{1*}, q_{2}, q_{2*}, q_{3}, q_{3*,}_{ }g_{1}, g_{1*}, g_{3}, g_{3*,} q_{4} nor q_{4}_{*} even if *P* and *P*_{*} conspire (here, relations T_{P} = *k*^{q1}, T_{P}^{q1*} = *k*, *k* = *c*^{q2}, *k*^{q2*} = *c*, *c* = T_{P}^{q3},* c*^{q3*} = T_{P}_{,} T_{P}_{*} = *k*^{g}^{1}, T_{P}_{*}^{g}^{1*} = *k*, *c* = T_{P}_{*}^{g}^{3}, *c*^{g}^{3*} = T_{P}_{*}, T_{P} = T_{P*}^{q}^{4} and T_{P}^{q}^{4}^{*} = T_{P*} are assumed). Therefore, under the strong RSA assumption and a condition where to find integer pair {*y*, *y*^{*}} that satisfies relation L^{yy}^{*} = L for a given integer L is computationally infeasible,* **P* or *P*_{*} cannot calculate pair {L, *v*} that satisfies relation L^{v}^{+1}*c*^{uv} = T_{P}^{R+1}T_{P*}^{R*+1}K_{w}K_{w}_{*}C_{w}^{R}C_{w}_{*}^{R*}/*k*^{u} for given *u* to make T_{P}^{R+1}T_{P*}^{R*+1}K_{w}K_{w}_{*}C_{w}^{R}C_{w}_{*}^{R*} consistent, in other words to decompose T_{P}^{R+1}T_{P*}^{R*+1}K_{w}K_{w}_{*}C_{w}^{R}C_{w}_{*}^{R*} into {L^{v}^{+1}, *k*^{u}, *c*^{uv}}, either.Q.E.D.

After having obtained anonymous credential S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}), 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_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R})^{W} = S(d_{1}_{║}d_{2}, (T_{P}^{R+1}K_{w}C_{w}^{R})^{W}) to show it to verifier *V* together with T_{P}^{W}, K_{w}^{W}, C_{w}^{W} and C_{w}^{RW}.

2.* V* examines whether S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R})^{W} is the consistent signature pair on (T_{P}^{R+1}K_{w}C_{w}^{R})^{W} or not by using public verification key pair d_{1*} and d_{2*}. After that, *V* decomposes it into T_{P}^{W}, T_{P}^{RW}, K_{w}^{W} and C_{w}^{RW} based on the information given by *P*.

3. To confirm that *P* had calculated pairs {K_{w}^{W} = *k*^{w}^{W}, C_{w}^{W} = *c*^{w}^{W}} and {T_{P}^{R}^{W}, C_{w}^{R}^{W}} from integer pairs {*k*, *c*} and {T_{P}^{W}, C_{w}^{W}} while using *P*’s same secret integers *w*W and R respectively, *V* generates its secret integers {Θ_{1}, Θ_{2}, Θ_{3}} and {Λ_{1}, Λ_{2}, Λ_{3}}, calculates triplets {*k*^{Θ}^{1}, *c*^{Θ}^{2}, (*kc*)^{Θ}^{3}}, {K_{w}^{W}^{Θ}^{1}, C_{w}^{W}^{Θ}^{2}, (K_{w}^{W}C_{w}^{W})^{Θ}^{3}}, {(T_{P}^{W})^{Λ}^{1}, (C_{w}^{W})^{Λ}^{2}, (T_{P}^{W}C_{w}^{W})^{Λ}^{3}} and {(T_{P}^{RW})^{Λ}^{1}, (C_{w}^{RW})^{Λ}^{2}, (T_{P}^{RW}C_{w}^{RW})^{Λ}^{3}} and shows {*k*^{Θ}^{1}, *c*^{Θ}^{2}, (*kc*)^{Θ}^{3}} and {T_{P}^{W}^{Λ}^{1}, C_{w}^{W}^{Λ}^{2}, (T_{P}^{W}C_{w}^{W})^{Λ}^{3}} to *P*.

4.* P* calculates ζ_{1} = (*k*^{Θ}^{1})^{w}^{W}, ζ_{2} = (*c*^{Θ}^{2})^{w}^{W}, ζ_{3} = ((*kc*)^{Θ}^{3})^{w}^{W}, *D* = (T_{P}^{W}^{Λ}^{1})^{R}, ρ_{1} = (C_{w}^{W}^{Λ}^{2})^{R} and ρ_{2} = ((T_{P}^{W}C_{w}^{W})^{Λ}^{3})^{R}.

5. If relations ζ_{1} = K_{w}^{W}^{Θ}^{1}, ζ_{2} = C_{w}^{W}^{Θ}^{2}, ζ_{3} = (K_{w}^{W}C_{w}^{W})^{Θ}^{3}, *D* = (T_{P}^{RW})^{Λ}^{1}, ρ_{1} = (C_{w}^{RW})^{Λ}^{2} and ρ_{2} = (T_{P}^{RW}C_{w}^{RW})^{Λ}^{3} hold, *V* determines that *P* is an eligible entity that knows R.

**Fig**

**ure**

**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_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R})^{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 (*k*^{w}^{W})^{Θ}^{1}, (*c*^{w}^{W})^{Θ}^{2}, ((*kc*)^{w}^{W})^{Θ}^{3}, (T_{P}^{RW})^{Λ}^{1}, (C_{w}^{RW})^{Λ}^{2} and (T_{P}^{RW}C_{w}^{RW})^{Λ}^{3} from triplets {*k*^{Θ}^{1}, *c*^{Θ}^{2}, (*kc*)^{Θ}^{3}} and {(T_{P}^{W})^{Λ}^{1}, (C_{w}^{W})^{Λ}^{2}, (T_{P}^{W}C_{w}^{W})^{Λ}^{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 (T_{P}^{R+1}K_{w}C_{w}^{R})^{W} into exactly T_{P}^{W}, T_{P}^{RW}, K_{w}^{W} and C_{w}^{RW}.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_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R})^{W1}. Provided that W_{1}, W_{2}, W_{3}, --- are integers secrets of *P*, no one other than *P* can know S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R})^{W1}, S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R})^{W2}, S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R})^{W3}, --- are different forms of a same credential either.

*Proof *

Under the strong RSA assumption, anyone except *P* cannot know T_{P}, T_{P}^{R} or R from any of S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R})^{W1}, S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R})^{W2}, S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R})^{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_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}), S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R})^{W1}, S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R})^{W2}, S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R})^{W3}, ---, provided that W_{1}, W_{2}, W_{3}, --- are secrets of *P*. Q.E.D.

**Proposition 6**

Under the strong RSA assumption, entity *P* that shows credential S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R})^{W} can prove its ownership only when it calculates *D* = (T_{P}^{W}^{Λ1})^{R} as T_{P}^{W}^{Λ1} to the power of exactly R.

*Proof*

To use R_{*} instead of R (R_{*} ≠ R) while satisfying relations ζ_{1} = K_{*}^{W}^{*Θ}^{1}, ζ_{2} = C_{*}^{W}^{*Θ}^{2}, ζ_{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 (T_{P}^{R+1}K_{w}C_{w}^{R})^{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)} = (T_{P}^{R+1}K_{w}C_{w}^{R})^{W}/*k*^{w}^{*W*}*c*^{w}^{*}^{W}^{*R*}= T_{P}^{(R}^{+1}^{)W}*k*^{w}^{W-}^{w}^{*W*}*c*^{w}^{W}^{R-}^{w}^{*}^{W}^{*R*} = L. But because R ≠ R_{*}, L becomes a function of at least T_{P} and *k* or T_{P} and *c* (i.e. L is a function of at least T_{P} and *k* if *w*W ≠ *w*_{*}W_{*}, and it is a function of T_{P} and *c* if *w*W = *w*_{*}W_{*}). Then, under the strong RSA assumption and in a condition where to find integer pair {*y*, *y*^{*}} which satisfies relation L^{yy}^{*} = L is computationally infeasible,* P* that does not know q_{1}, q_{1*}, q_{2}, q_{2*}, q_{3} nor q_{3*} (it is assumed that T_{P} = *k*^{q1}, T_{P}^{q1*} = *k*, *k* = *c*^{q2}, *k*^{q2*} = *c*, *c* = T_{P}^{q3} and* c*^{q3*} = T_{P}) 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_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}) 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_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R})^{W} because verification keys d_{1*} and d_{2*} are publicly known and (T_{P}^{R+1}K_{w}C_{w}^{R})^{W} is decomposed into T_{P}^{W}, T_{P}^{RW}, K_{w}^{W} and C_{w}^{RW} 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_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}), namely it cannot disable other entity *P*_{*} to use S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}) as below.

Threat-1 *P*_{*} that steals S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}) 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 {T_{P}^{W}, K_{w}^{W}, C_{w}^{W}, C_{w}^{RW}} that *P* had shown with S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R})^{W} at its past visit to *V*.

Threat-3 *P*_{*} can use S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}) if *P* informs it of secret R, i.e. S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}) 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_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R})^{W} and S(d_{1}_{║}d_{2}, T_{P*}^{R*+1}K_{w}_{*}C_{w}_{*}^{R*})^{W*} while defining integer pairs {*w*, W} and {*w*_{*}, W_{*}} in the way relation *w*W = *w*_{*}W_{*} holds by chance, issuer *S* can detect this fact by duplicated appearances of K_{w}^{W} = K_{w}_{*}^{W*} (= *k*^{w}^{W}) and if *S* is conspiring with *P*_{*}, it can know *w*W (= *w*_{*}W_{*}) by asking it to *P*_{*}. But *S* cannot identify *P* from *w*W, i.e. *S* cannot extract W from *w*W to calculate T_{j}^{W} for each T_{j }it had generated so that it can compare T_{j}^{W} with T_{P}^{W} that *P* shows together with S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R})^{W}.

**3.3. Used Seals of Anonymous Credentials**

A used seal of anonymous credential S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}) owned by credential holder *P* is defined as *U*^{R}, where verifier *V* defines base integer *U* and *P* calculates used seal* U*^{R} by using its secret R. Then, because R is unique and known only to *P*, verifier *V* or issuer *S* can use *U*^{R} as an evidence that *P* had certainly used S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}) to receive services from *V*. Here, *V* cannot calculate R from *U*^{R} of course. In addition, although *V* does not know R, it can force *P* to honestly calculate *U*^{R} by extending the interactions in the credential verification procedure where *V* shows T_{P}^{W}^{Λ}^{1} and *P* calculates *D* = (T_{P}^{W}^{Λ}^{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 *U*^{R} that is consistent with S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}), 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 *U*^{R} honestly.

**Used seal generation procedure**

3_{*}. *V* generates its secret integer Ω, to calculate (*U*T_{P}^{W})^{Λ}^{1}^{Ω} in addition to T_{P}^{W}^{Λ}^{1} and T_{P}^{RW}^{Λ}^{1}, and shows it with *U* and T_{P}^{W}^{Λ}^{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*_{*} = *U*^{R} and *B* = {(*U*T_{P}^{W})^{Λ}^{1}^{Ω}}^{R} in addition to *D* = (T_{P}^{W}^{Λ}^{1})^{R}.* *

5_{*}. *V* examines whether relations *D* = (T_{P}^{RW})^{Λ}^{1} and *B* = *U*_{*}^{Λ}^{1}^{Ω}*D*^{Ω} hold or not.

**Proposition 7**

Under the strong RSA assumption, *P* that uses credential S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}) in the used seal generation procedure must calculate *U*_{*}, *D* and *B* honestly as *U*_{*} = *U*^{R}, *D* = (T_{P}^{W}^{Λ}^{1})^{R} and *B* = {(*U*T_{P}^{W})^{Λ}^{1}^{Ω}}^{R}, respectively from *U*, T_{P}^{W}^{Λ}^{1} and (*U*T_{P}^{W})^{Λ}^{1}^{Ω} shown by verifier *V*, provided that *V* is honest.

*Proof *

Proposition 6 ensures that *P* calculates *D* as (T_{P}^{W}^{Λ}^{1})^{R} based on its secret R, because *P* cannot prove the ownership of S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}) if *D* ≠ (T_{P}^{W}^{Λ}^{1})^{R}. About *U*_{*}, if *P* calculates *U*_{*} as *U*^{Q} instead of *U*^{R} (Q ≠ R), because relation *D* = (T_{P}^{RW})^{Λ}^{1} is ensured, *P* must calculate *B* as (*U*^{Q})^{Λ}^{1}^{Ω}*D*^{Ω}. But to calculate (*U*^{Q})^{Λ}^{1}^{Ω}*D*^{Ω}, *P* must decompose (*U*T_{P}^{W})^{Λ}^{1}^{Ω} into *U*^{Λ}^{1}^{Ω} and (T_{P}^{W})^{Λ}^{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 *U*^{Q} instead of *U*^{R} dishonestly when it conspires with verifier *V*, but as will be discussed in the next section* **U*^{Q} 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_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}) 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*_{1}(i), *U*_{2}(i), ---, *U*_{H}(i) defined by independent authorities *S*_{1}, *S*_{2}, ---, *S*_{H}, *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 C_{w}^{W} and decomposition {T_{P}^{W}, T_{P}^{RW}, K_{w}^{W}, C_{w}^{RW}} that *P* had shown with S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R})^{W} at its past visit to verifier *V*, can easily use credential S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}) while changing its form to S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R})^{WW*} = S(d_{1}_{║}d_{2}, (T_{P}^{R+1}K_{w}C_{w}^{R})^{WW*}). Namely, *P*_{*} that generates W^{*} and knows {T_{P}^{W}, T_{P}^{RW}, K_{w}^{W}, C_{w}^{W}, C_{w}^{RW}} can extract C_{w}^{WW*} and consistently decompose (T_{P}^{R+1}K_{w}C_{w}^{R})^{WW*} into {T_{P}^{WW*}, T_{P}^{RWW*}, K_{w}^{WW*}, C_{w}^{RWW*}}, and based on them, conspiring* P*_{*} and *V*_{*} can carry out the credential verification procedure legitimately. Here, *P*_{*} shows S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R})^{WW*} instead of S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R})^{W} so that *V*_{*} will not be accused of having accepted same credential forms repeatedly even when the dishonest use of S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}) 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_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R})^{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_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}), 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_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}) 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_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}) from threat-3, the enhanced anonymous tag based credential scheme limits the number of times that entities can use same credential S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}) 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_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}), 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_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}) 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_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R})^{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_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}) 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_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R})^{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_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R})^{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_{1}_{║}d_{2}, T_{P*}^{R*+1}K_{w}_{*}C_{w}_{*}^{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*_{0}^{R} in addition to *U*(*V*, m)^{R}, where *S* asks all credential holders to calculate their initial used seals based on *U*_{0} 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_{1}_{║}d_{2}, T_{P*}^{R*+1}K_{w}_{*}C_{w}_{*}^{R*})^{W*}, calculates *U*_{r(P*)} = *U*(n)^{r(P*)}, *U*_{R} = *U*(n)^{Rr}^{(}^{P*}^{)}, L_{1} = T_{P*}^{W*}^{r(P*)} and L_{2} = T_{P*}^{R*W}^{*}^{r(P*)}.

3.* S* examines whether relations *U*_{r(P*)} = *U*(n)^{π}, *U*_{R} = *U*(n)^{R}^{π}, L_{1} = T_{P*}^{W*π} and L_{2} = T_{P*}^{R*W}^{*π} hold for same unknown π or not, and generates its secret integers τ and ξ to calculate L_{1}^{τ} and (*U*_{r(P*)}L_{1})^{τ}ξ.

4. *P*_{*} calculates* D*_{*} = (L_{1}^{τ})^{R*}* *and* B*_{*} = {(*U*_{r(P*)}L_{1})^{τ}ξ}^{R*}* *together with* U*_{R*} = *U*_{r(P*)}^{R*}.

5.* S* determines *P*_{*} is liable when one of relations* D*_{*} = L_{2}^{τ} and^{ }*B*_{*} = *U*_{R*}^{τ}ξ*D*_{*}ξ does not hold or *U*_{R*} = *U*(n)^{R*r(}^{P*}^{)} coincides with *U*_{R} = *U*(n)^{Rr}^{(}^{P*}^{)} (i.e. R^{*} = R).

In the above, relations *D*_{*} = L_{2}^{τ}^{ }and^{ }*B*_{*} = *U*_{R*}^{τ}ξ*D*_{*}ξ correspond to *D* = (T_{P}^{RW})^{Λ}^{1} and *B* = *U*_{*}^{Λ}^{1}^{Ω}*D*^{Ω} in the used seal generation procedure, therefore *P*_{*} is forced to calculate *U*_{R*} =* U*_{r(P*)}^{R*} = *U*(n)^{R*}^{r(P*)} honestly. Also, *S* can verify relations *U*_{r(P*)} = *U*(n)^{π}, *U*_{R} = *U*(n)^{R}^{π}, L_{1} = T_{P*}^{W*π}, and L_{2} = T_{P*}^{R*W}^{*π} in the same way as pair {K_{w}, C_{w}} in Sec. 3.2 was examined, and this means *P*_{*} calculates *U*_{R} as *U*(n)^{Rr(P*)}. Then, S can conclude that *P*_{*} is liable for the dishonest record when *U*_{R*} coincides with *U*_{R}, namely used seals *U*(n)^{R*r(}^{P*}^{)} and *U*(n)^{Rr}^{(}^{P*}^{)} of credentials S(d_{1}_{║}d_{2}, T_{P*}^{R*+1}K_{w}_{*}C_{w}_{*}^{R*}) and S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}) 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_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}), *S* constructs record {*U*(n), *U*(n)^{R}} in the invalid credential list from initial used seal {*U*_{0}, *U*_{0}^{R}} that *P* had left when S issued S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}). Then at a time when entity *P*_{*} shows its credential S(d_{1}_{║}d_{2}, T_{P*}^{R*+1}K_{w}_{*}C_{w}_{*}^{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 rejecti****on**** procedure**

1.* P*_{*} that requests *V*_{*}’s service by showing credential S(d_{1}_{║}d_{2}, T_{P*}^{R*+1}K_{w}_{*}C_{w}_{*}^{R*}) in form S(d_{1}_{║}d_{2}, T_{P*}^{R*+1}K_{w}_{*}C_{w}_{*}^{R*})^{W}^{*} calculates *U*_{r(P*)} = *U*(n)^{r(P*)}, *U*_{R} = *U*(n)^{Rr}^{(}^{P*}^{)}, L_{1} = T_{P*}^{W*}^{r(P*)} and L_{2} = T_{P*}^{R*W}^{*}^{r(P*)}. Here, *r*(*P*_{*}) is a secret integer generated by *P*_{*}.

2.* V*_{*} examines whether relations *U*_{r(P*)} = *U*(n)^{π}, *U*_{R} = *U*(n)^{R}^{π}, L_{1} = T_{P*}^{W*π} and L_{2} = T_{P*}^{R*W}^{*π} hold for same unknown π or not, and generates its secret integer τ and ξ to calculate L_{1}^{τ} and (*U*_{r(P*)}L_{1})^{τ}ξ.

3. *P*_{*} calculates* D*_{*} = (L_{1}^{τ})^{R*}* *and* B*_{*} = {(*U*_{r(P*)}L_{1})^{τ}ξ}^{R*}* *together with* U*_{R*} = *U*_{r(P*)}^{R*}.

4.* V*_{*} accepts *P*_{*}’s request when relations* D*_{*} = L_{2}^{τ}^{ }and^{ }*B*_{*} = *U*_{R}_{*}^{τ}ξ*D*_{*}ξ hold and *U*_{R*} = *U*(n)^{R*r(}^{P*}^{)} does not coincide with *U*_{R} = *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})^{w}^{W}, ζ_{2} = (*c*^{Θ}^{2})^{w}^{W}, ζ_{3} = ((*kc*)^{Θ}^{3})^{w}^{W}, *D* = (T_{P}^{W}^{Λ}^{1})^{R}, ρ_{1} = (C_{w}^{W}^{Λ}^{2})^{R}, ρ_{2} = (T_{P}^{W}C_{w}^{W})^{Λ}^{3}^{R}, *U*_{*} = *U*(n)^{R} and* B* = {*U*(n)T_{P}^{W}}^{Λ}^{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(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R})^{W}, to honestly calculate used seal *U*^{R}, verifier *V* in the original scheme generates multiple secret integers X_{1}, X_{2}, ---, X_{M}, and calculates (T_{P}C_{w})^{W(X1)},* *(T_{P}C_{w})^{W(X2)}, ---, (T_{P}C_{w})^{W(XM)} to ask *P* to calculate (T_{P}C_{w})^{W(X1)R},* *(T_{P}C_{w})^{W(X2)R}, ---, (T_{P}C_{w})^{W(XM)R} and {*U*(T_{P}C_{w})^{WXY}}^{R}* *by showing {(T_{P}C_{w})^{W(X1)},* *(T_{P}C_{w})^{W(X2)}, ---, (T_{P}C_{w})^{W(XM)}, *U*(T_{P}C_{w})^{WXY}} while randomly changing their positions. Namely, if *P* honestly calculates {*U*(T_{P}C_{w})^{WXY}}^{R}, *V* can know *U*^{R} as {*U*(T_{P}C_{w})^{WXY}}^{R}/(T_{P}C_{w})^{WXYR}. On the other hand if *P* tries to calculate it dishonestly, it may calculate (T_{P}C_{w})^{W(Xq)} inconsistently because it cannot identify *U*(T_{P}C_{w})^{WXY} in {(T_{P}C_{w})^{W(X1)}, ---, (T_{P}C_{w})^{W(XM)}, *U*(T_{P}C_{w})^{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_{1}, X_{2}, ---, X_{M} 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_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R})^{W} in the proposed scheme is configured as S(d, T_{P}^{R+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, T_{P}^{R+Gg+G+1})^{W} cannot disable *P* to calculate used seal as *U*^{R*} instead of* U*^{R} while using integer R_{*} (≠ R). In the enhanced scheme, K_{w}^{W} and C_{w}^{RW} included in credential S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R})^{W} disable *P* to dishonestly calculate used seals as shown in Proposition 7. Also, signature pair S(d_{1}_{║}d_{2}, *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 T_{A} 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_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}T_{A}_{w}^{a+1})^{W} based on credential S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}T_{A}_{w}^{a+1}) given from *S* and its secret integer W, and by showing it together with T_{P}^{W}, K_{w}^{W}, C_{w}^{W}, C_{w}^{RW}, T_{A}_{w}^{W} and T_{Aw}^{aW}. Here, T_{P}^{R+1}K_{w}C_{w}^{R} constitutes the identity part and T_{P}, K_{w} =*k*^{w}, C_{w}^{ }= *c*^{w} and R are defined as in Sec. 3.2. On the other hand, T_{A}_{w}^{a+1} constitutes the attribute part, and T_{A} is defined by *S* so that no one other than S can know integers v_{1}, v_{1*}, v_{2}, v_{2*}, v_{3}, v_{3*} that satisfy relations T_{A} = T_{P}^{v1}, T_{A}^{v1*} = T_{P}, T_{A} = *k*^{v2}, T_{A}^{v2*} = *k*, T_{A} = *c*^{v3}, T_{A}^{v3*} = *c*, and *P* calculates T_{A}_{w} as T_{A}^{w} while using its secret integer *w* that it had used for calculating K_{w} = *k*^{w} and C_{w}^{ }= *c*^{w}.

**Fig**

**ure**

**4.**Identity and attribute parts

The identity part in S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}T_{A}_{w}^{a+1}) plays the same roles as credential S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}) in previous sections did, i.e. the identity part conceals the identity of credential holder *P* while ensuring *P* is eligible, therefore identity part T_{P}^{R+1}K_{w}C_{w}^{R} must conceal R from anyone except *P*. On the other hand the purpose of attribute part T_{A}_{w}^{a+1} at this stage is not to conceal attribute value *a*, instead, the role of T_{A}_{w}^{a+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.

**A****ttribute value verification procedure 1**

1. *P* shows credential S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}T_{A}_{w}^{a+1})^{W} with T_{P}^{W}, K_{w}^{ W}, C_{w}^{W}, C_{w}^{RW}, T_{A}_{w}^{W}, T_{A}_{w}^{aW} 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_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}T_{A}_{w}^{a+1})^{W} and decomposes (T_{P}^{R+1}K_{w}C_{w}^{R}T_{A}_{w}^{a+1})^{W} into T_{P}^{W}, T_{P}^{RW}, K_{w}^{ W}, C_{w}^{RW}, T_{A}_{w}^{W} and T_{A}_{w}^{aW} based on the information given by *P*.

3. To determine whether *P* is an eligible holder of S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}T_{A}_{w}^{a+1})^{W} or not, *V* examines the consistency of decomposition {T_{P}^{W}, T_{P}^{RW}, K_{w}^{ W}, C_{w}^{RW}} as in steps 3-5 of the credential verification procedure.

4. *V* confirms that *P* had calculated T_{A}_{w}^{W} as T_{A} to the power of unknown *w*W that was used for calculating K_{w}^{W} = *k*^{w}^{W} and C_{w}^{W }= *c*^{w}^{W}, and determines that *P* deserves *a* when relation T_{A}_{w}^{aW} = (T_{A}_{w}^{W})^{a} holds.

From discussions in previous sections, it is apparent that the above procedure ensures *P* is the eligible holder of S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}T_{A}_{w}^{a+1})^{W}, i.e. only *P* that knows R can use the credential. In addition, attribute part (T_{A}_{w}^{a+1})^{W} disables *P* to declare attribute value *a* dishonestly as follow, i.e. when *P* decomposes T_{A}_{w}^{(a+1)W} into T_{A}_{w}^{w*} and T_{A}_{w}^{a*w*} while finding integers *a*_{*} and W_{*} that are different from *a* and W, although relation T_{A}_{w}^{a*w*}T_{A}_{w}^{w*} = T_{A}_{w}^{(a+1)W} may hold, *V* detects the dishonesty because T_{A}_{w}^{w*} and K_{w}^{W} are T_{A} and *k* to the power of different integers.

Credential S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}) 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 T_{E}, *P* calculates T_{E}_{w} = T_{E}^{w} and T_{E}_{w}^{e+1} based on attribute value *e* to construct the credential as S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}T_{A}_{w}^{a+1}T_{E}_{w}^{e+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_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}T_{A}_{w}^{a+1}T_{E}_{w}^{e+1})^{W} is not examined for example, *P* that possesses an illegitimate credential can declare the value of T_{E}_{w}^{(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 {T_{A}_{w}^{W}, T_{A}_{w}^{aW}}, 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 T_{A}_{w}^{Wa*} from T_{A}_{w}^{W} for every possible attribute value *a*_{*} to compare the result with T_{A}_{w}^{aW}. 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_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}T_{A}_{w}^{a}^{+1}) instead of S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}T_{A}_{w}^{a+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 {T_{A}_{w}^{W}, T_{A}_{w}^{a}^{W}} by calculating T_{A}_{w}^{W}^{a}^{*} from T_{A}_{w}^{W} 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_{1}_{║}e_{2}, T_{P}^{Re}K_{w}C_{w}^{Re}T_{A}_{w}^{Q1+1}) that includes integer Q_{1} as below, where the reference credential enables *P* to convince others that relation *max*/2 < Q_{1} < *max* holds while concealing Q_{1} itself, and e_{1} and e_{2} in it are singing keys of *S* that are different from d_{1} and d_{2}, as will be discussed at the end of this section.

**Fig**

**ure**

**5.**Real and dummy parts in an attribute value

**Attribute value ****generation**** procedure**

1. *P *shows reference credential S(e_{1}_{║}e_{2}, T_{P}^{Re+1}K_{w}C_{w}^{Re}T_{A}_{w}^{Q1+1}) with {T_{P}^{Re}, K_{w}, C_{w}, C_{w}^{Re}, T_{A}_{w}, T_{A}_{w}^{Q1}} to *S*, and convinces *S* that decomposition {T_{P}, K_{w}, C_{w}, C_{w}^{Re}, T_{A}_{w}, T_{A}_{w}^{Q1}} of T_{P}^{Re+1}K_{w}C_{w}^{Re}T_{A}_{w}^{Q1+1} is consistent.

2. *P* generates random integer *a*’ that satisfies relations *max*/2 <* a*’ < *max* and *a*’ < Q_{1}, and calculates T_{A}_{w}^{a}, T_{A}_{w}^{a}^{’}, T_{A}_{w}^{Q1} and* *T_{A}_{w}^{Q1-}^{a}^{’} to show them together with T_{A}_{w}^{Q1}, *a* and Q_{1} - *a*’ to *S*.

3. *S* confirms that Q_{1} - *a*’ is less than *max*/2, T_{A}_{w}^{Q1} is certainly calculated from reference credential S(e_{1}_{║}e_{2}, T_{P}^{Re+1}K_{w}C_{w}^{Re}T_{A}_{w}^{Q1+1}), T_{A}_{w}^{Q1-}^{a}^{’} equals to T_{A}_{w}^{Q1}/T_{A}_{w}^{a}^{’}, and T_{A}_{w}^{a} and T_{A}_{w}^{Q1-}^{a}^{’} are T_{A}_{w} to the power of *a* and (Q_{1} - *a*’), respectively.

4. *S* calculates T_{A}_{w}^{a}^{+1} = T_{A}_{w}^{a}T_{A}_{w}^{a}^{’}T_{A}_{w} = T_{A}_{w}^{a+a}^{’}^{+1} to include it in credential S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}T_{A}_{w}^{a}^{+1}).

In the above, *S* issues credential S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}T_{A}_{w}^{a}^{+1}) while identifying *P*, therefore *P* can show reference credential S(e_{1}_{║}e_{2}, T_{P}^{Re+1}K_{w}C_{w}^{Re}T_{A}_{w}^{Q1+1}) without changing its form. Also *P* in step 3 can convince others that T_{A}_{w}^{Q1} is certainly included in reference credential S(e_{1}_{║}e_{2}, T_{P}^{Re+1}K_{w}C_{w}^{Re}T_{A}_{w}^{Q1+1}) because T_{A}_{w}, K_{w} and C_{w} are calculated as T_{A}_{w} = T_{A}^{w}, K_{w} = *k*^{w}, C_{w}^{ }= *c*^{w} by same unknown integer *w*, and this ensures that T_{A}_{w}^{Q1} is calculated as T_{A}_{w} to the power of integer Q_{1} that satisfies relation *max*/2 < Q_{1} < *max* although Q_{1} 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_{1} < *max* holds, apparently (Q_{1} - *a*’) becomes less than *max*/2 because *max*/2 < Q_{1} < *max* is ensured, but when *a*’ > *max* (this means *a*’ > Q_{1}),* *(Q_{1} - *a*’)_{mod B} is calculated as (Q_{1} - *a*’)_{mod B} = B + (Q_{1} - *a*’) = Q_{1} + (B - *a*’), i.e. (Q_{1} - *a*’)_{mod B} becomes greater than *max*/2 because Q_{1} > *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_{1} - *a*’), T_{A}_{w}^{a}^{’} and T_{A}_{w}^{Q1-}^{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_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}T_{A}_{w}^{a}^{+1}) is greater than *b* that is designated by *V*, under the condition that all integers *a*, *b*, Q and *a*^{2}, *b*^{2}, Q^{2} are less than B/2, and although Q is *P*’s secret integer, *P* can convince *V* relations Q < B/2 and Q^{2} < B/2 by reference credential S(e_{1}_{║}e_{2}, T_{P}^{Re+1}K_{w}C_{w}^{Re}T_{A}_{w}^{Q+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_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}T_{A}_{w}^{a}^{+1}) and reference credential S(e_{1}_{║}e_{2}, T_{P}^{Re+1}K_{w}C_{w}^{Re}T_{A}_{w}^{Q+1}) calculates S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}T_{A}_{w}^{a}^{+1})^{W} and S(e_{1}_{║}e_{2}, T_{P}^{Re+1}K_{w}C_{w}^{Re}T_{A}_{w}^{Q+1})^{W*} to show them to *V*, with {T_{P}^{W}, K_{w}^{W}, C_{w}^{W}, C_{w}^{RW}, T_{A}_{w}^{W}, T_{A}_{w}^{a}^{W}} and {T_{P}^{W}^{*}, K_{w}^{W}^{*}, C_{w}^{W}^{*}, C_{w}^{R}^{e}^{W}^{*}, T_{A}_{w}^{W}^{*}, T_{A}_{w}^{QW*}}.

2.* V* decrypts S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}T_{A}_{w}^{a}^{+1})^{W} to (T_{P}^{R+1}K_{w}C_{w}^{R}T_{A}_{w}^{a}^{+1})^{W}, decomposes the result to T_{P}^{W}, T_{P}^{RW}, K_{w}^{W}, C_{w}^{RW}, T_{A}_{w}^{W} and T_{A}_{w}^{a}^{W}, and confirms that the decomposition is consistent. In the same way, it decrypts S(e_{1}_{║}e_{2}, T_{P}^{R}^{e}^{+1}K_{w}C_{w}^{R}^{e}T_{A}_{w}^{Q+}^{1})^{W}^{*} to (T_{P}^{R}^{e}^{+1}K_{w}C_{w}^{R}^{e}T_{A}_{w}^{Q+}^{1})^{W}^{*}, decomposes the result to T_{P}^{W}^{*}, T_{P}^{R}^{e}^{W}^{*}, K_{w}^{W}^{*}, C_{w}^{R}^{e}^{W}^{*}, T_{A}_{w}^{W}^{*} and T_{A}_{w}^{QW*}, and confirms the decomposition is consistent.

3. *V* generates *b* and calculate *U*^{b}, where *U* is the base of used seals.

4. *P* generates used seals *U*^{a} from pair {T_{A}_{w}^{W}, T_{Aw}^{a}^{W}} in S(d_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}T_{A}_{w}^{a}^{+1})^{W*} to calculate *U*^{a}/*U*^{b} =* U*^{a}^{-}^{b}. *P* also calculates used seal* U*^{(}^{a}^{-}^{b}^{)Q} from pair {T_{A}_{w}^{W*}, T_{A}_{w}^{Q}^{W*}} in S(e_{1}_{║}e_{2}, T_{P}^{Re+1}K_{w}C_{w}^{Re}T_{A}_{w}^{Q+1})^{W*} and base value *U*^{(}^{a}^{-}^{b}^{)}, and discloses *U*^{a}, *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 *U*^{a} and *U*^{(}^{a}^{-}^{b}^{)Q} as shown in Proposition 7. In addition, relations *a* < B/2, *b* < B/2, Q < B/2, *a*^{2} < B/2, *b*^{2} < B/2 and Q^{2} < B/2 are ensured, where, *S* can confirm that *a* < B/2 and *a*^{2} < 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_{1}_{║}e_{2}, T_{P}^{Re+1}K_{w}C_{w}^{Re}T_{A}_{w}^{Q+1}) as shown later. Therefore, (*a*-*b*)Q_{mod 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*)Q_{mod B} = B + (*a*-*b*)Q, as a consequence, (*a*-*b*)Q_{mod 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_{1}_{║}d_{2}, T_{P}^{R+1}K_{w}C_{w}^{R}T_{A}_{w}^{a}^{+1}T_{E}_{w}^{e}^{+1})^{W} owned by *P*, *V* can confirm that *P* honestly extracts T_{E}_{w}^{(}^{e}^{+1)W} from the credential by asking *P* to prove that it knows *e* included in T_{E}_{w}^{(}^{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^{2} < B/2 without disclosing Q by obtaining reference credential S(e_{1}_{║}e_{2}, T_{P}^{Re+1}K_{w}C_{w}^{Re}T_{A}_{w}^{Q+1}) in the course of member registration procedure, in which issuer *S* accepts *P* as an eligible entity. Here, *S* uses signing key e_{1} and e_{2} that are different from d_{1} and d_{2} to discriminate reference credentials from usual ones. Now *P* obtains reference credential S(e_{1}_{║}e_{2}, T_{P}^{Re+1}K_{w}C_{w}^{Re}T_{A}_{w}^{Q+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 T_{A}^{u1} = G_{1}, T_{A}^{u2} = G_{2}, ---, T_{A}^{uN} = G_{N} while generating a set of secret integers {u_{1}, ---, u_{N}} and shows G_{1}, G_{2}, ---, G_{N} to S.

2.* S* chooses single integer G_{q} from {G_{1}, ---, G_{N}}.

3.* P* discloses each u_{j} except u_{q}.

4. For each disclosed u_{j}, *S* examines relations u_{j} < B/2, u_{j}^{2} < B/2 and T_{A}^{uj} = G_{j}, and when the relations are satisfied, as the value of T_{Aw}^{Q+1} it includes T_{A}^{uq+1} in reference credential S(e_{1}_{║}e_{2}, T_{P}^{Re+1}K_{w}C_{w}^{Re}T_{A}_{w}^{Q+1}).

In the above, apparently *P* can conceal u_{q} ( = Q) from *S*. On the other hand, although *P* can define u_{q} illegitimately, it must disclose u_{q} if *S* does not choose it, and this means *S* can convince itself that u_{q} satisfies the conditions u_{q} < B/2 and u_{q}^{2} < B/2 with probability (N-1)/N. *P* can generate reference credential S(e_{1}_{║}e_{2}, T_{P}^{Re+1}K_{w}C_{w}^{Re}T_{A}_{w}^{Q1+1}) in the attribute value generation procedure in the same way. Here, although *S* must ask *P* to calculate a large number of integers {T_{A}^{u1}, ---, T_{A}^{uN}} 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 EUROCRYPT’01, 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 CRYPTO’88, 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 | |||