A Short Paper on How to Improve U-Prove Using
Self-Blindable Certificates?
Lucjan Hanzlik and Kamil Kluczniak
Faculty of Fundamental Problems of Technology,
Wrocław University of Technology{firstname.secondname}@pwr.wroc.pl

Abstract. U-Prove is a credential system that allows users to disclose information about themselves in a minimalistic way. Roughly speaking, in the U-Provesystem a user obtains certified cryptographic tokens containing a set of attributes
and is able to disclose a subset of his attributes to a verifier, while hiding theundisclosed attributes. In U-prove the actual identity of a token holder is hiddenfrom verifiers, however each token has a static public key (i.e. token pseudonym),
which makes a single token traceable, by what we mean that, if a token is presented twice to a verifier, then the verifier knows that it is the same token. We
propose an extension to the U-Prove system which enables users to show U-Provetokens in a blinded form, so even if a single token is presented twice, a verifier is
not able to tell whether it is the same token or two distinct tokens. Our proposition
is an optional extension, not changing the core of the U-Prove system. A verifier
decides whether to use issuer signatures from U-Prove, or the blind certificatesfrom the extension.
Key words: U-Prove, Anonymous Credentials, Self-Blindable Certificates

1

Introduction

David Chaum in [1] sketched some of the problems related to identity certificates. Oneof them is that service providers are able to track the activity of users. The idea tohide the actual identity of a user is based on pseudonyms. A pseudonym is a unique
identifier by which a user can authenticate against some parties in the system. Typically pseudonyms are issued by service providers in order to blind the actual identityof a user. Pseudonymity can be differently understood. In some systems users appear
under just one pseudonym which sometimes is called a token. Other systems provide
unique pseudonyms for a user which are different in distinct service providers and even
if these service providers cooperate, the pseudonyms cannot be linked. This means thathaving two or more pseudonyms it is infeasible to decide whether the pseudonym isrelated to one user or many different users. The notion of unlinkability was also described in [1] and can be differently understood. One situation is, as described above,
when a user presents different pseudonyms in different domains and the identity cannot?

This research was conducted within project 2012-9/4 of the Ventures programme of Foundation for Polish Science, cofinanced from European Union, Regional Development Fund.

2

Lucjan Hanzlik and Kamil Kluczniak

be linked between this domains, however within one domain a user appears under justone pseudonym and thus is tracable in it [2]. Another situation is when each authentication session provides a new pseudonym. We will call the second situation untraceability
since the data which a user passes during two or more authentication sessions are unlinkable, so it cannot be used to trace the activity of a particular user.
Generally, the anonymity notion appears in a range of different protocols and schemes.
The main goal of group signatures [3,4,5] , for instance, is to identify that a signer belongs to a group and the signatures made by any group member are unlinkable in thesense that, a verifier checks only if a signature was made by a relevant group member,but it is infeasible to determine who exactly produced that signature.
A similar notion of anonymity can be observed in anonymous credential systems
where a user can prove different statements about himself, but without revealing anyother information to a verifier. Such credential systems based on CL-Signatures [6] were
designed in [7] and are constructed for algebraic groups of unknown order. Anothercredential system, designed by Microsoft, is called U-Prove [8] where a user obtains
authentication tokens and is able to proof statements about himself, which are containedin that token. The token contains a public key, so in some sense it is a pseudonym of auser, and an issuer certificate on that public key. Presenting one U-Prove token twice ormore requires to show the token public key and the certificate in an unblinded form, so
a set of verifiers can easily track a single token.
In this short paper we study the possibility to improve the U-Prove credential systemby providing the untraceability property for a U-Prove token. So in effect, many presentations of a single token should be unlinkable. We believe that an interesting building
block introduced by Verhuel in [9], called self-blindable certificate, can naturally provide the untraceability property for credential systems such as U-Prove. The idea behinda self-blindable certificate is, that a issuer generates a certificate under a users public
key, and the user can present such certificate in an blinded form to a verifier.
Contribution We show an extension to the Microsoft U-Prove credential systemproviding the untraceability property for U-Prove tokens using self-blindable certificates. In short, instead of obtaining a linkable certificate on a token, we issue a selfblindable certificate on the token public key, so a token holder can show statements
related to the token without revealing the token public key, i.e. show the token public
key in an blinded form and prove that it is genuine by showing the blinded certificate.
In effect two or more authentication sessions become unlinkable and verifiers cannot
track one particular token. Our extension don’t changes the U-Prove system substantially. A verifier can choose, depending on his intend, whether to verify the standard
U-Prove certificate or the self-blindable certificate. In the first case, the protocols goesunchanged as described in the specification [8]. When self-blindable certificates areused, then some steps of the protocol are modified. First in section 2 we describe a construction for self-blindable certificates from [9]. Then, we give a high-level descriptionof the U-Prove system and indicate the changes between our contribution and the original protocol in section 3. Finally in section 4 we give a brief security analysis of our
proposed extension.

