Efficient and Strongly Secure Dynamic
Domain-Specific Pseudonymous Signatures for
ID Documents
Julien Bringer1 , Hervé Chabanne12 , Roch Lescuyer1 , and Alain Patey12
1Morpho, Issy-Les-Moulineaux, FranceTélécom ParisTech, Paris, France
Identity and Security Alliance (The Morpho and Télécom ParisTech Research Center){julien.bringer|herve.chabanne|roch.lescuyer|alain.patey}@morpho.com
2

Abstract. The notion of domain-specific pseudonymous signatures(DSPS) has recently been introduced for private authentication of ID
documents, like passports, that embed a chip with computational abilities. Thanks to this privacy-friendly primitive, the document authenticates to a service provider through a reader and the resulting signatures
are anonymous, linkable inside the service and unlinkable across services.
A subsequent work proposes to enhance security and privacy of DSPS
through group signatures techniques. In this paper, we improve on these
proposals in three ways. First, we spot several imprecisions in previous
formalizations. We consequently provide a clean security model for dynamic domain-specific pseudonymous signatures, where we correctly address the dynamic and adaptive case. Second, we note that using group
signatures is somehow an overkill for constructing DSPS, and we provide
an optimized construction that achieves the same strong level of security
while being more efficient. Finally, we study the implementation of our
protocol in a chip and show that our solution is well-suited for theselimited environments. In particular, we propose a secure protocol fordelegating the most demanding operations from the chip to the reader.
Keywords: ID documents, Privacy-enhancing cryptography, Domainspecific pseudonymous signatures.

1

Introduction

Authentication with ID documents. Recently, the German BSI agency introduced
several security mechanisms regarding the use of ID documents for authentication purposes [10]. In such situations, a Machine Readable Travel Document(MRTD) connects to a Service Provider (SP) through a reader (for concreteness, one might see the MRTD as a passport). The security mechanisms of [10]can be summarized as follows. First of all, during the PACE protocol (Password
Authenticated Connection Establishment), the MRTD and the reader establish
a secure channel. Then, during the EAC protocol (Extended Access Control ),the MRTD and the SP authenticate each other through another secure channel.

The reader transfers the exchanged messages. At last, during the (optional) RI
protocol (Restricted Identification), the MRTD gives its pseudonym for the service to the SP. This pseudonym enables the SP to link users inside its service.
However, across the services, users are still unlinkable. The latter property iscalled cross-domain anonymity. This property is interesting for many applications, since it offers at the same time privacy for the users and usability for theservice provider, who might not want to have fully anonymous users, but mightwant them to use an account to give them more personal services (e.g. bankaccounts, TV subscriptions, etc.).
For authentication purposes, giving pseudonyms is insufficient since the authenticity of the pseudonym is not guaranteed. For this reason, subsequent works[6, 5] adopt a “signature mode” for the RI protocol. This signature mode can be
described as follows.
1. The SP sends the MRTD the public key dpk of the service and a message m.
2. The MRTD computes a pseudonym nym as a deterministic function of its
secret key usk and the public key dpk.
3. The MRTD signs m with its secret key usk and the pseudonym nym.
4. The MRTD sends the signature σ and the pseudonym nym to the SP.
5. The SP checks the signature σ.
The contribution of [6] is to propose this signature mode and to present anefficient construction based on groups of prime order (without pairings). Their
construction relies on a very strong hypothesis regarding the tamperproofness of
the MRTD. In fact, recovering two users’ secrets enables to compute the key ofthe certification authority. To deal with this concern, the authors of [5] propose
to introduce group signatures into this signature mode. In addition to providing
strong privacy properties, group signatures provide collusion resistance even if
several users’ secrets do leak.
Our contributions. The authors of [5] claim that the security model of group
signatures directly gives a security model for DSPS, and, in fact, leave imprecise
the definition of the DSPS security properties. Moreover, the model of [6] only
concerns the static case, and their anonymity definition is flawed. So a security
model for dynamic DSPS as such has to be supplied. Our first contribution is thena clean security model for dynamic domain-specific pseudonymous signatures.
This first contribution highlights the fact that, in some sense, using group
signatures is “too strong” for constructing DSPS signatures. Following this intuition, we provide a new construction that is more efficient than the one of [5],while achieving the same strong security and privacy properties. Our second contribution is then an efficient proven secure dynamic DSPS with short signatures.
Finally, we concentrate on the use of our DSPS scheme in the RI protocol
for MRTD private authentication. Our construction is based on bilinear pairings, but, as a first advantage, no pairing computation is necessary during thesignature. However, we can go a step further, by taking advantage of the computational power of the reader. If some computations are delegated to the reader,then the chip only performs computation in a group of prime order. This is avaluable practical advantage since existing chips might be used. Otherwise, one
needs to deploy ad hoc chips, which has an industrial cost.
Related notions. As a privacy-preserving cryptographic primitive, a DSPS scheme
shares some properties with other primitives. We now discuss common points
and differences. DSPS schemes share some similarities with group signatureswith verifier local revocation (VLR) [9] in the sense that, in both primitives, therevocation is done on the verifier’s side. However, the anonymity properties are
not the same: group signatures are always unlinkable, whereas DSPS achievesome partial linkability. Moreover, one can establish a parallel with the notionof cross-unlinkable VLR group signatures [4], where users employ several group
signatures for several domains such that the signatures are unlinkable acrossdomains. Within a domain, the group signatures are however unlinkable, whichis too strong for the context of DSPS.
The difference between DSPS and pseudonym systems [14] or anonymous credential systems [11] is that DSPS-pseudonyms are deterministic whereas anonymous credentials pseudonyms must be unlinkable. In a DSPS scheme, the unlinkability is required across domains only, which is a weaker notion compared toanonymity in anonymous credentials. In fact, the anonymity of DSPS is a weaker
notion compared to the anonymity of group signatures, as noticed above, and(multi-show) anonymous credentials are often constructed through group signatures techniques [11].
A point of interest is to clarify the relation between pseudonymous signaturesand direct anonymous attestations (DAA) [2]. A DAA scheme might be seen (cf.
[7]) as a group signature where (i) the user is split between a TPM and a host,(ii) signatures are unlinkable but in specific cases and (iii) there is no opening
procedure. More precisely, the partial linkability is achieved by the notion of
basename, a particular token present in all signature processes. Two signatures
are linkable if, and only if, they are issued with the same basename.
At a first sight, a DSPS scheme is a DAA scheme where basenames are
replaced by pseudonyms, and where the underlying group signature is replaced
by a VLR group signature. The VLR group signatures introduce revocation
concerns that are away from DAA. Moreover, in the ID document use-case,
the MRTD/reader pair might be seen as the TPM/host pair of DAA scheme.
However, both primitives remain distinct. The choice of pseudonyms in DSPS
is more restrictive than the choice of the basename in DAA. Moreover, the hostalways embeds the same chip, but a MRTD is not linked to a specific reader,and might authenticate in front of several readers. Both differences impact theDSPS notion of anonymity.
Organization of the paper. In Section 2, we supply a security model for dynamic
domain-specific pseudonymous signatures, and discuss in details some tricky
points to formalize. Then in Section 3, we present our efficient constructionof dynamic DSPS, and prove it secure in the random oracle model. Finally in
Section 4, we discuss some implementation considerations and, among otherthings, analyse the possibility to delegate some parts of signature computationfrom the MRTD to the reader.

