1 Introduction↩︎

Electronic identification schemes (eIDs) are essential for secure, efficient, and reliable digital interactions in both the public and private sectors. They enable individuals to authenticate themselves online, e.g., when accessing public e-government services, or private services like banking or healthcare, without relying on insecure methods like passwords. By providing a verified digital identity, eIDs help reduce fraud, identity theft, and cybercrime while ensuring compliance with data protection laws like the GDPR.

In this context, pseudonyms play a crucial role in enhancing privacy and data protection while enabling secure digital interactions. Instead of using a fixed personal identifier across all services, pseudonyms allow users to generate sector-specific or transaction-specific identifiers, ensuring that their real identity remains protected in different contexts. This approach aligns with the principles of GDPR, particularly data minimization and purpose limitation, by allowing only the necessary identity attributes to be shared on a need-to-know basis, and also helps prevent unwanted tracking and profiling, reducing the risk of mass surveillance or identity theft.

While many European countries have eID systems, not all of them implement sector-specific pseudonyms. Instead, national eID systems often use single identifier (e.g., the social security numbers) without the added complexity of domain-specific pseudonyms.

One of the first countries to introduce pseudonyms was Austria, where so-called “bereichsbezogene Personenkennzeichen” (bPk; sector-specific personal identifiers)¹ to enhance data privacy, security, and interoperability in digital identity management were already introduced in 2004 as part of the national e-Government Act.² These identifiers ensure that personal data is not universally traceable across different administrative or private sectors, reducing the risk of unauthorized profiling and misuse. By deriving unique identifiers per sector, ID Austria ensures that individuals can interact with government services, healthcare providers, and financial institutions without exposing a single, universal personal identifier.