A Short Paper on How to Improve U-Prove Using Self-Blindable Certificates2

3

Self-Blindable Certificates

We first recall the definition of Self-Blindable Certificates as described in [9] by Verheul. Then, we present a construction that implements this definition.
2.1

Definition

We assume that the system consists of users and a trust provider. We define a certificate
on a users public key PU ∈ U, signed with the trust providers secret key ST , as:{PU , Sig(PU , ST )}.
Let C be the set of all possible certificates and let F be a set called transformation
factor space. We call the certificates C self-blindable if there exist a efficiently computable transformation map D : C × F → C such that:– For any certificate C ∈ C and f ∈ F the certificate D(C, f ) is signed with thesame trust provider secret key as the certificate C.
– Let C1 , C2 be certificates and let f ∈ F is known. If C2 = D(C1 , f ) then one canefficiently compute a transformation factor f 0 ∈ F such that C1 = D(C2 , f 0 ).
– The mapping D(., .) induces a mapping D0 : U × F → U namely if C1 , C2 arecertificates on a users public key PU , then D(C1 , f ) and D(C2 , f ) are certificates
for the public key D0 (PU , f ), for any transformation factor f ∈ F .
– Let PU be the public key of a user and let f ∈ F be a transformation factor known
by the user. If the user possesses the private key for PU , then the user also knows
the private key for D0 (PU , f ).
– If the users public key PU is fixed and the transformation factor f is a uniformly
random element in F , then D0 (PU , f ) is a uniformly random element in U.
2.2

Instantiation

Definition 1. Let G1 , G2 , GT be cyclic groups of prime order q. Let e : G1 ×G2 → GT
be a map with the following properties:– for P ∈ G1 , Q ∈ G2 and a, b ∈ Zq , we have e(aP, bQ) = e(P, Q)a·b ,– if P is a generator of G1 and Q is a generator of G2 , then e(P, Q) generates GT ,– there is an efficient algorithm to compute e(P, Q) for P ∈ G1 , Q ∈ G2 .
We now say that the function e is a:– Type 1 pairing function if G1 = G2 ,– Type 2 pairing function if G1 and G2 are distinct groups and there exists a efficiently computable isomorphism ψ : G2 → G1 ,– Type 3 pairing function if G1 and G2 are distinct groups and there is no known
isomorphism ψ : G2 → G1 .
Type 1 pairing is also called symmetric, because G1 = G2 . Type 2 and type 3 are called
asymmetric.
From now on, we will only use the multiplicative notation (even when the group isadditive) to simplify the description and to remain compatible with the U-Prove Crypto
Specification V1.1 [8].

4Lucjan Hanzlik and Kamil Kluczniak

Construction We present the second construction from [9]. However, we extend theconstruction to type 2 pairing (so the security analysis in [9] is valid) and not only type1 as is the original description.
In this case we define the set U as G31 , the transformation factor space F as Z2q andthe certificate space C as G1 . In addition let P1 be the generator of G1 and P2 be thegenerator of G2 .
Let z, f ∈ Zq be the private key of the trust provider and let r, rf , h, hz (for random r, h ∈ G2 ) be his public key. The users public key takes the following form:(g1 , g2 , g1x1 g2x2 ), where g1 is a random element in G1 , g2 = g1f and (x1 , x2 ) is the private key of the user. The certificate for the users public key is (g1x1 g2x2 )z . The certificate
can be easily verified by checking if:?

e(g1x1 g2x2 , hz ) = e((g1x1 g2x2 )z , h)and?

e(g1 , rf ) = e(g2 , r)and by verifying that the user knows x1 and x2 , which can be checked using the
Okamoto variant of Schnorr’s identification scheme [10].
Note that, for a random (k, l) ∈ F , D(., .) and D0 (., .) defined as follows:D((g1x1 g2x2 )z , (k, l)) = (g1x1 g2x2 )z·l·k ,D ((g1 , g2 , g1x1 g2x2 ), (k, l)) = (g1l , g2l , (g1x1 g2x2 )l·k )0fulfil the above definition of self-blindable certificates.

3

Our Contribution