2

Definition and security properties of dynamic DSPS

A dynamic domain-specific pseudonymous signature scheme is given by an issuing authority IA, a set of users U, a set of domains D, and the functionalities {Setup, DomainKeyGen, Join, Issue, NymGen, Sign, Verify, DomainRevoke,
Revoke} as described below. By convention, users are enumerated here with indices i ∈ N and domains with indices j ∈ N.
Setup. On input a security parameter λ, this algorithm computes global parameters gpk and an issuing secret key isk. A message space M is specified. The sets U and D are initially empty. The global parameters gpk
are implicitly given to all algorithms, if not explicitly specified. We note
(gpk, isk) ← Setup(1λ ).
DomainKeyGen. On input the global parameters gpk and a domain j ∈ D, thisalgorithm outputs a public key dpkj for j. Together with the creation ofa public key, an empty revocation list RLj associated to this domain j iscreated. We note (dpkj , RLj ) ← DomainKeyGen(gpk, j).
Join ↔ Issue. This protocol involves a user i ∈ U and the issuing authority IA.
Join takes as input the global parameters gpk. Issue takes as input the
global parameters gpk and the issuing secret key isk. At the end of the
protocol, the user i gets a secret key uski and the issuing authority IA getsa revocation token rti . We note uski ← Join(gpk) ↔ Issue(gpk, isk) → rti .
NymGen. On input the global parameters gpk, a public key dpkj for a domainj ∈ D and a secret key uski of a user i ∈ U, this deterministic algorithm
outputs a pseudonym nymij for the user i usable in the domain j. We note
nymij ← NymGen(gpk, dpkj , uski ).
Sign. On input the global parameters gpk, a public key dpkj of a domain j ∈ D,a user secret key uski of a user i ∈ U, a pseudonym nymij for the user i andthe domain j and a message m ∈ M, this algorithm outputs a signature σ.
We note σ ← Sign(gpk, dpkj , uski , nymij , m).
Verify. On input the global parameters gpk, a public key dpkj of a domainj ∈ D, a pseudonym nymij , a message m ∈ M, a signature σ and therevocation list RLj of the domain j, this algorithm outputs a decision d ∈{accept, reject}. We note d ← Verify(gpk, dpkj , nymij , m, σ, RLj ).
DomainRevoke. On input the global parameters gpk, a public key dpkj of adomain j ∈ D, an auxiliary information auxj and the revocation list RLj of
the domain j, this algorithm outputs an updated revocation list RL0j . Wenote RL0j ← DomainRevoke(gpk, dpkj , auxj , RLj ).
Revoke. On input the global parameters gpk, a revocation token rti of a useri ∈ U and a list of domain public keys {dpkj }j∈D0 ⊆D , this algorithm outputs
a list of auxiliary information {auxj }j∈D0 ⊆D intended to the subset D0 ⊆ D
of domains. We note {auxj }j∈D0 ⊆D ← Revoke(gpk, rti , {dpkj }j∈D0 ⊆D ).

We consider the dynamic case where both users and domains may be added tothe system. Users might also be revoked. Moreover, the global revocation may
concern all the domains at a given point, or a subset of them. A global revocation protocol enabling to revoke the user i from every domain is implicit here: it
suffices to publish rti . Using rti and public parameters, anyone can revoke useri, even for domains that will be added later. Pseudonyms are deterministic. Thisimplies the existence of an implicit Link algorithm to link signatures inside a
specific domain. On input a domain public key dpk and two triples (nym, m, σ)and (nym0 , m0 , σ 0 ), this algorithm outputs 1 if nym = nym0 and outputs 0 otherwise. This also gives implicit procedures for the service providers to put the users
on a white list or a black list, without invoking the Revoke or DomainRevoke
algorithms: it suffices to publish the pseudonym of the concerned user.
Security definitions. To be secure, a DSPS scheme should satisfy the correctness, cross-domain anonymity, seclusiveness and unforgeability properties.
Informally, a DSPS scheme is (i) correct if honest and non-revoked users are
accepted (signature correctness) and if the revocation of honest users effectively
blacklists them (revocation correctness), (ii) cross-domain anonymous if signatures are unlinkable but within a specific domain, (iii) seclusive if it is impossible
to exhibit a valid signature without involving a single existing user, and (iv) unforgeable if corrupted authority and domains owners cannot sign on behalf ofan honest user. Let us now formalize each of these intuitions. The definition ofcorrectness does not make difficulties and is postponed to the full version [3].
Oracles and variables. We model algorithms as probabilistic polynomial Turingmachines (with internal states state and decisions dec). We formalize the security
properties as games between an adversary and a challenger. The adversary may
have access to some oracles that are given Figure 1. Moreover, games involvethe following global variables: D is a set of domains, HU of honest users, CU of
corrupted users and CH of inputs to the challenge. UU is the list of “uncertainty”(see the anonymity definition below) that is: the list, for each pseudonym, of theusers that might be linked to this pseudonym (in the adversary’s view). usk
records the users’ secret keys, rt the revocation tokens, nym the pseudonyms,
dpk the domain public keys, RL the revocation lists and Σ the signed messages.
Seclusiveness. Informally, a DSPS scheme achieves seclusiveness if, by similarity
with the traceability property of the group signatures, an adversary A is unable
to forge a valid signature that cannot “trace” to a valid user. In the group signature case, there is an opening algorithm, which enables to check if a valid user
produced a given signature. However, there is no opening here, so one might ask
how to define “tracing” users. Nevertheless, the management of the revocation
tokens allows to correctly phrase the gain condition, as in VLR group signatures [9], providing that we take into account the presence of the pseudonyms.
At the end of the game, we revoke all users on the domain supplied by theadversary. If the signature is still valid, then the adversary has won the game.
Indeed, in this case, the signature does not involve any existing user. (This is ananalogue of “the opener cannot conclude” in the group signature case).