In the following we briefly recap the functioning of the information flow on a logical level, cf. also [1] and 1. For more details on these flows, we also refer to 9. The actual authentication system starts with a registration phase. All Austrian citizens and new residents are automatically created by the central authority; this registration and participation are mandatory by law from first official registration (e.g., after birth or immigration) in Austria onward. When a user wishes to pseudonymously authenticate to a public service \(SP\) , the user leverages the national eID system to authenticate to a dedicated central public authority (“Stammzahlregisterbehörder”) upon request of the service provider. This authority derives the bPk from a locally stored and protected secret key created during the registration and sends it to the service provider . Furthermore, also in the absence of users, public authorities and governmental services may request the central authority to derive a bPk for a specific user, thereby relieving them from locally storing identity data in the plain to adhere to privacy-by-design principles. Additionally, the central authority is the only entity in the system which is able to link bPks across different domains, in case that multiple public authorities are involved in a transaction (e.g., municipality services and tax authorities), e.g., \(SP'\) can obtain an encrypted version of the bPk for \(SP''\) to enable \(SP''\) to assign the bPk to the current file . In case of abuse of pseudonymity, e.g., by filing false statements, or if necessary for other reasons (e.g., decease of a user), the central authority is also able to de-anonymize bPks. Finally, starting with \(2018\), bPks cannot just be used in communications with public authorities, but also with private companies. Overall, this caused more than \(2.5\) billion queries to the central authority annually [2].

Cryptographically, the computation of the bPk follows an encrypt-then-hash approach. That is, the central authority first encrypts the user’s resident registration number \(uid\) using a symmetric encryption scheme \(\mathsf{SymEnc}\) under a secret key \(sk\), and then hashes the result together with a public identifier of \(SP\), obtaining the bPk. That is, the bPk has the form \(\mathsf{Hash}(\mathsf{SymEnc}(sk,uid),SP)\) [3]. Specifically, this approach is instantiated using 3DES as symmetric encryption scheme, and SHA-1 as hash function³, while the supported domains are defined in a dedicated regulation⁴.

Looking at the existing solution, there are multiple questions to be addressed:

Availability.

The current architecture of the Austrian pseudonym system relies on a fully centralized architecture. Even if protected with state-of-the-art techniques, a denial of service attack, or also a non-malicious outage of the central authority cannot be excluded, resulting in immediate impacts on public authorities which no longer can obtain bPks. Furthermore, with the increasing use in the private sector, this impact also increasingly effects private service providers such as banks or private healthcare providers.

Privacy.

In the current architecture, the central authority is a fully trusted entity, without the user having the freedom to choose between different providers. While this is somewhat inherent due to its defined tasks and duties, it is also involved in any authentication session involving bPks, i.e., it learns who is authenticating to which service when and how often. While the authority acts within a tight legal corset to guarantee that the collected data is not misused, a malicious adversary obtaining (potentially read-only) access to this data can infer detailed identity profiles of millions of citizens.

Authenticity.

Overcoming the aforementioned challenges by simply distributing, e.g., \(\mathsf{SymcEnc}(sk,uid)\) to the individual users does not work in a straightforward manner, as was indeed done by the Austrian “Bürgerkarte” (citizen’s card) [4]. However, while \(sk\) remains protected at the central authority in this case and citizens may derive arbitrary bPks from this value, they could not prove to a service provider that the bPk is well-formed, i.e., a service provider could not distinguish a valid bPk for a given user from, e.g., a random bit string. This in turn allows users to authenticate under arbitrary bPks anytime they authenticate, which is especially critical for authentications to private companies, which do not have a legal basis to compare the correctness of the computation with the central authority. Thus, such authenticity guarantees are essential due to the potential legal implications bound to user authentication.

Provability.

Finally, while the specific way how bPks are currently computed intuitively seems to achieve all expected security guarantees, at least when modeling the hash function as a random oracle, it does not provide formal guarantees. Specifically, neither a rigorous definition of the required properties nor formal proofs have been published, in contradiction to the provable security paradigm for highly sensitive applications.

1.0.0.1 Our Contribution.

The goal of this work is thus to suggest bPk^#, a revised architecture and design, overcoming the above limitations without hindering the applicability of the proposed solution. It is worth noting that while our approach is inspired by a specific real-world system, the solution does not contain specificities, e.g., of the related eID system, such that it could be used also in the context of other countries.

More precisely, our contributions can be summarized as follows:

• In a first step, we derive the functional and non-functional requirements from the current design of the Austrian bPk system, including legal constraints from the Austrian e-Government law (e.g., related to mandatory key generation at the time of birth). We summarize the different capabilities that have to be offered by such a system, and for the first time formally define the non-functional, i.e., security- and privacy-related, requirements.

• We then provide a provably secure generic construction satisfying the security definitions. In contrast to the existing solution, our solution is fully distributed in the sense that the central authority is only involved in unavoidable cases, e.g., when pseudonyms need to be linked across different domains, or when a pseudonym has to be deanonymized. Nevertheless, despite being computed by the user, the service provider has formal authenticity guarantees that a real user has provided a well-formed pseudonym.

• In order to further reduce the dependability on the central authority, we further offer the possibility that also pre-defined service providers can compute pseudonyms for arbitrary users – yet only for their own scope. While this solves the impact, e.g., of an attack on the central authority, this might not be desirable for certain (e.g., private) service providers. Our construction thus naturally allows for a distinction between service providers who may, and others who may not, compute pseudonyms.

• Finally, we provide a concrete instantiation of our construction from standard building blocks such as digital signatures, zero-knowledge proofs, and non-interactive key exchange protocols. Going a step further, we instantiate our system with pairing-based building blocks and analyze its efficiency. Notably, on midrange hardware from 2022 the generation of a pseudonym including the proof of well-formedness takes less than \(5\) ms on average whereas verification of the proofs takes less than \(10\) ms.

1.0.0.2 Related Work.

There is a large body of work on privacy-preservation in eID systems. In the following we give a concise overview over some of the most closely related approaches found in the literature.

The evolution of the Austrian eID system including its integration into eGovernment services has seen discussion in the academic literature throughout the last two decades, e.g., [1], [5]–[9]. To the best of our knowledge, the specific requirements, design and the construction of bPks has not seen a formal treatment with an analysis in the framework for provable security.

For the German eID system [10], Dagdelen proposed a domain-specific pseudonymous signature scheme. In the German system, however, users are equipped with identity cards that store their secret key material. The generation of pseudonyms is done by running a non-interactive Diffie-Hellmann key exchange with a service provider public-key. In contrast, no proof is provided and thereby is affected by the same issues as the existing Austrian approach.

More generally, cryptographic pseudonym systems were introduced by Chaum [11], and later formalized and deployed in a series of work, including scope-exclusive pseudonyms, e.g., [12]–[15]. However, these concepts are focusing on user-centricity without the possibility for fine-grained delegation of the pseudonym computation to other entities.

Notably, Bringer et al. [16] use domain-specific pseudonyms in an eID context. In another series of work, Camenisch et al. [17], [18] introduced domain-specific pseudonym systems which allow a central authority to translate pseudonyms from one domain to another providing very high anonymity and transparency. While all being suitable candidates upon first glance, these schemes use models where keys are managed in a fully decentralized manner, thus being incompatible with the requirements of the Austrian legal framework.

Deswarte et al. [19] proposed a privacy-preserving national identity card system. However, their system was designed to prove attributes of a user in an unlinkable manner, and explicitly does not support pseudonyms. Furthermore, no rigorous security framework nor formal proofs are provided.

Finally, in general Self-Sovereign Identity (SSI) systems such as [20], [21], users are completely put in control of their secret keys and thus all actions in the system involve active participating of users. As discussed above, bPks need to be computable in specific cases due to the legal requirements of the Austrian eID system and thus SSI systems lack required functionality.

In summary, while a large body of relevant research exists, to the best of our knowledge none of these works covers all the details identified in our analysis of the Austrian bPk system, which inherently requires a central authority, yet also requires the need to delegate pseudonym computation to both users and service providers in a provably secure manner, to increase privacy, overcome efficiency challenges, and maximize availability and resilience.

1.0.0.3 Outline.

This document is structured as follows. 2 introduces the notation, and summarizes the necessary cryptographic background. In 3 we then introduce the modeling, including syntax and interfaces, but also functional and security requirements. We then present a generic construction from existing cryptographic building blocks, together with a rigorous security proof, in 4, before presenting a concrete instantiation and implementation in 5. In 6, we discuss the integration of revocation and key rotation in our construction. We finally conclude in 7.

2 Preliminaries↩︎

Readers familiar with the high-level concepts of public key encryption, digital signatures, non-interactive key exchange, and zero-knowledge proofs can safely skip this section upon first reading, and later come back for formal details, e.g., related to security proofs.

2.1 Notations↩︎

In this paper, we denote the security parameter as \(\lambda \in \mathbb{N}\) and \(1^\lambda\) as its unary representation.

An algorithm \({\mathcal{A}}\) is called Probabilistic Polynomial Time (PPT) if its running time is bounded by a polynomial \(P(|x|)\) for every input \(x\). Unless stated otherwise, all algorithms and adversaries considered in this paper are PPT.

Let \((\Omega,\mathcal{E}, \mathbb{P})\) be a probability space. We write \(\mathbb{P}[\Omega : \omega ]\) the probability of an event \(\omega \in \mathcal{E}\) in space \(\Omega\). A function \(\varepsilon : \mathbb{N} \rightarrow \mathbb{R}^+\) is said negligible if it vanishes faster than every reverse polynomial. More formally, if \(\forall k\in \mathbb{N}, \exists n_0 \in \mathbb{N} : \forall n > n_0, \varepsilon(n) \leq n^{-k}\).

For all cryptographic primitives used in this paper, we assume that the \(\mathsf{pk}\) can always be implicitly derived from the corresponding \(\mathsf{sk}\), i.e., knowing \(\mathsf{sk}\) enables at least implicit access to \(\mathsf{pk}\).

2.2 Cryptographic Building Blocks↩︎

In the following recap the basic definitions required for the building blocks used in our generic construction. For all the building blocks, we omit formal definitions of correctness, i.e., all schemes are supposed to function properly if all parties follow the protocol specifications.

2.2.1 Public Key Encryption↩︎

A public key encryption scheme is a cryptographic system that uses a publicly known key for encryption and a corresponding private key for decryption, enabling secure communication without prior key exchange.

The most fundamental security requirement for public key encryption requires that, only knowing the public key, it is computationally infeasible to decide which of two (adversarially chosen) plaintexts is encrypted in a ciphertext. For an in-depth discussion, we refer, e.g., to Katz and Lindell [22].

Definition 2 (IND-CPA). Let \({\Lambda}\) be a public-key encryption scheme. We define the IND-CPA experiment of \({\Lambda}\) by \(\mathrm{Exp}_{{\Lambda},{\mathcal{A}}}^{\mathrm{IND-CPA}}(\lambda)\) in 2. We say that \({\Lambda}\) is IND-CPA secure if there is a negligible function such that: \[\mathrm{Adv}_{{\Lambda},{\mathcal{A}}}^{\mathrm{IND-CPA}}(\lambda) \overset{\mathrm{def}}{=} \bigg|\:\mathbb{P}\left[ \mathrm{Exp}_{{\Lambda},{\mathcal{A}}}^{\mathrm{IND-CPA}}(\lambda) = 1 \right] - \frac{1}{2} \bigg| \leq \varepsilon(\lambda)\]

2.2.2 Digital signature↩︎

A digital signature ensures the authenticity, integrity, and non-repudiation of a message or document using a private signing key and a publicly verifiable signature.

There exist several unforgeability notions. For our construction, we require only a basic notion, which states that no adversary not knowing the secret key can create a valid signature on an arbitrary new message, even after having seen arbitrarily many signatures on messages of its choice. For an in-depth discussion, we refer, e.g., to Katz and Lindell [22].

2.2.3 Non-Interactive Zero-Knowledge Proof of Knowledge Systems↩︎

A zero-knowledge proof of knowledge is a cryptographic proof that allows a prover to convince a verifier that a statement is true without revealing any additional information beyond what is revealed by the message itself. If it only consists of a single message being sent from the prover to the verifier, it is called non-interactive (NIZK).

Formally, let \(\mathcal{L}\) be a NP-language associated with a relation \(R\) such that \(\mathcal{L}_R = \{x\;| \exists w : R(x,w) = 1\}\)

Firstly, it must not be possible to generate proofs for wrong statements.

Secondly, the verifier must not learn anything beyond the statement itself.

Furthermore, no adversary not knowing a valid witness should be able to convince the verifier with more than negligible probability. This is modeled by the existence of an extractor which can extract a valid witness from any adversary that is able to generate valid proofs. This should hold even if the adversary has previously seen simulated proofs on statements of its own choice.

For further discussions, we refer, e.g., to Goldwasser et al. [23] and Derler and Slamanig [24].

We adopt the Camenisch-Stadler framework [25] for representing proof goals. We write: \[\pi\gets\mathsf{NIZK}\left[(\alpha,\beta,\gamma):Y=G^\alpha\cdot H^\beta ~\land~ Z=G^\alpha\cdot H^\gamma ~\land~ \gamma=\alpha\cdot\beta\right]\] to denote a NIZK demonstrating knowledge of the values \(\alpha, \beta, \gamma\) that satisfy the relation on the right-hand side, where all values outside the parentheses are assumed to be public.

2.2.4 Non Interactive Key Exchange↩︎

A key exchange protocol allows two or more parties to securely establish a shared secret key over an insecure channel. A non-interactive key exchange (NIKE) protocol enables parties to compute a shared key without direct communication, typically using pre-exchanged public information. The first example of a NIKE scheme can be found in the seminal work Diffie and Hellman [26]. Our definition follows the work of Freire et al. [27], where we assume that the identities can implicitly be derived from the keys.

An important feature of NIKEs is that they are symmetric in the sense that two users, each knowing their own secret key and the other’s public key, will obtain the same shared key. That is, if \((sk_0,pk_0)\) and \((sk_1,pk_1)\) are the keys of two users, it always holds that \(\mathsf{ShareKey}(pk_1,sk_0)=\mathsf{ShareKey}(pk_0,sk_1)\). To satisfy this requirement, \(\mathsf{ShareKey}\) is usually designed as deterministic function, which we will also assume in the following.

We say that a NIKE is secure, if no adversary not knowing the corresponding secret keys can decide which secret key was used to compute a specific shared key, even if the adversary can choose the public key and request arbitrary shared keys before.

The following definition is targeted to our specific needs, and naturally satisfied by most existing constructions. In particular, in contrast to previous work [27], [28], we do not require any guarantees against rogue keys, as in our construction all public keys will be honestly generated, and thus only consider honestly generated keys in the experiment.

Definition 10 (Indistinguishability). A NIKE protocol \({\Psi}\) is said to be indistinguishable if for any PPT adversary \({\mathcal{A}}\), there is a negligible function \(\varepsilon\) such that: \[Adv^{IND-NIKE}_{{\Psi},{\mathcal{A}}}(\lambda) \overset{\mathrm{def}}{=} \bigg|\:\mathbb{P}\left[ \mathrm{Exp}_{{\Psi},{\mathcal{A}}}^{\mathrm{IND-NIKE}}(\lambda) = 1 \right] - \frac{1}{2} \bigg| \leq \varepsilon(\lambda)\] where \(\mathrm{Exp}_{{\Psi},{\mathcal{A}}}^{\mathrm{IND-NIKE}}\) is the experiment described in 4.

Finally, we additionally require that no two secret keys can result in the same public key. Note that this property is naturally satisfied by most constructions over cyclic groups.

For the definition, remember that a function \(f : X \rightarrow Y\) is said to be injective if \(f(x) = f(y)\) implies \(x = y\) for all \(x,y\in X\).

3 Framework for Delegatable Pseudonyms↩︎

In the following we now define a framework for delegatable pseudonym systems. We therefore briefly recap the core functionalities on an informal level, based on the Austrian bPk system. We then introduce the syntax for such systems, and finally provide formal and unambiguous definitions for the security properties of such schemes.

3.1 Requirements↩︎

A first set of functional requirements immediately follows from the responsibilities of the Austrian Stammzahlregisterbehörde as specified in the national eGovernment law:

Central authority pseudonym generation.

The central authority needs to be able to compute pseudonyms on behalf of all user from the first registration (e.g., birth or arrival in Austria) onward. It is not foreseen that users may opt out from the system.

Pseudonym linking.

The central authority needs to be able to “translate” pseudonyms for a specific user from one domain to another to allow inter-organization linking when required (subject to clear regulations).

De-anonymization.

In case of abuse of anonymity, the central authority has to be able to re-identify the user’s identity, without breaking the user’s privacy in other domains.

From a security and privacy point of view, the following requirements are guaranteed by the actual system.

Privacy/Anonymity.

Even colluding service providers shall not be able to decide by themselves whether two pseudonyms belong to the same user or not. That is, they should not be able to pool their information about a specific user, except for cases where the central authority previously translated pseudonyms from one domain to another.

Authenticity/Non-frameability.

Pseudonyms generated must be provably authentic, i.e., a malicious entity should not be able to compute pseudonyms for identities they do not own (or which do not exist at all). More precisely, even if a subset of users collude, they should not be able to issue a pseudonym that would be de-anonymized towards an identity not in this set of malicious users.

Finally, it is important to note that current system does not foresee the possibility to revoke a user or rotate keys.

While the current architecture as depicted in 1 satisfies all these (legally mandated) requirements, a system addressing the challenges mentioned in 1 additionally needs to satisfy requirements related to decentralization and increased metadata privacy:

User pseudonym generation

In addition to the central authority, honest users should be able to compute their pseudonyms entirely locally themselves, without prejudice to the verification of authenticity by the service provider.

SP pseudonym generation

Certain types of service providers (e.g., public agencies) may be able to also locally generate pseudonyms for arbitrary users, yet only within their own domain.

The latter requirement is optional but might be interesting in case of unavailability of the central authority. We are also aware that this requires careful and delicate balancing between privacy and availability, as corrupt service providers may compute arbitrary pseudonyms and share this information with other entities. We thus envision that service providers with this capability would be subject to legal regulations (e.g., public agencies), and also that their secret key is secured, e.g., within a hardware security module (HSM) precisely logging each pseudonym computation, such that the behavior can be audited, e.g., by data protection authorities.

The resulting high-level flows of our architecture are depicted in 5 and 9: Users can obtain their own key material from the central authority ( – ), while trusted service providers optionally obtain their own secret key . Using the public key of a SP , users can now locally compute verifiable pseudonyms for SP , while trusted SPs can fetch a user public key to locally compute the pseudonym . The authorities capabilities (e.g., linking pseudonyms or computing pseudonyms for less tech-savvy users) remain intact.

3.2 Syntax↩︎

For the initialization of the system, we require a global setup algorithm, defining common parameters, etc. This algorithm only needs to be executed once for the entire system. As usual, this algorithm is assumed to be carried out by a trusted party. To reduce the required trust into this party, in practice one might implement the algorithm as a multi-party protocol⁵, with the use of random oracles for constructions in the random oracle model, or similar. The resulting parameters are assumed to be input to all other algorithms, and will sometimes be omitted for notational convenience.

\(\mathsf{Setup}(1^\lambda) \to pp\)

is a probabilistic algorithm that, given security parameter \(1^\lambda\), outputs public parameters \(pp\) of underlying primitives used in the scheme.

The following algorithms are executed by the central authority. The first algorithm is only generated once, to establish a master key pair (corresponding, e.g., to the \(3DES\) key in the current bPk system). Subsequently, the central authority creates secret and public keys for all users and service providers. Note that in many other privacy-enhancing protocols such as group signatures [30], [31] or attribute-based credentials [13], the key generation happens on the user side. Centralizing it in our modeling was an active design decision. Firstly, pseudonyms must remain constant throughout life, making it difficult to make citizens responsible for backups of their secret key. Secondly, and more importantly, keys must be available from birth, and there is no legal opportunity to opt-out. Service provider keys are also generated by the authority, as only certain service providers (e.g., public authorities), should have access to the secret key at all, and if, it needs to be included, e.g., in secure hardware, cf. also 3.1:

\(\mathsf{KeyGen}(pp) \to ({msk}, {mpk})\)

is a probabilistic algorithm that, given public parameters \(pp\) as input, outputs the master secret key \({msk}\) and the master public key \({mpk}\).

\(\mathsf{KeyGen}_{user}({msk}) \to ({usk}, {upk})\)

is a probabilistic algorithm that, given the master secret key \({msk}\), outputs a pair of public and private keys \(({usk},{upk})\) for the user .

\(\mathsf{KeyGen}_{SP}({msk}) \to ({spsk}, {sppk})\)

is a probabilistic algorithm that, given the master secret key \({msk}\), outputs a pair of public and private keys \(({spsk}, {sppk})\) for the service provider.

Next, users need to be able to generate pseudonyms. To achieve authenticity, they additionally generate a proof showing the well-formedness of the pseudonym, i.e., proving that it was derived from a honest user secret key. This proof can then be verified by the service provider. If pseudonyms are computed by the service provider (for those that have access to the secret key corresponding to their public key), obviously no such proof is needed. To keep the model as light-weight as possible, we do not add an additional interface for pseudonym generation through the central authority, as it can simply leverage the service prover’s interface as well.

\(\mathsf{NymGen}_{user}({usk},{mpk},{sppk}) \to (\mathsf{nym},\pi)\)

is an algorithm that, given \({usk},{upk},{sppk}\) and \({mpk}\), outputs the user pseudonym \(\mathsf{nym}\) and validity proof \(\pi\).

\(\mathsf{NymVf}({mpk},{sppk},\mathsf{nym},\pi) \to 0/1\)

is a deterministic algorithm that, given the master public key \({msk}\), a service provider public key \({sppk}\), a pseudonym \(\mathsf{nym}\), a proof \(\pi\), outputs \(1\) or \(0\) whether \(\pi\) is valid for \(\mathsf{nym}\) or not.

\(\mathsf{NymGen}_{SP}({spsk},{mpk},{upk}) \to \mathsf{nym}\)

is a deterministic algorithm that, given the secret key of the service provider \({spsk}\) and the public key of the user \({upk}\), outputs the user pseudonym \(\mathsf{nym}\) specific to a service provider.

Finally, in case of abuse, the central authority has to be able to re-identify the user from a pseudonym and proof. Also, this allows the central authority to translate a pseudonym from one domain to another, by first opening a given pseudonym, and then computing the new pseudonym for a different domain for the same user.

\(\mathsf{Open}(\pi, {msk}) \to {upk}\)

is a deterministic algorithm that, given a proof \(\pi\) and the master secret key \({msk}\), outputs the user public key \({upk}\).

We want to remark that this final algorithm might in fact not be necessary for cross-domain linking if the approach currently used in the Austrian bPk system is followed. In that system, when a pseudonym for a given domain is known, the underlying user can only be identified either by brute-forcing all possible users or by consulting a lookup table containing all issued pseudonyms, since the pseudonym generation relies on a one-way function.

3.3 Security Framework↩︎

From a security point of view, we expect three main properties: completeness, saying that honest users can always authenticate; non-frameability, capturing that pseudonyms need to be verifiable and guarantee authenticity; and anonymity, saying that pseudonyms should not leak any information about a user’s identity, including especially also unlinkability.

We define these properties formally in the following.

3.3.1 Correctness↩︎

We omit a formal definition of correctness. Intuitively, it ensures that honest users will always be able to successfully present pseudonyms to honest service providers, and that the (trusted) central authority will always be able to link or re-identify honest users.

Furthermore, as illustrated in 6, service providers and users should always obtain the same pseudonym for a given user (i.e., knowing \({usk}\) and \({sppk}\) should result in the same \(\mathsf{nym}\) as starting from \({upk}\) and \({spsk}\)).

3.3.2 Non-Frameability↩︎

As discussed earlier, authenticity of user-generated pseudonyms is of high importance due to the potential legal implications of formal authentications. This property is captured by our notion of non-frameability, which ensures that an honest user cannot be falsely accused of having generated a pseudonym and corresponding proof. This should even hold if all other users collude, in which case they still cannot produce a valid pseudonym and proof that falsely implicates an innocent member. In contrast to the non-frameability notion, e.g., in group signatures [31], [32], the central authority must not collude, as our framework does contain secret key material solely held by the user (cf. the discussion in 3.2). Additionally, our notion also captures the basic unforgeability notion, which says that colluding users also cannot generate a valid pseudonym and proof which do not link to any existing user in the system.

In the experiment, \(\mathrm{N}\) denotes the set of queried pseudonyms. Let \(KP_u\) be the set of all created pairs of user public and private keys generated by the central authority. We also define the subsets \(\mathrm{PK_u}\) (resp. \(\mathrm{SK_u}\)) of \(KP_u\) as the set of honestly generated user public (resp. private) keys. Let \(\mathrm{PK_{sp}}\), \(\mathrm{SK_{sp}}\), and \(\mathrm{KP_{sp}}\) be the respective sets of service provider keys generated by the central authority. Finally, \(\mathrm{C_{u}}\) denotes the set of corrupted users.

In the security experiment, the adversary is given access to a number of oracles. Intuitively, upon the adversary’s request, \({\mathcal{O}}^{GenU}\) creates a new honest user, and hands the corresponding public key \({upk}\) to \({\mathcal{A}}\). Similarly, the adversary may request the creation of additional service providers through a call to \({\mathcal{O}}^{GenSP}\), again obtaining only the corresponding public key \({sppk}\). For any pair of users and service providers, the adversary may now request the corresponding user pseudonym, together with a proof of well-formedness, through \({\mathcal{O}}^{Nym}\); in case that the indicated service provider or user does not exist, the oracle returns \(\bot\). Finally, \({\mathcal{A}}\) can corrupt users, thereby obtaining the corresponding secret key \({usk}\), through \({\mathcal{O}}^{CorruptU}\).

We now formally define these oracles in [o:genu] [o:gensp] [o:nym] [o:corruptu]. Note that no oracle for corrupting service providers exists: as discussed earlier, untrusted service providers do not obtain their secret key, so that they are unable to generate pseudonyms by themselves. Trusted (e.g., publicly hosted) service providers should only receive their \({spsk}\) within secure hardware, such that key extraction is not possible, either.

3.3.3 Anonymity↩︎

In the following we now formalize the main privacy property of delegatable pseudonym systems. In a nutshell, the goal is that no adversary is able to decide significantly better than random guessing whether by which of two (adversarially chosen) users a specific pseudonym was created.

Informally, anonymity is modeled through a left-or-right (LoR) oracle, which the adversary can call to generate pseudonyms for arbitrary service providers, and which will always return the pseudonym either for the first or for the second input. The adversary wins if it can decide which is the case, under the following constraints: \((b)\) for the same service provider, the adversary must not query inconsistent inputs, e.g., \(({upk}_1,{upk}_2)\) and then \(({upk}_1,{upk}_3)\), as this would trivially allow the adversary to decide which output it receives; \((c)\) similarly, it must not request an honest pseudonym for a service provider that it also used in the LoR oracle, e.g., \(({upk}_1,{upk}_2)\) to LoR and also obtain a pseudonym for \({upk}_1\), as this trivially allows to guess the output it receives; \((d)\) it must not send \({upk}\)’s that it (previously or later on) corrupted to the LoR oracle, as again it could simply check for the output of the LoR oracle; and finally \((e)\) it must not request pseudonyms for corrupted service providers or pseudonyms. While the latter is clear similarly to \((d)\), it is rather an artifact from our proof strategy which however does not impose real limitations in practice, as we (as discussed before) assume that \({spsk}\) is never given to the adversary in the plain.

The definition of the experiment depends on two additional oracles beyond those used in the previous section. That is, \({\mathcal{O}}^{LoR}\) always returns the \(b^{\text{th}}\) pseudonym and proof for two inputs \(({upk},{upk}')\) for a given service provider. Finally, service providers can be corrupted through the \({\mathcal{O}}^{CorruptSP}\) oracle. We formally define these oracles in [o:lor] [o:corruptsp].

4 Construction↩︎

In the following we provide a blackbox construction from a set of cryptographic primitives as defined in 2 and provide rigorous proofs that it achieves non-frameability and anonymity. Therefore, let \({\Sigma}\) be a signature scheme, \({\Lambda}\) be an encryption scheme, \({\Psi}\) be a non-interactive key exchange protocol with secret key to public key injective property, and \({\Pi}\) be a non-interactive weakly simulation-sound proof system. Without loss of generality, we assume that the schemes are compatible in the sense that the message spaces of \({\Sigma}\) and \({\Lambda}\) include the public key space of \({\Psi}\).

The intuition of our construction is now as follows. The central authority generates the NIKE keys for all users and service providers, and pseudonyms are simply shared keys derived from the NIKE between a service provider and a user, which immediately yields commutativity, i.e., they will always obtain the same pseudonym.

In order to ensure that user-generated pseudonyms are authentic, the user does not only receive their secret key of the NIKE, but in addition a signature from the central authority on the public key. Now, when the user generates a pseudonym \(\mathsf{nym}\) they also compute a proof \(\pi\) that they used the service provider’s public key and a user secret key for which they also know a signature on the corresponding user public key.

Finally, to enable the central authority to trace users, the user in addition adds an encrypted version of their public key to the proof goal.

A detailed and formal specification of \({bPk\textsuperscript{\#}}_{{\Lambda},{\Sigma},{\Psi},{\Pi}}\) is given in Construction  [Framework].

We now obtain the following core results regarding the security of our generic construction.

Intuitively, to see non-frameability, note that an adversary would either have to break the proof-of-knowledge guarantees of the NIZK (to prove that it did a valid computation even though it did not) or forge a signature (in order to introduce a new, non-existing user to the system), yet both these cases are excluded by the guarantees of the building blocks. For the full proof, we refer to 8.1.

Anonymity basically follows from the fact that user prove their statements in zero-knowledge, and that the encryption of their identity does not leak information to a computationally bounded adversary either. Furthermore, the indistinguishability property of the NIKE guarantees that also known pseudonyms cannot be used to link users to fresh \({sppk}\)’s. For the full proof, we refer to 8.2.

5 Instantiation↩︎

In the following, we consider a pairing-based instantiation of our generic bPk^#construction with a concrete selection of compatible schemes.

5.1 Building Blocks↩︎

The main constraint for our construction is the choice of a signature scheme which can efficiently be combined with a NIZK to support the proof of knowledge of a valid signature from the central authority. We are inspired by the constructions of [33], [34] which are based on Groth’s structure-preserving signatures [35]. We only need to sign a single element in one of the source groups and thus give a presentation of the signature scheme adapted to our needs⁶:

• \(\mathsf{Groth}_1.\mathsf{Setup}(1^\lambda)\) generates public parameters of a bilinear group \((\mathbb{G}_1,\mathbb{G}_2,\mathbb{G}_T,e,p,G,\hat{G})\) of prime order \(p\), where \(G\in\mathbb{G}_1\) and \(\hat{G}\in\mathbb{G}_2\) are generators. It additionally outputs an element \(Y\gets_{\$}\mathbb{G}_1\).

• \(\mathsf{Groth}_1.\mathsf{KeyGen}()\) samples \(\mathsf{sk}\gets\mathbb{Z}_p^*\) and sets \(\mathsf{pk}\gets\hat{G}^\mathsf{sk}\).

• \(\mathsf{Groth}_1.\mathsf{Sign}(\mathsf{sk},\mathsf{msg})\) samples \(r\gets\mathbb{Z}_p^*\) and computes a signature \(\sigma=(\hat{R},S,T)=(\hat{G}^r,(Y\cdot G^\mathsf{sk})^{1/r},(Y^\mathsf{sk}\cdot\mathsf{msg})^{1/r})\).

• \(\mathsf{Groth}_1.\mathsf{Rand}(\sigma)\) rerandomizes a valid signature \(\sigma\) by sampling \(r'\gets\mathbb{Z}_p^*\) and outputting a randomized signature \(\sigma'=(\hat{R}',S',T')=(\hat{R}^{r'},S^{1/r'},T^{1/r'})\) on the same message.

• \(\mathsf{Groth}_1.\mathsf{Verify}(\mathsf{pk},\sigma,\mathsf{msg})\) outputs \(1\) if and only if it holds that \(e(S,\hat{R})=e(Y,\hat{G})\cdot e(G,\mathsf{pk})\) and \(e(T,\hat{R})=e(Y,\mathsf{pk})\cdot e(\mathsf{msg},\hat{G})\).

For the NIKE we need to also select schemes with public keys in \(\mathbb{G}_1\). Under the XDH assumption, note that we can instantiate the Diffie-Hellman [26] NIKE in \(\mathbb{G}_1\). Hence, we obtain the following NIKE:

• \(\mathsf{DH}.\mathsf{Setup}(1^\lambda)\) sets \(pp\) to \(\mathbb{G}_1\) and \(H \gets_{\$}\mathbb{G}_1\). Returns \(pp\).

• \(\mathsf{DH}.\mathsf{KeyGen}()\) samples \(\mathsf{sk}\gets_{\$}\mathbb{Z}_p^*\) and sets \(\mathsf{pk}\gets H^\mathsf{sk}\).

• \(\mathsf{DH}.\mathsf{ShareKey}(\mathsf{pk}', \mathsf{sk})\) computes \(\mathsf{shk}\gets \mathsf{pk}'^\mathsf{sk}\).

Similarly, under the XDH assumption, ElGamal encryption [36] provides a secure public-key encryption scheme in \(\mathbb{G}_1\) with message space \(\mathbb{G}_1\):

• \(\mathsf{ElGamal}.\mathsf{Setup}(1^\lambda)\) sets \(pp\) to \(\mathbb{G}_1\) and \(K \gets_{\$}\mathbb{G}_1\). Returns \(pp\).

• \(\mathsf{ElGamal}.\mathsf{KeyGen}()\) samples \(\mathsf{sk}\gets_{\$}\mathbb{Z}_p^*\) and sets \(\mathsf{pk}\gets K^\mathsf{sk}\).

• \(\mathsf{ElGamal}.\mathsf{Enc}(\mathsf{pk}, \mathsf{msg})\) computes \(r \gets_{\$}\mathbb{Z}_p^*\), return \((K^r, \mathsf{pk}^r \mathsf{msg})\).

• \(\mathsf{ElGamal}.\mathsf{Dec}(\mathsf{sk}, (c_1, c_2))\) returns \(c_2 c_1^{-\mathsf{sk}}\).

5.2 Protocol Specification↩︎

Putting the above building blocks into the generic construction presented in 4, we now obtain the concrete instantiation described in [const:concrete].

Note that the proof goal could be slightly simplified, by replacing \({upk}'^s\) by \(H^{{usk}'}\) in all equations, and removing the explicit term. By proving the relation \({upk}=\mu({usk}')\) implicitly, one can reduce the computational complexity of the proof goal by one discrete logarithm, and also reduce the communication complexity by removing \({upk}'\) from \(\pi\). However, we refrain from this slight optimization to allow for a direct mapping of the instantiation to our generic construction.

Note that Schnorr-style proofs made non-interactive using the Fiat-Shamir transform [37] induce a simulation-sound extractable NIZK provided that the underlying \(\Sigma\)-protocol provides quasi-unique responses [38] and the statement is used as part of the challenge generation [39]. As the statement is a conjunction of proofs of knowledge of discrete logarithms, the responses are quasi-unique. Alternatively, the proof system could also be instantiated with Groth-Sahai [40] to prove the pairing equations.

5.3 Efficiency Evaluation↩︎

The above pairing-based instantiation was implemented⁷ in Rust 1.85 using the BLS12-381 bilinear pairing via the ark-bls12-381 crate⁸. To demonstrate the efficiency of our construction, we have benchmarked the implementation on an Intel Core i7-1265U with 16 GB of RAM running Ubuntu 24.04. Since all algorithms except \(\mathsf{NymGen}\) and \(\mathsf{NymVf}\) consist of at most 3 efficient group operations, we present the results of \(\mathsf{NymGen}\) and \(\mathsf{NymVf}\) in 9 10. From the benchmark results we can observe that over 100 runs the runtime over \(\mathsf{NymGen}\) averages at \(4.94 \pm 0.02\) ms and \(\mathsf{NymVf}\) averages at \(7.61 \pm 0.03\) ms.

5.3.0.1 Implementation of Central Authority and Service Providers.

Note that for the central authority it is of paramount importance that its secret key is stored in an HSM. With our scheme, all operations that need to be performed by the central authority consist of group operations in either \(\mathbb{G}_1\) or \(\mathbb{G}_2\). Furthermore, observe that the secret key of \(\mathsf{Groth}_1\) is only applied to group elements in \(\mathbb{G}_1\). Hence, we can follow the same approach as in [41] which use existing implementations of RSA and elliptic curve groups to implement \(\mathbb{G}_1\) operations on a secure element whereas all operations in \(\mathbb{G}_2\) can be performed outside.

For a Service Provider having access to their secret key, the situation is even simpler. The only operation that needs to be performed in an HSM in this case is one group operation to generate \(\mathsf{nym}\). Hence, the same approach can be applied.

6 Key Rotation and Revocation↩︎

As discussed earlier, participation in the bPk system is mandatory by the Austrian eGovernment law, and thus no opt-out functionality is required and not provided. Also, no features for revocation or key rotation are foreseen in the current architecture, and similarly our decentralized design does not consider it either. However, following modern design paradigms, we next explain how to avoid impersonation attacks and how to achieve forward unlinkability in case of a key compromise by adding mechanisms for updating secret keys. In particular, we could additionally use time-dependent epoch and a stable user identifier in the user’s secret key secret. A detailed description of the proposed mechanisms and their implications is provided in 10.

7 Conclusion↩︎

In this paper, we have presented bPk^#, a user-centric delegatable pseudonym system preserving all required key functionalities of Austria’s governmental sector-specific personal identifier (bPk) concept. We presented the first formal modeling of such a functionality, and provided a generic construction together with a specific instantiation from standard building blocks. Our reference implementation underpins the practicability of our approach, resulting in runtimes below \(20\)ms for all operations on standard hardware.

7.0.0.1 Future Work.

As our scheme may potentially find applications also in other national eID systems beyond Austria, future proofing the deployment with post-quantum building blocks is of central interest. Our generic construction provides the framework to instantiate the scheme with post-quantum secure building block in a black-box manner, e.g., from lattice-based signatures, public-key encryption schemes and proof systems. While recent progress was made in this area, e.g., [42]–[45], selecting compatible proof systems and building blocks to obtain a practically efficient instantiation poses an interesting open problem.

An orthogonal interesting extension inspired, e.g., by [18], could also be to include transparency mechanisms, to allow users to track and audit all pseudonym computations that were carried out on their behalf by any of the other entities (CA or SPs) in the system.

Acknowledgements. This work was in part supported by the European Union’s Horizon Europe project licorice (grant agreement no. 101168311), prepared, a project funded by the Austrian security research programme KIRAS of the Federal Ministry of Finance (BMF), and the CHIST-ERA project reminder (grant number PCI2023-145989-2) through the Austrian Science Fund (FWF) project number I 6650-N. Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the funding agencies. Neither European Union nor the granting authorities can be held responsible for them

8 Security Proofs↩︎

In the following we now provide detailed formal proofs for our main security properties. We omit a proof of correctness, as this can trivially be verified based on the construction.

8.1 Non-frameability (1)↩︎

8.2 Anonymity (2)↩︎

9 Sequence Diagrams↩︎

In 15, we provide an overview of the logical flows of the current and envisioned phases in the Austrian bPk system.

Note that in both systems, the user key is generated when the user first registers in Austria; however, in the existing system, this key is never returned to the user. In a new key request step, citizens may obtain their keys after proper authentication using, e.g., the national eID system. In the standard authentication flow, the central authority is no longer involved in our new design; yet, while not depicted here, the legacy flow is functionally still supported, e.g., for less tech-savvy users which prefer a “bPk-as-a-service” setting. In both versions, service providers can further request the central authority to compute pseudonyms for specific users after providing proof of eligibility to obtain these pseudonyms. While this is a common flow in the current system (in particular by public agencies), this can now also be done locally by dedicated (i.e., semi-trusted) service providers, which can compute pseudonyms for users for their own scope, thereby further reducing the dependency on the central authority.

10 Rotation key and Revocation↩︎

The signature in the user’s secret key, i.e., \(\sigma \gets {\Sigma}.\mathsf{Sign}({upk},{msk}_{{\Sigma}})\), could be extended to \(\sigma \gets {\Sigma}.\mathsf{Sign}(({upk},\mathtt{uid},\mathtt{epoch}),{msk}_{{\Sigma}})\), where \(\mathtt{uid}\) is a stable user identifier attached to a user’s public key, and \(\mathtt{epoch}\) is a counter increasing on a regular basis. Upon authentication, users would now prove knowledge of a valid signature for the current \(\mathtt{epoch}\) without disclosing \(\mathtt{uid}\). In case that linking to previous periods is necessary, the user could additionally send the pseudonym from that previous period and show that they are both belonging to the same \(\texttt{uid}\) while keeping it private. Adapting the zero-knowledge proofs in our construction is straightforward at low costs. The computational costs will roughly double if a user needs to prove consistency with a previous pseudonym which only needs to done once per service.

When a user registers to a new service and needs to prove that it is the first registration, we would recommend to leverage the central authority to generate all previous pseudonyms of that user so that the service provider can check them against its existing database. While coming at the cost of a somewhat more active central authority, this approach relieves the user from having to store all their previous secret keys.

By ensuring that user secret keys are only stored within secure hardware elements and appropriate authentication mechanisms are employed, e.g., by requiring biometric authentication to request access – the latter being a standard requirement in many eID solutions – this approach enables key rotation at relatively low costs. However, if “on the spot” revocation of a user key is required, more sophisticated solutions need to be applied, leveraging from the broad literature on (issuer-side) revocation of attribute-based credential systems using very different approaches including, e.g., accumulators [46]–[48] or allow/deny lists [49]. There, the issuer typically maintains some public revocation information on all active (alternatively: revoked) credentials, and users upon authentication prove that their credential is currently valid (or not revoked) relative to this revocation information, without revealing any further information about their certificate. However, revocation of anonymous credentials often introduces substantial computational and procedural overheads, such that a clear risk assessment under the current legislation would be required.

References↩︎