In this section, we will present our extension. We describe it by embedding it into the UProve Crypto Specification V1.1 [8]. Due to space reasons we only show a sketch of thesystem. Thus, we advise to read this section in conjunction with [8]. Our extension is an
optional feature. In short, a token issuer makes an additional self-blindable certificate
on the tokens public key. In the proof generation and verification a user or verifier,depending on the use case, can choose whether to show the standard signature specified
in [8] or the self-blindable certificate from our proposed extension. We will denote as[Standard] the situation when the signature from [8] is used, and as [Blinding] when
the self-blindable certificate is used. An exception from this is the issuing phase, where
both certificates are issued to the token holder.
3.1

System Parameters

The system parameters consist of the standard U-Prove parameters:
IP = (U IDP , desc(G1 ), U IDH , (g0 , g1 , . . . , gn , gt ),(e1 , . . . , en ), (z0 , z1 , . . . , zn , zt ), S)
where– U IDP is a unique identifier of the token,– desc(G1 ) is the description of a group of prime order q with a generator g ∈ G1

A Short Paper on How to Improve U-Prove Using Self-Blindable Certificates5– U IDH is the specification of the hash function H,– (g0 , g1 , . . . , gn , gt ) is the issuers public key, where y0 is private, g0 = g y0 and
g1 , . . . , gt are random group generators.
– (e1 , . . . , en ) list of byte values indicating whether or not the attribute values A1 , . . . , An
are hashed computing an UProve token.
– (z0 , z1 , . . . , zn , zt ) for each i ∈ {1, . . . , n, t}, zi = giy0 .
– S - specification for the issuer parameters.
and the additional extension parameters:
IP[Blinded] = (q, p, pr , G2 , GT , e, p0 , p1 ).
where G2 is a cyclic group of order q generated by p, r is random in Zq , e is a Type 2
pairing in sense of Definition 1, p0 = pr·z , p1 = pf and (z, f ) is the issuers secret key.
3.2

Issuing U-Prove Token

The issuing protocol is similar to the one in the specification [8]. In the issuing procedure the user receives a U-Prove token of the form:
T = (U IDP , h, T I, IP, (σz0 , σc0 , σr0 )[STANDARD] , (B)[BLINDED] ).
During the issuing procedure the user generates a private key α ∈ Zq which is associated with the public key h = (g0 g1x1 . . . gnxn gtxt )α of the token T . The values σz0 , σc0
and σr0 form the issuer signature on the public key h.
In our extension, a user obtains a self-blindable certificate on the tokens public key
h. The issuer computes h2 = hf . The user then chooses two private keys b1 and b2 ,computes a value hb1 hb22 on which the issuer makes his signature using his private key
z. Finally, the self-blindable certificate with the corresponding public key, obtained by
the user is of the form B = (h, h2 , hb1 hb22 , (hb1 hb22 )z ) and his private keys associatedto the certificate are b1 and b2 .
3.3

Presenting U-Prove TokenIn this subsection we describe the proof presentation procedure.
Input:
1. Disclosed attributes: D ⊂ {1, . . . , n},
2. Undisclosed attributes: U ⊂ {1, . . . , n}\D,
3. U-Prove token: T = (U IDP , h, T I, IP, (σz0 , σc0 σr0 )[STANDARD] , (B)[BLINDED] ),4. Message: m ∈ {0, 1}∗ ,5. Private key: α,
6. Attribute values: (A1 , . . . , An ) ∈ ({0, 1}∗ )n .
Proof Generation:
1. For each i ∈ U , generate wi ∈ Zq andQ generate w0 ∈ Zq ,2. [Standard] Compute a = H(hw0 ( i∈U giwi )), or6

Lucjan Hanzlik and Kamil Kluczniak

Q
2. [Blinded] Choose a random blinding l and compute a = H(hw0 ·l ( i∈U giwi ))3. xt = ComputeXt(IP, T I),
4. For each i ∈ {1, . . . , n}, xi = ComputeXi(IP, Ai ),5. [Blinded] Compute the blinded token(a) Blind the U-Prove public key B1 = hl , where l is chosen randomly,(b) Blind the certificate for the token by computing B2 = hl2 , B3 = (hb1 hb22 )l·k
and B4 = ((hb1 hb22 )z )l·k , where k is chosen randomly.
(c) Choose r1 , r2 at random, and compute additionally B10 = B1r1 and B20 = B2r2 .
(d) The blinded certificate consists of Bb = (B1 , B2 , B3 , B4 , B10 , B20 )(e) Set the blinded token as T = (U IDP , T I, IP, Bb ) (note that the blinded UProve token is contained in Bb ).
5. c = GenerateChallenge(IP, T , a, m, D, {xi }i∈D ),6. [Standard] Compute r0 = cα−1 + w0 , or
6. [Blinded](a) Compute r0 = cα−1 · l−1 + w0 ,(b) Compute s1 = r1 − c · k · b1 and s2 = r2 − c · k · b2
7. Compute ri = −cxi + wi for each i ∈ U , where wi is chosen randomly,
8. Return the U-Prove token proof ({Ai }i∈D , a, r0 , {ri }i∈U ).
8. [Blinded] Additionally, return s1 and s2 .
3.4