SeclusivenessDSPS(λ)
A- (gpk, isk) ← DSPS.Setup(1λ ) ; D, HU, CU ← {}- O ← {AddDomain(·), AddUser(·), CorruptUser(·), UserSecretKey(·), Sign(·, ·, ·),ReadRegistrationTable(·), SendToIssuer(·, ·)}- (dpk∗ , nym∗ , m∗ , σ∗ ) ← AO (gpk)- Find j ∈ D such that dpk∗ := dpk[j]. If no match is found, then return 0.
- Return 1 if for all i ∈ U , either rt[i] = ⊥ or DSPS.Verify(gpk, dpk∗ , nym∗ , m∗ , σ∗ ,RL)= accept where RL := DSPS.DomainRevoke gpk, dpk∗ , aux, RL[j] and aux:= DSPS.Revoke(gpk, rt[i], {dpk∗ }).

A DSPS scheme achieves seclusiveness if the probability for a polynomial adversary A to win the SeclusivenessDSPS
game is negligible (as a function of λ).
A
Unforgeability. Informally, we want that a corrupted authority and corrupted
owners of the domains cannot sign on behalf of an honest user.
UnforgeabilityDSPS(λ)
A- (gpk, isk) ← DSPS.Setup(1λ ) ; D, HU, CU ← {}- O ← {AddDomain(·), WriteRegistrationTable(·, ·), Sign(·, ·, ·), SendToUser(·, ·)}- (dpk∗ , nym∗ , m∗ , σ∗ ) ← AO (gpk, isk)
- Return 1 if all the following statements hold.
- There exists j ∈ D such that dpk∗ = dpk[j]- There exists i ∈ HU such that nym∗ = nym[i][j], usk[i] 6= ⊥ and rt[i] 6= ⊥- m∗ 6∈ Σ[(i, j)]- DSPS.Verify(gpk, dpk∗ , nym∗ , m∗ , σ∗ , {}) = accept- DSPS.Verify(gpk, dpk∗ , nym∗ , m∗ , σ∗ , L) = reject where L := DomainRevoke(gpk,
dpk∗ , DSPS.Revoke(gpk, rt[i], {dpk∗ }), {})A DSPS scheme achieves unforgeability if the probability for a polynomial adgame is negligible (as a function of λ).
versary A to win the UnforgeabilityDSPS
A
Cross-domain anonymity. Informally, a DSPS scheme achieves cross-domain anonymity if an adversary is not able to link users across domains. We formalize
this intuition thanks to a left-or-right challenge oracle. Given two users i0 andi1 and two domains jA and jB , the challenger picks two bits bA , bB ∈ {0, 1} andreturns (nym0 , nym1 ) where nym0 is the pseudonym of ibA for the first domain
and nym1 the pseudonym of ibB for the second domain. The adversary wins if hecorrectly guesses the bit (bA == bB ), in other words if he correctly guesses that
underlying users are the same user or not. The Challenge oracle is called once.
(λ)
AnonymityDSPS
A$- (gpk, isk) ← DSPS.Setup(1λ ) ; D, HU, CU, CH ← {} ; bA , bB ← {0, 1}- O ← {AddDomain(·), AddUser(·), CorruptUser(·), UserSecretKey(·), Revoke(·, ·),DomainRevoke(·, ·), Nym(·, ·), NymDomain(·), NymSign(·, ·, ·), SendToIssuer(·, ·),Challenge(bA , bB , ·, ·, ·, ·)}- b0 ← AO (gpk)- Return 1 if b0 == (bA == bB ), and return 0 otherwise.

AddUser(i)AddDomain(j)- if j ∈ D, then abort- if i ∈ HU ∪ CU , then abort- RL[j] := {} ; All[j] := copy(HU )- HU := HU ∪ {i}- dpk[j] ← DomainKeyGen(gpk, j)- run usk ← Join(gpk) ↔ Issue(gpk, isk) → rt
- ∀i ∈ HU ,- usk[i] := usk ; rt[i] := rt- Σ[(i, j)] := {} ; UU[(i, j)] := &(All[j])- ∀j ∈ D,- nym[i][j] ← NymGen(gpk, dpk[j], usk[i])- Σ[(i, j)] := {} ; All[j] := All[j] ∪ {i}- return dpk[j]- nym[i][j] ← NymGen(gpk, dpk[j], usk[i])CorruptUser(i)- UU[(i, j)] := &(All[j])- if i ∈ HU ∪ CU , then abort
UserSecretKey(i)- CU := CU ∪ {i}- if i 6∈ HU or ∃j ∈ D, s.t. (i, j) ∈ CH, abort- usk[i] := ⊥ ; nym[i] := ⊥ ; rt[i] := ⊥- HU := HU \ {i} ; CU := CU ∪ {i}- dec[IA][i] := cont ; state[IA][i] := (gpk, isk)
- ∀j ∈ D,
Nym(i, j)- UU[(i, j)] := {i} ; All[j] := All[j] \ {i}- if i 6∈ HU or j 6∈ D or (i, j) ∈ CH, abort- ∀i0 ∈ HU , if UU[(i0 , j)] 6= &(All[j]),- UU[(i, j)] := {i} ; All[j] := All[j] \ {i}then UU[(i0 , j)] := UU[(i0 , j)] \ {i}- ∀i0 ∈ HU \ {i}, if UU[(i0 , j)] 6= &(All[j]),- return (usk[i], nym[i])then UU[(i0 , j)] := UU[(i0 , j)] \ {i}Revoke(i, D 0 )- return nym[i][j]- ∀j ∈ D 0 , call DomainRevoke(i, j)
NymDomain(j)- return {RL[j]}j∈D0- if j 6∈ D, then abort
DomainRevoke(i, j)- result := random perm(copy(All[j]))- if i 6∈ HU or j 6∈ D or (i, j) ∈ CH, then abort- ∀i ∈ HU ,- aux ← Revoke(gpk, rt[i], {dpk[j]})- if UU[(i, j)] == &(All[j]),- RL[j] ← DomainRevoke(dpk[j], aux, RL[j])- UU[(i, j)] := copy(All[j])- UU[(i, j)] := {i} ; All[j] := All[j] \ {i}- All[j] := {} ; return nym[i][j] i∈result- ∀i0 ∈ HU \ {i}, if UU[(i0 , j)] 6= &(All[j]),then UU[(i0 , j)] := UU[(i0 , j)] \ {i}Sign(i, j, m)- return RL[j]- if i 6∈ HU or j 6∈ D, then abort
NymSign(nym, j, m)- Σ[(i, j)] := Σ[(i, j)] ∪ {m}- if j 6∈ D, then abort- return Sign(dpk[j], usk[i], nym[i][j], m)- find i ∈ HU such that nym[i][j] == nym
ReadRegistrationTable(i)if no match is found, then abort- return rt[i]- Σ[(i, j)] := Σ[(i, j)] ∪ {m}WriteRegistrationTable(i, M )- return Sign(gpk, dpk[j], usk[i], nym[i][j], m)- rt[i] := M
SendToUser(i, Min )- if i ∈ CU , then abort ; if i 6∈ HU , then
HU := HU ∪ {i} ; Min := ε ; usk[i] := ⊥ ; state[i][IA] := gpk ; dec[i][IA] := cont- (state[i][IA], Mout , dec[i][IA]) ← Join(state[i][IA], Min , dec[i][IA])- if dec[i][IA] == accept, then usk[i] := state[i][IA]- return (Mout , dec[i][IA])SendToIssuer(i, Min )- if i 6∈ CU , then abort- (state[IA][i], Mout , dec[IA][i]) ← DSPS.Issue(state[IA][i], Min , dec[IA][i])- if dec[IA][i] == accept, then set rt[i] := state[IA][i]- return (Mout , dec[IA][i])Challenge(bA , bB , jA , jB , i0 , i1 )- if i0 6∈ HU or i1 6∈ HU or i0 == i1 or jA 6∈ D or jB 6∈ D or jA == jB , then abort- if ∀j ∈ {jA , jB }, ∃i ∈ {i0 , i1 } such that {i0 , i1 } 6⊆ UU[(i, j)], then abort- CH := {(i0 , jA ), (i0 , jB ), (i1 , jA ), (i1 , jB )} ; return (nym[ibA ][jA ], nym[ibB ][jB ])Fig. 1. Oracles provided to adversaries

A DSPS scheme achieves cross-domain anonymity if the probability for a polynomial adversary A to win the AnonymityDSPS
game is negligible34 .
A
3

The SendToIssuer oracle might be surprising here. But, contrary to group signatures, the issuing authority IA is not corrupted. This assumption is minimal since
the IA may trace all honest users. Hence we must give the adversary the ability tointeract as a corrupted user with the honest issuer.
4
Our model takes into account the case where pseudonyms leak from the network. To
this aim, the NymDomain oracle gives the adversary a collection of pseudonyms.

Discussion about anonymity. We want to catch the intuition of being anonymous across domains, so we propose that the adversary supplies two domainsof its choice, and aims at breaking anonymity across these domains. Moreover,
the Challenge oracle, in our model, does not output two signatures, but two
pseudonyms belonging to the different domains. The adversary’s goal is to guess
if those pseudonyms belong to the same user or not. To obtain signatures, theadversary may call a NymSign oracle. The adversary does not directly supply auser, but a pseudonym and obtains a signature on behalf of the underlying user.
If the adversary A wants a signature from a particular user, A asks for this user’s
pseudonym and then asks the NymSign oracle for a signature.
Since the functionality is dynamic, there might be no anonymity at all if
we do not take care of the formalization. For instance, an adversary might ask
for adding two domains, two users, i0 , i1 , ask for their pseudonyms throughtwo calls to NymDomain, add a user i2 and win a challenge involving i0 , i2 with
non-negligible probability. This attack does not work here, since the All list is
emptied after each NymDomain call.
To correctly address the cross-domain anonymity definition, we introduce
a notion of “uncertainty” in the oracles. The challenger maintains, for each
pseudonym, a list of the possible users the pseudonym might be linked to from theadversary’s point of view. These lists evolve in function of the adversary’s queries.
Thus, the challenger ensures that the pseudonyms returned by the Challenge
oracle contain enough uncertainty for at least one domain. Note that the uncertainty is required for only one domain. A user queried to the Challenge might
be known or revoked in a domain: the adversary has to guess whether the otherpseudonym belongs to the same user.
Comparison to previous security models. First, the model of [6] is static: all users
and domains are created at the beginning of the games, while our security games
are all dynamic. Second, let us focus on the cross-domain anonymity and showthat their definition is flawed. The adversary is given all pseudonyms and all
domain parameters. The left-or-right challenge takes as input two pseudonyms
for the same domain and a message and outputs a signature on this message by
one of the corresponding users. A simple strategy to win the game, independentlyof the construction, is to verify this signature using both pseudonyms: it will
be valid for only one of them. This observation motivates our choice for ourchallenge output to be a pair of pseudonyms and not a pair of signatures, since
it is easy to verify correctness using pseudonyms. Moreover, in their game, both
pseudonyms queried to the challenge oracle are in the same domain, which does
not fit the cross-domain anonymity, while our challenge involving two different
domains does. Third, the model of [6] does not allow for collusions: the adversary
can be given at most one user secret key (indeed, with their construction, using
two users’ secret keys, one can recover the issuing keys)5 .
The model of [5] is largely inspired by the security model of VLR group
signatures. That is why it does not enough take into account the specificities of
DSPS. The challenge of the cross-domain anonymity game also considers a single
5

For sake of clarity, note that (nymi , dsnymij ) in [6] maps to (i, nymij ) in our model.

domain and outputs a signature (but it does not take as input the pseudonymsof the users, only identifiers, so it does not inherit the security flaw of [6]).
The model also lacks from a precise description of the oracles, thus leaving
looseness on what are the exact inputs and outputs. Our model is more precise
and separated from the model of group signatures, which leads, as we will see inthe following, to a more efficient construction.

3

An efficient construction of dynamic DSPSIn this section, we present an efficient construction of dynamic DSPS we callthe D scheme and prove it secure in the sense of the previous Section in the
random oracle model. Our construction makes use of bilinear pairings. A bilinear
environment is given by a tuple (p, G1 , G2 , GT , e) where p is a prime number,
G1 , G2 and GT are three groups of order p (in multiplicative notation) and e
is a bilinear and non-degenerate application e : G1 × G2 → GT . The propertyof bilinearity states that for all g ∈ G1 , h ∈ G2 , a, b ∈ Zp , we have e(g a , hb ) =e(g, h)ab = e(g b , ha ). The property of non-degeneracy states that for all g ∈ G1 \{1G1 }, h ∈ G2 \ {1G2 }, e(g, h) 6= 1GT . Bilinear environments may be symmetricif G1 = G2 or asymmetric if G1 6= G2 . Let us now describe our scheme.
Setup(1λ )1. Generate an asymmetric bilinear environment (p, G1 , G2 , GT , e)$$
2. Pick generators g1 , h ← G1 \ {1G1 } and g2 ← G2 \ {1G2 }γ
3. Pick γ ∈ Zp ; Set w := g2
4. Choose a hash function H : {0, 1}∗ → {0, 1}λ
5. Return gpk := (p, G1 , G2 , GT , e, g1 , h, g2 , w, H) ; isk := γDomainKeyGen(gpk, j)$
1. Pick r ← Z∗p ; Set RLj ← {} ;Return dpkj := g1 r ; RLj

Join(gpk) ↔ Issue(gpk, isk)
0$
1. [i] Pick f 0 ← Zp ; Set F 0 := hf
2. [i] Compute Π := PoK{C = Ext-Commit(f 0 )∧NIZKPEqDL(f 0 , C, F 0 , h)}6
3. [U → IA] Send F, Π[IA] Check Π
 1