Verifying U-Prove Token

Input
1. Issuer parameter fields IP and if the token is blinded then additionally IP[Blinded] .
2. Ordered indices of disclosed attributes: D ⊂ {1, . . . , n},
3. Ordered indices of undisclosed attributes: U ⊂ {1, . . . , n} \ D,
4. The UProve token in form
– [Standard] T = (U IDP , h1 , T I, IP, σz0 , σc0 , σr0 ), or– [Blinded] T = (U IDP , T I, IP, Bb ).
5. The presentation proof ({Ai }i∈D , a, r0 , {ri }i∈U ),6. [Blinded] The proof of knowledge s1 , s2 .
Proof Verification:
1. [Standard] Run the V erif yT okenSignature(IP, T ) procedure which verifies(σz0 , σc0 , σr0 ) (see [8]), or
1. [Blinded] Run V erif ySelf BlindableCertif icate(Bb , T , s1 , s2 ).
2. xt = ComputeXt(IP, T I),
3. For each i ∈ D, xi = ComputeXi(IP, Ai ),4. Set c = GenerateChallenge(IP, T , a, m, D, {xi }i∈D ),5. [Standard] Extract k = h from T , or
5. [Blinded] Extract k = B1 from T ,Q
Q?
6. Verify that a = H((g0 gtxt i∈D gixi )−c k r0 ( i∈U giri )).

A Short Paper on How to Improve U-Prove Using Self-Blindable Certificates

3.5

7

Verify Self Blindable Certificate

Having as input the system parameters and the issuers parameters IP[Blinded] , the challenge c the blinded token T in particular the values B1 , B2 , B3 , B4 , B10 and B20 , checkthe following proof of knowledge:?

B1s1 B2s2 B3−c = B10 B20
Now, check whether the certificate was indeed issued by the issuer by verifying thefollowing equations:?

e(B3 , p0 ) = e(B4 , pr )

4

and

?

e(B1 , p1 ) = e(B2 , p)

Security Analysis

Since this is a work in progress, we only present an intuition for the security proof. In
particular, we show two things:
1. the adversary, without any U-Prove tokens, cannot create an U-Prove token thatpasses the verification,
2. having k U-Prove tokens, the adversary cannot forge a k + 1 U-Prove token which
is different then each of the k tokens he possesses and that will pass the verification.
3. having k tokens, the adversary cannot create an U-Prove token which is different
then each of the k tokens he possesses and that will pass the verification.
The first statement covers the case when the adversary, without any knowledge of UProve tokens in the system, would like to exploit the extension to pass the verification.
On the other hand, the second statement covers the case when the adversary would liketo exploit the extension to change some attributes in his U-Prove tokens.
Let us first assume that there exists an adversary that without access to any U-Provetoken, creates a U-Prove token that passes the verification. However, then we can use
such adversary to forge the underlying self-blindable certificates. Thus, since the selfblindable certificates presented in subsection 2.2 are secure against forgery, as shownin [9], so is our extension.
Now we show that the second statement is valid. Let for i ∈ {1, . . . , k}:
b

b

b

b

2,i
2,i z
(hi , h2,i , hi 1,i h2,i
, (hi 1,i h2,i) )be the U-Prove token extensions known to the adversary. Note that hi is the U-Prove tokens public key which contains all attributes. Without loss of generality we assume thatthe adversary would like to change some attributes in token i = 1. We will now showbb2,1
b2,1 z
how he can change the token (h1 , h2,1 , h11,1 h2,1
, (hi 1b1,1 h2,1
) ) and the contained in
it attributes, in such a way that it will pass the verification. Obviously, he can blind thistoken according to the protocol but then the token contains the same attributes. According to the security proof of the used self-blindable certificates (see appendix in
Q [9]) theadversary can only change h1 (the tokens public key) in such a way that h1 = i∈I hri i ,for I ⊂ {1, . . . , k} and ri are known to the adversary.