00
00
4. [IA] Pick x, f ∈ Zp ; Set F := F 0 · hf ; A := g1 · F γ+x ; Z := e(A, g2 )5. [U ← IA] Send f 00 , A, x, Z?
6. [i] Set f := f 0 + f 00 ; Check e(A, g2 x · w) = e(g1 · hf , g2 )The user gets uski := (f, A, x, Z) ; The issuer gets rti := (F, x)
NymGen(gpk, dpkj , uski )1. Parse uski as (fi , Ai , xi , Zi ) ;6

Return nymij := hfi · (dpkj )xi

Ext-Commit is an extractable commitment scheme (a perfectly binding computationally hiding commitment scheme where an extraction key allows to extract thecommitted value). NIZKPEqDL(f, C, F, h) is a Non Interactive Zero Knowledge Proofof Equality of the Discrete Logarithm f of F w.r.t h with the value committed in C.

The Sign procedure is obtained by applying the Fiat-Shamir heuristic [13] toa proof of knowledge of a valid user’s certificate (we explicitly give this proofof knowledge in Appendix A.1). More precisely, a signer proves knowledge of 1(f, (A, x)) such that A = g1 · hf γ+x and nym = hf · dpkx .
Sign(gpk, dpk, usk, nym, m)
1. Parse usk as (f, A, x, Z)$
2. Pick a, ra , rf , rx , rb , rd ← Zp ; Set T := A · harxrf
3. Set R1 := h · dpk ; R2 := nymra · h−rd · dpk−rb
4. Set R3 := Z rx · e(h, g2 )a·rx −rf −rb · e(h, w)−ra
5. Compute c := H(dpkknymkT kR1 kR2 kR3 km)
6. Set sf := rf + c · f ; sx := rx + c · x ; sa := ra + c · a ; sb := rb + c · a · x ;sd := rd + c · a · f
7. Return σ := (T, c, sf , sx , sa , sb , sd )Verify(gpk, dpk, nym, m, σ, RL)
1. If nym ∈ RL, then return reject and abort.
2. Parse σ as (T, c, sf , sx , sa , sb , sd )3. Set R10 := hsf · dpksx · nym−c ; R20 := nymsa · h−sd · dpk−sb−c
4. Set R30 := e(T, g2 )sx · e(h, g2 )−sf −sb · e(h, w)−sa · e(g1 , g2 ) · e(T, w)−1
5. Compute c0 := H(dpkknymkT kR10 kR20 kR30 km)
6. Return accept if c = c0 , otherwise return reject.
Revoke(gpk, rti , D0 )1. Parse rti as (Fi , xi ) ;Return {auxj := Fi · (dpkj )xi }j∈D0

DomainRevoke(gpk, dpkj , auxj , RLj )7
1. Return RLj := RLj ∪ {auxj }We now sketch a proof of the following theorem. A full proof can be found in [3].
Theorem 1. The D scheme achieves seclusiveness, unforgeability and crossdomain anonymity in the sense of Section 2 in the random oracle model under
the DL, q-SDH and DDH assumptions.
$

Discrete Logarithm DL. Let G be a cyclic group of prime order p. Given (g, h) ←G2 , find x ∈ N such that g x = h.
Decisional Diffie-Hellman DDH. Let p be a prime number, G be a cyclic group$of order p and a, b, c ← Zp . Given g := (g, A, B, C) ∈ G4 , decide whether g =(g, g a , g b , g a+b ) or g = (g, g a , g b , g c ).
q-Strong Diffie-Hellman q −SDH. Let (p, G1 , G2 , GT , e) be a bilinear environment,
2
q
$
$
$
h1 ← G1 , h2 ← G2 and θ ← Zp . Given (h1 , h1 θ , h1 θ , . . . , h1 θ , h2 , h2 θ ) ∈ Gq+1×1
G22 , find a pair (c, g1 1/(θ+c) ) ∈ Zp \ {−θ} × G1 .
7

A revocation list is a set of revoked pseudonyms. Given a (pseudonym, signature)pair, the revocation test is a simple membership test. In practice, this can be donevery efficiently.

We first show that, under a chosen-message attack, in the random oracle model, it
is computationally impossible to produce a valid D signature σ := (T, c, sf , sx , sa ,sb , sd ) without the knowledge of a valid certificate (f, A, x, Z). In other words,
from a valid signature, we can extract a valid certificate. This “extraction step” isstandard when signature schemes are built by applying the Fiat-Shamir heuristic[13] to a given Σ-protocol (cf. [16, 15, 12]).
Proof of seclusiveness. In the random oracle model, the D scheme achievesseclusiveness in the sense of Section 2 if the SDH problem is hard. Let (h1 , h1 θ ,2qh1 θ , . . . , h1 θ , h2 , h2 θ ) ∈ Gq+1
×G22 be a SDH instance on a bilinear environment1(p, G1 , G2 , GT , e). We build an algorithm B that outputs (c, g1 1/(θ+c) ), for ac ∈ Zp \ {−θ}, from an adversary A against the seclusiveness of our scheme.
$$