8

Lucjan Hanzlik and Kamil Kluczniak

Let us now assume that |I| = 2. It follows that h1 is of the form:
x0

x0

x0

x00

x00 x00(g0 g1 1 . . . gnn gt t g0 g1 1 . . . gnn gt t )αfor some key α, encodings x01 , . . . , x0n of attributes A1 , . . . , An and encodingsx001 , . . . , x00n of attributes A01 , . . . , A0n . However, a public key of such form will not pass
the standard U-Prove verification. The verifier checks whether:YY?
giri )).
a = H((g0 gtxt
gixi )−c k r0 (
i∈D

i∈U

Let us consider one disclosed attribute under base gj , j ∈ {1, . . . , n}. The adversary
can choose to disclose x0j or x00j . Without loss of generality, let the adversary disclose x00j .
x00

x00

Then, the value (gj j )−c will be canceled by the value (gj j )c , which will be computed
x0

x0

in k r0 . However, note that the value (gj j )c will also be computed, since (gj j ) is part ofthe public key k = h1 . Note further, that x0j cannot be part of the undisclosed attributes
since the verifier uses only bases gi for i ∈ U and j 6∈ U . It follows that the adversary
would have to know loggi (gj ) for a i ∈ U or find a collision for the hash function H(since c depends on the value of a).
The same argumentation works for |I| ∈ {3, . . . , k}. Thus, even if the adversary
has k tokens, he cannot create a new U-Prove token that contains a subset of attributes
from the k tokens he possesses.

5

Conclusion

We have shown, that it is possible to create an extension for the U-Prove credential
system that allows to randomize the token. This extension allows to use the token multiple times in such a way that the verifier cannot link two presentation proofs of thesame token. To assure, the validity of the token we use self-blindable certificates instead of blind signatures used in the standard specification. To give some intuition, forthe security of this construction, we give a brief rationale. Future work will include aformal security proof of our extension in the sense that this extension is as secure as thestandard U-Prove specification (which in fact has no formal security proof).

References
1. Chaum, D.: Security without identification: transaction systems to make big brother obsolete.
Commun. ACM 28(10) (October 1985) 1030–1044 1
2. Brickell, E., Camenisch, J., Chen, L.: Direct anonymous attestation. In: Proceedings of the
11th ACM conference on Computer and communications security. CCS ’04, New York, NY,
USA, ACM (2004) 132–145 2
3. Ateniese, G., Camenisch, J., Hohenberger, S., de Medeiros, B.: Practical group signatures
without random oracles. Cryptology ePrint Archive, Report 2005/385 (2005) http://
eprint.iacr.org/. 2

A Short Paper on How to Improve U-Prove Using Self-Blindable Certificates9

4. Bellare, M., Micciancio, D., Warinschi, B.: Foundations of group signatures: formal definitions, simplified requirements, and a construction based on general assumptions. In: Proceedings of the 22nd international conference on Theory and applications of cryptographic
techniques. EUROCRYPT’03, Berlin, Heidelberg, Springer-Verlag (2003) 614–629 2
5. Boneh, D., Boyen, X., Shacham, H.: Short group signatures. In: In proceedings of
CRYPTO’04, LNCS series, Springer-Verlag (2004) 41–55 2
6. Camenisch, J., Lysyanskaya, A.: A signature scheme with efficient protocols. In: Proceedings of the 3rd international conference on Security in communication networks. SCN’02,
Berlin, Heidelberg, Springer-Verlag (2003) 268–289 2
7. Camenisch, J., Van Herreweghen, E.: Design and implementation of the idemix anonymous
credential system. In: Proceedings of the 9th ACM conference on Computer and communications security. CCS ’02, New York, NY, USA, ACM (2002) 21–30 2
8. Paquin,C.,
Zaverucha,G.:
U-prove
cryptographic
specification
v1.1.
http://research.microsoft.com/pubs/166969/
U-ProveCryptographicSpecificationV1.1Revision2.pdf (April 2013) 2,
3, 4, 5, 6
9. Verheul, E.R.: Self-blindable credential certificates from the weil pairing. In Boyd, C., ed.:
ASIACRYPT. Volume 2248 of Lecture Notes in Computer Science., Springer (2001) 533–
551 2, 3, 4, 7
10. Okamoto, T.: Provably secure and practical identification schemes and corresponding signature schemes. In Brickell, E.F., ed.: CRYPTO. Volume 740 of Lecture Notes in Computer
Science., Springer (1992) 31–53 4