Parameters. B picks k ← [1, q], x1 , . . . , xq , s1 , . . . , sq ← Zp , computes g2 := h2 ,−w := (h2 θ ) · h2 −xk . For {x1 , . .Q
. , xq } ∈ Fp , define polynomials
QqP , Pm and Pm forqm ∈ [1, q] on Fp [X] by P := n=1 (X + xn − xk ), Pm := n=1,n6=m (X + xn −Qq−xk ), Pm:= n=1,n6=m,n6=k (X + xn − xk ). Expanding P on θ, we get P (θ) =
Pq
q
θn
n
from
n=0 an θ for some {an }n=0 depending on the xn . Since B knows h1
the q-SDH challenge, B is able to compute h1 P (θ) without the knowledge of θ.
$$B picks α ← Zp , β ← Z∗p , sets g1 := h1 β(αP (θ)−sk Pk (θ)) , h := h1 βPk (θ) and gives(e, G1 , G2 , GT , e, g1 , h, g2 , w, H) to A.
Simulating the issuing algorithm. Let Aux be the following sub-routine, taking as input (f 0 , ctr) ∈ Zp × N and outputting (f 00 , A, x, Z) as in the fourth
step of the D.Issue algorithm. ctr is a counter for the queries. B sets Actr :=−h1 β(αPctr (θ)+Pctr (θ)(sctr −sk )) and returns (sctr − f 0 , Actr , xctr , e(Actr , g2 )).
Simulating the oracles. A counter is set ctr := 0. When A asks for adding a new$honest user, B sets ctr := ctr+1, picks f 0 ← Zp , calls the Aux procedure on input
00
00, Actr , xctr , Zctr ), Actr , xctr , Zctr ), records usk[ctr] := (f 0 + fctr
(f 0 , ctr), gets (fctr00
f 0 +fctr
and rt[ctr] := (h, xctr ). When A interacts with the issuer as a corrupted
0
user, B sets ctr := ctr + 1 and extracts f 0 such that F := hf thanks to theextraction key ek. B then calls the Aux procedure on the input (f 0 , ctr), and00, Actr , fctr , Zctr ) back, which B transfers to A. B records usk[ctr] :=gets (fctr
0
00
0
00
(f + fctr , Actr , xctr , Zctr ) and rt[ctr] := (hf +fctr , xctr ).
Response. A eventually outputs (dpk∗ , nym∗ , m∗ , σ∗ ). If this is a non trivial response, then there exists j ∈ D such that dpk∗ = dpk[j]. At this point, B blacklists all users near j, by updating RL[j]. For all i ∈ U, we have (i) usk[i] 6= ⊥and (ii) rt[i] 6= ⊥. If the response is valid, then Verify(gpk, dpk∗ , nym∗ , m, σ,
RL[j])= accept. This means that B can extract a new certificate (f∗ , A∗ , x∗ , Z∗ )in reasonable expecting time.
Solving the SDH challenge. Since from (ii) for all i ∈ U, rt[i] 6= ⊥, then, if
the signature is not rejected, then there is no n ∈ [1, q], such that nym∗ =hfn · (dpk∗ )xn . Hence (iii) (f∗ , x∗ ) 6∈ {(f1 , x1 ), . . . , (fq , xq )}. We have two cases.
(A) x∗ ∈ {x1 , . . . , xq }. (A.I) If x∗ 6= xk , B returns ⊥ and aborts. (A.II) Let
us now assume that x∗ = xk . We have f∗ 6= sk (since f∗ = sk contradicts (iii))

11

and (A∗ sk · Ak −f∗ ) sk −f∗ = h1 β(αP (θ)−sk Pk (θ)) θ . By dividing
Qq β(αP (θ) − sk Pk (θ))
by θ we get R and Q such that C := R(0) = −βsk n=1,n6=k (xn − x∗ ) and1

C(A∗ sk · Ak −f∗ ) sk −f∗ = h1 θ +Q(θ) where C 6= 0. B computes h1 1/θ := ((A∗ sk ·1
Ak −f∗ ) sk −f∗ · h1 −Q(θ) )1/C , sets c := 0 and returns (0, h1 1/θ ).
(B) x∗ 6∈ {x1 , . . . , xq }. In particular, we have (iv) xn −x∗ 6= 0 for all n ∈ [1, q].
Let us now consider the quantity βPk (θ)(αθ + f∗ − sk ) as a polynomial D in θ.
If we carry out the Euclidean division of D by (θ + x∗ − xk ), we get Q and R
such that D(θ) = (θ + x∗ − xk )Q(θ) + R(θ). As (θ + x∗ − xk ) is a first degree
polynomial X − (xk − x∗ ), we hknow that R(θ) = D(xi k − x∗ ), so B can compute
Qq
C := R(θ) = D(xk − x∗ ) = β
n=1,n6=k (xn − x∗ ) (α(xk − x∗ ) + f∗ − sk ). We
Q(θ)+

C

θ+x∗ −xkhave A∗ = h1
. B can compute h1 Q(θ) from the SDH challenge.
(B.I) (f∗ − sk ) 6= α(x∗ − xk ). In this case, C 6= 0 by (iv) and by the choice of11β, so B can compute g1 θ+x∗ −xk = A∗ · g1 −Q(θ) C , set c = x∗ − xk , and return(c, g1 1/(θ+c) ). (B.II) (f∗ − sk ) = α(x∗ − xk ). B returns ⊥ and aborts.
In [3] we show that A outputs a valid forgery with probability , then B
solves the SDH challenge with probability at least /2q.
tu

Proof of unforgeability. In the random oracle model, the D scheme achieves
unforgeability in the sense of the Section 2 if the DL problem is hard. Let A be
an adversary against the unforgeability of the D scheme. Let (p, G1 , G2 , GT , e)be a bilinear environment and (g, H) be a discrete logarithm instance in G1 . We
construct an algorithm B that computes θ := logg H.
$$$

Parameters. B picks g1 ← G1 , g2 ← G2 , γ ← Zp , sets h := g and w := g2 γ .
B gives parameters gpk := (e, G1 , G2 , GT , e, g1 , h, g2 , w) to A. B picks a random
user i ∈ [1, qU ]. In addition, B generates parameters for the extractable commitment scheme Ext-Commit and the non-interactive proof system NIZKPEqDL.
Simulating the oracles. At each time B interacts (as an honest user) with A (asthe corrupted issuing authority), B follows the Join procedure, but for the i-thuser. In the latter case, B sets F 0 := H, simulates Π and gets (fi00 , Ai , xi , Zi )100where Ai = (g1 · H · hfi ) xi +γ for some fi00 . B does not know fi , but can compute00
nymij := H · hfi · dpkj xi for all j ∈ D. When A asks for a signature, B simulatesa signature for i, other signatures are normally computed.
Response. A play of A gives a valid and non trivial (dpk∗ , nym∗ , m∗ , σ∗ ). Then(i) we can find a domain j such that dpk∗ = dpk[j] and an honest user iwith consistent values nymij ∈ nym[i][j], (Fi , xi ) ∈ rt[i] and (∗, Ai , xi , Zi ) ∈usk[i] such that nym∗ = nymij = Fi · (dpk∗ )xi , and (ii) we are able to extract
a valid certificate (f∗ , A∗ , x∗ , Z∗ ) where, in particular, nym∗ = hf∗ · (dpk∗ )x∗ .
Since discrete representations in G1 are unique modulo p, then we have thatf∗ = logg Fi (the pseudonym must be valid in a non trivial forgery) and x∗ = xi .
With probability |U1 | we have i = i, since i is independent of the view of A.
This implies that Ai = A∗ (a value A is determined by f , x and γ). Thus1
100
A∗ = (g1 · g f∗ ) x∗ +γ = (g1 · H · hfi ) x∗ +γ and we obtain θ = f∗ − fi00 .
tuProof of anonymity. The D scheme achieves anonymity in the sense of Section 2
if the DDH problem is hard in G1 . Let qU be the number of queries to AddUser
and SendToIssuer and qD to AddDomain. Let A be an -adversary against theunforgeability of the D scheme. Let (p, G1 , G2 , GT , e) be a bilinear environmentand (g, A, B, C) a Diffie-Hellman instance in G1 . We construct B that decides
whether C is the Diffie-Hellman of A and B w.r.t. g.
Parameters. The parameters gpk := (p, G1 , G2 , GT , e, g1 , h, g2 , w) for the D scheme are computed honestly, knowing isk = γ, except that g1 := g. B picks two$$$
bits bA , bB ← {0, 1}, a random user i ← [1, qU ] and a random domain j ← [1, qD ].
Simulating the oracles. Since the challenger knows the issuing secret key, andmoreover can simulate signatures on behalf of any user, then the simulation of
the oracles is done without noticeable facts, except that B acts as if dpkj = B
and xi = logg A. B aborts and returns a random bit if the user i is queried to
UserSecretKey (B has no valid uski ) or if nymij is not returned by Challenge.
The reduction relies upon the following procedure for simulating pseudonyms.
SimNym(i, j).
(I) i 6= i and j 6= j: B gets (fi , xi ), (dpkj , rj ) and sets nymij := hfi · g1 rj xi .
(II) i = i and j 6= j: B gets fi , (dpkj , rj ) and sets nymij := hfi · Arj .
(III) i 6= i and j = j: B gets (fi , xi ) and sets nymij := hfi · Bxi .
(IV) i = i and j = j: B gets fi and sets nymij := hfi · C.
Response. Eventually, A outputs a bit b0 , its guess for (bA == bB ). B returns
true if (b0 == (bA == bB )), or false otherwise, as response to its own challenge.
Let us now estimate the advantage that B has of solving the DDH challenge.
AdvDDH
B = Pr[B ⇒ true|C = DHg (A, B)] − Pr[B ⇒ true|C is random]= Pr[abort] · P1 + Pr[abort] · P2 − Pr[abort] · P3 − Pr[abort] · P4

where P1 := Pr[B ⇒ true|abort ∧ C = DHg (A, B)], P2 := Pr[B ⇒ true|abort ∧C = DHg (A, B)], P3 := Pr[B ⇒ true|abort ∧ C is random] and P4 := Pr[B ⇒true|abort ∧ C is random]. Due to the lack of space, we only give a bound andpostpone its analysis to the full version of our paper [3]. We obtain:
1
+1
1
1
+ Pr[abort] ·− Pr[abort] · − Pr[abort] ·
2 
2
2
2
 

qS · (qH + qS )

qC
≥
· 1−
· 1−
(qU − qC ) · qD
qU
p4

AdvDDH
B = Pr[abort] ·where qC , qS and qH are the number of queries to (resp.) UserSecretKey, Sign
and H.
tu

MRTD(gpk, usk)
Reader(gpk)
SP(gpk, dpk)$x
nym := h · dpk ; a, ra , rf , rx , rb , rd ← Zp
B1 := Arx · ha·rx −rf −rb ; B2 := h−ra
B1 , B 2−−−−−−−−−−−−−−−−−→
R3 := e(B1 , g2 ) · e(B2 , w)
R3←−−−−−−−−−−−−−−−−−
T := A · ha ; R1 := hrf · dpkrx
R2 := nymra · h−rd · dpk−rb
compute c, sf , . . . , sd as previouslyfFig. 2. Delegation of computation from the MRTD to the reader

4

Implementation considerations

Signature size. A signature σ := (T, c, sf , sx , sa , sb , sd ) is composed of 1 elementin G1 , a challenge of size λ and five scalars, which is particularly short for thislevel of security. By comparison, a signature of [5] is of the form (B, J, K, T, c,sf , sx , sa , sb ) ∈ G1 4 × {0, 1}λ × Zp 4 . The short group signature of [12] lies in∈ G1 4 × {0, 1}λ × Zp 4 as well, which highlights the fact that we do not need thewhole power of group signatures here.
Pre-computations and delegation of computation. In the D scheme, the issuer
computes the element Z := e(A, g2 ) and adds it to the user secret key. Thanks
to this pre-computation, the user avoids to compute any pairing. In the signatureprocedure, the user only computes (multi)-exponentiations in G1 and GT . This isan advantage if we consider that the user is a smart-card, as in the ID documentuse-case.
But we can go a step further by delegating some computation from the card
to the reader. The MRTD interacts with the SP through the reader but, in the
RI protocol, even in signature mode, the reader just transfers the messages. In
our case however, we take advantage of the computational power of the reader.
A proposal for this kind of delegation is given Figure 2. We obtain a piece of
valuable advantages since there is no need to implement large groups operations(like operations in GT ) in the MRTD. As a consequence, we do not need todevelop specific chips for achieving those heavy computations, and existing chips
can be used. We implemented our protocol on a PC. Following first estimationsof a partial implementation on a chip, the overall signature and communication(including delegation) between the reader and the passport cost around 890ms,
for equipment currently in use.
Security of the delegation. Of course, this delegation of computation must be
done without compromising the security. In the DAA analysis of [7], a DAA
scheme (with distinct host and TPM) is built upon a pre-DAA scheme (where
TPM and host are not separated). However, our analysis differs, because theMRTD is not linked to a single reader. Therefore we adapt our model. We
add a pair of successive oracles (with a lock mechanism between their calls):
GetPreComp(i, j, m), enabling a corrupted reader to obtain pre-computations
from an honest user, and Sign0 (i, j, D), where the same user produces a signature
given a delegated computation D supplied by the adversary. Formal definition
are given in [3].
Now, in the seclusiveness game, users are corrupted and try to cheat with
the issuer and the verifier. We can assume that readers are corrupted, so theadversary might call GetPreComp and Sign0 to interact with honest users. In theunforgeability game, we can also assume that the reader is corrupted and add thetwo oracles above. Regarding the anonymity, in our use case, the reader is able
to read the data on the ID document, so there is no anonymity in front of thereader (for the concerned domain/user), as there is no anonymity of the TPM
from the host’s point of view in a DAA scheme. However, we still want a notionof unlinkability across domains. Even if a reader is corrupted, the same user
must remain anonymous in other domains, which is exactly our DSPS notion ofanonymity. So the adversary might call GetPreComp and Sign0 , and we restrict
the Challenge query to involve at most one user for which the adversary called
GetPreComp (before and after the Challenge call).
Finally, we adapt our proofs. First, in the anonymity proof, the challenger
honestly computes signatures for all users, but i, for which signatures are simulated. Then, we must show that, in each game, the challenger can simulate B1 ,B2 and σ (a proof of this fact is given in Appendix A.2). In our construction,
the adversary can compute A from B2 and σ. The fact that we can simulatesignatures even in the cross-domain anonymity game shows that the knowledgeof A does not help linking users across domains.

5

Conclusion

In this paper, we supplied a clean security model for dynamic domain-specificpseudonymous signatures, and compared this notion with other privacy-friendly
cryptographic primitives. We then highlighted the fact that, in some sense, usinggroup signatures is “too strong” for constructing DSPS signatures. Following thisintuition, we provided a new construction that is more efficient than the oneof [5], while achieving the same strong security and privacy properties. Finally,
we concentrated on the use of our DSPS scheme in the RI protocol for MRTD
private authentication. Our construction might be implemented on existing chips
if one takes advantage of the computational power of the reader. We suppliedan analysis of such a delegation of computation.
Acknowledgements. The authors would like to thanks the anonymous reviewers for their valuable comments. This work has been partially funded by theEuropean FP7 FIDELITY project (SEC-2011-284862). The opinions expressedin this document only represent the authors’ view. They reflect neither the viewof the European Commission nor the view of their employer.

References
1. Dan Boneh, Xavier Boyen, Short signatures without random oracles, the SDH
assumption in bilinear groups, J. of Crypt., 21(2), pp. 149-177, 2008.
2. Ernest Brickell, Jan Camenisch, Liqun Chen, Direct anonymous attestation,
CCS’04, pp. 132-145, ACM, 2004.
3. Julien Bringer, Hervé Chabanne, Roch Lescuyer, Alain Patey, Efficient andstrongly secure dynamic domain-specific pseudonymous signatures for ID documents, Full version available at http://eprint.iacr.org/2014/067.
4. Julien Bringer, Hervé Chabanne, Alain Patey, Cross-unlinkable hierarchicalgroup signatures, EuroPKI 2012, LNCS 7868, pp. 161-177, Springer, 2013.
5. Julien Bringer, Hervé Chabanne, Alain Patey, Collusion-resistant domain-specific pseudonymous signatures, NSS’13, LNCS 7873, pp. 649-655, Springer, 2013.
6. Jens Bender, Özgür Dagdelen, Marc Fischlin, Dennis Kügler, Domain-specificpseudonymous signatures for the German identity card, ISC’12, LNCS 7483,
pp. 104-119, Springer, 2012.
7. David Bernhard, Georg Fuchsbauer, Essam Ghadafi, Nigel Smart, Bogdan
Warinschi, Anonymous attestation with user-controlled linkability, Int. J. Inf.
Sec., 12(3), pp. 219-249, 2013.
8. Paulo Barreto, Michael Naehrig, Pairing-friendly elliptic curves of prime order,
SAC’05, LNCS 3897, pp. 319-331, Springer, 2006.
9. Dan Boneh, Hovav Shacham, Group signatures with verifier-local revocation,
CCS’04, pp. 168-177, ACM, 2004.
10. Bundesamt für Sicherheit in der Informationstechnik (BSI), Advanced Security
Mechanisms for Machine Readable Travel Documents, Part 2 – Extended AccessControl Version 2 (EACv2), Password Authenticated Connection Establishment(PACE),, Restricted Identification (RI), TR-03110-2, March 2012.
11. Jan Camenisch, Anna Lysyanskaya, Signature schemes, anonymous credentials
from bilinear maps, CRYPTO’04, LNCS 3152, pp. 56-72, Springer, 2004.
12. Cécile Delerablée, David Pointcheval, Dynamic fully anonymous short group
signatures, VIETCRYPT’06, LNCS 4341, pp. 193-210, Springer, 2006.
13. Amos Fiat, Adi Shamir, How to prove yourself: practical solutions to identification, signature problems, CRYPTO’86, LNCS 263, pp. 186-194, Springer, 1987.
14. Anna Lysyanskaya, Ronald Rivest, Amit Sahai, Stefan Wolf, Pseudonym systems, SAC’99, LNCS 1758, pp. 184-199, Springer, 2000.
15. David Pointcheval, Jacques Stern, Security arguments for digital signatures,
blind signatures, J. of Crypt., 13(3), pp. 361-396, 2000.
16. Claus-Peter Schnorr, Efficient identification, signatures for smart cards, CRYPTO’89, LNCS 435, pp. 239-252, Springer, 1989.

A

Appendix

A.1

A proof of knowledge of a valid certificate

Let P be the protocol Figure 3 for proving knowledge of (f, (A, x)) such that 1
A = g1 · hf γ+x and nym = hf · dpkx . In [3], we show that (i) for an honest
verifier, the transcripts T , (R1 , R2 , R3 ), c, (sf , sx , sa , sb , sd ) can be simulated
in an indistinguishable way, without knowing any valid certificate, and that(ii) there exists an extractor for the protocol P.

Parameters. (p, G1 , G2 , GT , e), g1 , h ∈ G1 , g2 ∈ G2 .
Issuer. isk := γ ∈ Zp , ipk := w := g2 γ . Domain. r ∈ Zp , dpk := g1 r 6= 1G1 .
 1User. usk := (f, A, x, Z), f, x ∈ Zp , A := g1 · hf γ+x ∈ G1 , Z := e(A, g2 ) ∈ GT .
$nym := hf · dpkx ; a ← Zp ; T := A · ha$r f , r x , r a , r b , r d ← Zp
rfrx
R1 := h · dpk ; R2 := nymra · h−rd · dpk−rb
R3 := Z rx · e(h, g2 )a·rx −rf −rb · e(h, w)−raR1 , R2 , R3−→$c ← {0, 1}λc←−sf ← rf + c · f ; sx ← rx + c · x ; sa ← ra + c · asb ← rb + c · a · x ; sd ← rd + c · a · f
sf , sx , sa , sb , sd−→?

hsf · dpksx = R1 · nymc?

nymsa · h−sd · dpk−sb = R2c?
e(T, g2 )sx · e(h, g2 )−sf −sb · e(h, w)−sa = R3 · e(g1 , g2 ) · e(T, w)−1

Fig. 3. The P protocol

A.2

Simulation of signatures with delegated computation

We now adapt the proofs of our main scheme to the extended model of Section 4.
We first simulate the GetPreComp step. In the seclusiveness proof, all signatures
are honestly computed. In the unforgeability proof, if i 6= i, then all signatures
are honestly computed. If i = i, then, given H (from the DL challenge), Ai , xi
00$
and fi00 , B picks a, c, sf , sx , sa , sb ← Zp and computes B1 := (Ai −xi · H · hfi )c ·Asx · ha·sx −sf −sb and B2 := ha·c−sa . In the cross-domain anonymity proof, thechallenger honestly computes signatures for all users, but i, for which signatures$are simulated. Given A (from the DDH challenge) and fi , B picks α ← Zp .
The same α is used in each signature, for consistency. Then, for each signaturequery, B picks fresh values a, c, sf , sx , sa , sb and computes B1 := (A−α · hfi )c ·T sx · h−sf −sb and B2 := ha·c−sa . (The simulation is done as if Ai := g1 α .)We now simulate the Sign0 oracle (identically in the three proofs). B retrievesm, B1 , B2 , c, sa , sx , sa , sb from the GetPreComp step. Whatever D is (D may not$equal e(B1 , g2 ) · e(B2 , w)), B picks sd ← Zp , computes T , R1 and R2 as usualand sets c as the random oracle’s value for the input dpkknymkT kR1 kR2 kDkm.
If D is correct w.r.t. B1 and B2 , then B returns a valid signature. If not, thenthe signature is no longer valid but the response remains consistent w.r.t. B1and B2 .
tu