This paper was published in the Proceedings of the ACM Asia Conference on Computer and Communications Security (ASIA CCS ’26), June 1–5, 2026, Bangalore, India. https://doi.org/10.1145/3779208.3785289
bPk#: Delegatable Pseudonyms
arXiv:2605.30212v1 [cs.CR] 28 May 2026
And Their Applications to National eID Systems Stephan Krenn
Doryan Lesaignoux
Sebastian Ramacher
AIT Austrian Institute of Technology
AIT Austrian Institute of Technology
AIT Austrian Institute of Technology
Vienna, Austria
Vienna, Austria
Vienna, Austria
Abstract Electronic identities (eIDs) are crucial in an increasingly digitalized environment. Pseudonyms, as offered by Austria’s governmental sector-specific personal identifiers (bPks), can significantly improve privacy by ensuring that personal data is not universally traceable across public services and private companies. However, the current architecture comes with several challenges regarding availability, privacy, and authenticity, due to a fully centralized design. This paper proposes bPk# , a distributed architecture to address these issues, reducing reliance on the central authority, while still providing all functional requirements to the existing bPk system. In particular, users are delegated the rights to compute their own pseudonyms, thereby minimizing metadata revealed to the central authority, while (subsets of) service providers may receive the right to compute pseudonyms only within their own domain, thereby reducing the availability needs of the central authority. To the best of our knowledge, we provide the first formal framework for such delegatable pseudonym systems, together with a generic construction for which we provide formal security proofs. Furthermore, we propose a concrete instantiation of our construction, together with a reference implementation demonstrating the practical efficiency.
Keywords national eID system, sector-specific pseudonyms, provable security
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 transactionspecific 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)1 to enhance data privacy, security, and interoperability in digital identity management were already introduced in 2004 as part of the national e-Government Act.2 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 [42] and Figure 1. For more details on these flows, we also refer to Appendix B. 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 𝑆𝑃 1 , the user leverages the national eID system 2 to authenticate to a dedicated central public authority (“Stammzahlregisterbehörder”) 3 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 4 . 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 privacyby-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., 𝑆𝑃 ′ can obtain an encrypted version of the bPk for 𝑆𝑃 ′′ to enable 1 https://www.bundeskanzleramt.gv.at/agenda/digitalisierung/
stammzahlenregisterbehoerde/bereichsspezifische-personenkennzeichen/ beschreibung.html 2 https://ris.bka.gv.at/GeltendeFassung.wxe?Abfrage=Bundesnormen& Gesetzesnummer=20003230
Stephan Krenn, Doryan Lesaignoux, and Sebastian Ramacher
2
eID
3 5
Central authority 1
SP
SP' SP''
4
Figure 1: Logical information flow in the current bPk architecture 𝑆𝑃 ′′ to assign the bPk to the current file 5 . 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 [44]. Cryptographically, the computation of the bPk follows an encryptthen-hash approach. That is, the central authority first encrypts the user’s resident registration number 𝑢𝑖𝑑 using a symmetric encryption scheme SymEnc under a secret key 𝑠𝑘, and then hashes the result together with a public identifier of 𝑆𝑃, obtaining the bPk. That is, the bPk has the form Hash(SymEnc(𝑠𝑘, 𝑢𝑖𝑑), 𝑆𝑃) [1]. Specifically, this approach is instantiated using 3DES as symmetric encryption scheme, and SHA-1 as hash function3 , while the supported domains are defined in a dedicated regulation4 . 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., SymcEnc(𝑠𝑘, 𝑢𝑖𝑑) to the individual 3 https://www.bundeskanzleramt.gv.at/agenda/digitalisierung/
stammzahlenregisterbehoerde/veroeffentlichungen.html 4 https://www.ris.bka.gv.at/GeltendeFassung.wxe?Abfrage=Bundesnormen&
Gesetzesnummer=20003476
users does not work in a straightforward manner, as was indeed done by the Austrian “Bürgerkarte” (citizen’s card) [46]. However, while 𝑠𝑘 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. 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 realworld 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 eGovernment 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 predefined 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
bPk# : Delegatable Pseudonyms
distinction between service providers who may, and others who may not, compute pseudonyms.
due to the legal requirements of the Austrian eID system and thus SSI systems lack required functionality.
• 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.
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.
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., [42, 43, 45, 47–49]. 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 [21], Dagdelen proposed a domainspecific 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 [19], and later formalized and deployed in a series of work, including scope-exclusive pseudonyms, e.g., [12, 17, 37, 41]. 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. [9] use domain-specific pseudonyms in an eID context. In another series of work, Camenisch et al. [13, 14] 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.
Outline. This document is structured as follows. Section 2 introduces the notation, and summarizes the necessary cryptographic background. In Section 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 Section 4, before presenting a concrete instantiation and implementation in Section 5. In Section 6, we discuss the integration of revocation and key rotation in our construction. We finally conclude in Section 7.
2
Preliminaries
Readers familiar with the high-level concepts of public key encryption, digital signatures, non-interactive key exchange, and zeroknowledge 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 𝜆 ∈ N and 1𝜆 as its unary representation. An algorithm A is called Probabilistic Polynomial Time (PPT) if its running time is bounded by a polynomial 𝑃 (|𝑥 |) for every input 𝑥. Unless stated otherwise, all algorithms and adversaries considered in this paper are PPT. Let (Ω, E, P) be a probability space. We write P[Ω : 𝜔] the probability of an event 𝜔 ∈ E in space Ω. A function 𝜀 : N → R+ is said negligible if it vanishes faster than every reverse polynomial. More formally, if ∀𝑘 ∈ N, ∃𝑛 0 ∈ N : ∀𝑛 > 𝑛 0, 𝜀 (𝑛) ≤ 𝑛 −𝑘 . For all cryptographic primitives used in this paper, we assume that the pk can always be implicitly derived from the corresponding sk, i.e., knowing sk enables at least implicit access to pk.
2.2
Cryptographic Building Blocks
Deswarte et al. [23] 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.
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.
Finally, in general Self-Sovereign Identity (SSI) systems such as [2, 39], 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
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.
Stephan Krenn, Doryan Lesaignoux, and Sebastian Ramacher
Definition 2.1 (Public-Key Encryption scheme). A public-key encryption scheme Λ is a tuple of four PPT algorithms (Setup, KeyGen, Enc, Dec) such that: • Setup(1𝜆 ) → 𝑝𝑝: This algorithm takes a security parameter 𝜆 and outputs public parameters 𝑝𝑝. • KeyGen(𝑝𝑝) → (sk, pk): This algorithm takes public parameters 𝑝𝑝 and outputs a secret and public key (sk, pk). • Enc(pk, 𝑚) → 𝑐: This algorithm takes a public key pk and a message 𝑚 and outputs a ciphertext 𝑐. • Dec(sk, 𝑐) → 𝑚 ∗ : This algorithm takes a secret key sk and a ciphertext 𝑐 and outputs a message 𝑚 ∗ . 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 [33]. Definition 2.2 (IND-CPA). Let Λ be a public-key encryption scheme. We define the IND-CPA experiment of Λ by ExpIND−CPA (𝜆) Λ,A in Experiment 1. We say that Λ is IND-CPA secure if there is a negligible function such that: h i 1 def IND−CPA AdvIND−CPA (𝜆) = P ExpΛ,A (𝜆) = 1 − ≤ 𝜀 (𝜆) Λ,A 2
Experiment 1 − ExpIND−CPA (𝜆) Λ,A (sk, pk) ← KeyGen(𝑝𝑝)
3: 𝑚 0 , 𝑚 1 ← A (𝑝𝑝, pk) $ 4: 𝑏 ← {0, 1} 5: 𝑐 ∗ = Enc(pk, 𝑚𝑏 ) 6: 𝑏 ∗ ← A (𝑝𝑝, pk, 𝑐 ∗ ) 7: if 𝑏 ∗ = 𝑏 then return 1
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 [33]. Definition 2.4 (EUF-CMA). Let Σ be a signature scheme. Σ achieves existential unforgeability under chosen-message attacks (EUF-CMA) if: 𝑝𝑝 ← Setup(1𝜆 ) Verify(pk, 𝜎 ∗, 𝑚 ∗ )) = 1 (sk, pk) ← KeyGen(·) P : ≤ 𝜀 (𝜆) 𝑚 ∗ ∉ Q Sign (𝑚 ∗, 𝜎 ∗ ) ← A O Sign (pk) 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 L be a NP-language associated with a relation 𝑅 such that L𝑅 = {𝑥 |∃𝑤 : 𝑅(𝑥, 𝑤) = 1} Definition 2.5 (Non Interactive proof). A non-interactive proof system Π is a tuple of three PPT algorithms {Setup, Prove, Verify} such that:
1: 𝑝𝑝 ← Setup(1𝜆 ) 2:
• Verify(pk, 𝜎, 𝑚) → 0/1: This algorithm takes a public key pk, a signature 𝜎 and a message 𝑚 and outputs 1 or 0 whether the signature is valid or not.
𝑚 0, 𝑚 1 ∈ M
• Setup(1𝜆 ) → 𝑐𝑟𝑠: This algorithm takes a security parameter 𝜆 and outputs a common reference string 𝑐𝑟𝑠. • Prove(𝑐𝑟𝑠, 𝑥, 𝑤) → 𝜋: This algorithm takes a common reference string 𝑐𝑟𝑠, a statement 𝑥 and a witness 𝑤 as input and outputs a proof 𝜋.
8: end if 9: return 0
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. Definition 2.3 (Signature scheme). Under a security parameter 𝜆, a signature scheme Σ is a tuple of four PPT algorithms Setup, KeyGen, Sign, Verify} such that: • Setup(1𝜆 ) → 𝑝𝑝: This algorithm takes a security parameter 𝜆 and outputs public parameters 𝑝𝑝.
• Verify(𝑐𝑟𝑠, 𝑥, 𝜋) → 0/1: This algorithm takes a common reference string 𝑐𝑟𝑠, a statement 𝑥 and a proof 𝜋 as input and outputs 1 or 0 whether the proof is valid or not. Firstly, it must not be possible to generate proofs for wrong statements. Definition 2.6 (Soundness). Π is sound if for any PPT adversary A, there is a negligible function 𝜀 such that: Verify(𝑐𝑟𝑠, 𝑥 ∗, 𝜋 ∗ ) = 1 𝑝𝑝 ← Setup(1𝜆 ) P : ≤ 𝜀 (𝜆) ∧ 𝑥 ∗ ∉ L𝑅 (𝑥 ∗, 𝜋 ∗ ) ← A (𝑝𝑝)
• KeyGen(𝑝𝑝) → (sk, pk): This algorithm takes public parameters 𝑝𝑝 and outputs a secret and public key (sk, pk).
Secondly, the verifier must not learn anything beyond the statement itself.
• Sign(𝑚, sk) → 𝜎: This algorithm takes a message 𝑚 and a secret key sk and outputs a signature 𝜎.
Definition 2.7 (Adaptive zero-Knowledge). A non-interactive proof system Π is said to be adaptive zero-knowledge if there exists
bPk# : Delegatable Pseudonyms
a PPT simulator SIM = {S1, S2 } such that for every PPT adversary A, there exists a negligible function 𝜀 such that: h i def 𝐾 𝐴𝑑𝑣 𝑍Π,A,S (𝜆) = P 𝑐𝑟𝑠 ← Setup(1𝜆 ) : A P (𝑐𝑟𝑠,·,·) (𝑐𝑟𝑠) = 1 − h i P (𝑐𝑟𝑠, 𝜏) ← S1 (1𝜆 ) : A S (𝑐𝑟𝑠,𝜏,·,·) (𝑐𝑟𝑠) = 1 ≤ 𝜀 (𝜆) where 𝜏 is a simulation trapdoor, P and S are two oracles that return ⊥ if 𝑅(𝑥, 𝑤) ≠ 1 or, respectively, 𝜋 ← Prove(𝑐𝑟𝑠, 𝑥, 𝑤) and 𝜋 ← S2 (𝑐𝑟𝑠, 𝜏, 𝑥) otherwise. 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. Definition 2.8 (Weak Simulation-Sound Extractability). An adaptively zero-knowledge proof system Π achieves weak simulation sound extractability if there exists a PPT extractor (S, E) such that for every PPT adversary A we have: h i def 𝑀 −𝑆𝑜𝑢𝑛𝑑 𝐴𝑑𝑣 𝑆𝐼 (𝜆) = P (𝑐𝑟𝑠, 𝜏) ← S1 (1𝜆 ) : A (𝑐𝑟𝑠) = 1 Π,A h i −P (𝑐𝑟𝑠, 𝜏, 𝜁 ) ← S(1𝜆 ) : A (𝑐𝑟𝑠) = 1 ≤ 𝜀 1 (𝜆) and, h i def 𝑒𝑎𝑘 −𝐸𝑥𝑡 𝑊 𝑒𝑎𝑘 −𝐸𝑥𝑡 𝐴𝑑𝑣𝑊 (𝜆) = P Exp (𝜆) = 1 ≤ 𝜀 2 (𝜆) Π,A Π,A 𝑒𝑎𝑘 −𝐸𝑥𝑡 is defined in Experiment 2. where Exp𝑊 Π,A
𝑒𝑎𝑘 −𝐸𝑥𝑡 (𝜆) Experiment 2 − Exp𝑊 Π,A
(𝑐𝑟𝑠, 𝜏, 𝜁 ) ← S(1𝜆 ) 2: (𝑥 ∗ , 𝜋 ∗ ) ← A S (𝑐𝑟𝑠,𝜏,·) (𝑐𝑟𝑠) 3: 𝑤 ← E (𝑐𝑟𝑠, 𝜏, 𝑥 ∗ , 𝜋 ∗ ) 4: if Verify(𝑐𝑟𝑠, 𝑥 ∗ , 𝜋 ∗ ) = 1 ∧ 𝑅(𝑥 ∗ , 𝑤) ≠ 1 ∧ (𝑥 ∗ , ·) ∉ Q S then return 1 5: end if 6: return 0 Where S(𝑐𝑟𝑠, 𝜏, 𝑥) := S2 (𝑐𝑟𝑠, 𝜏, 𝑥) and Q S keeps track of queries and answers of S. 1:
For further discussions, we refer, e.g., to Goldwasser et al. [29] and Derler and Slamanig [22]. We adopt the Camenisch-Stadler framework [16] for representing proof goals. We write: h i 𝜋 ← NIZK (𝛼, 𝛽, 𝛾) : 𝑌 = 𝐺 𝛼 · 𝐻 𝛽 ∧ 𝑍 = 𝐺 𝛼 · 𝐻 𝛾 ∧ 𝛾 = 𝛼 · 𝛽 to denote a NIZK demonstrating knowledge of the values 𝛼, 𝛽, 𝛾 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 [24]. Our definition follows the work of Freire et al. [28], where we assume that the identities can implicitly be derived from the keys. Definition 2.9 (Non Interactive Key Exchange protocol). A non-interactive key exchange protocol Ψ is a tuple of PPT algorithms {Setup, KeyGen, ShareKey} such that: • Setup(1𝜆 ) → 𝑝𝑝: This algorithm takes a security parameter 𝜆 and outputs public parameters 𝑝𝑝. • KeyGen(𝑝𝑝) → (sk, pk): This algorithm takes public parameters 𝑝𝑝 and outputs a secret and public key (sk, pk). • ShareKey(pk′, sk) → 𝑘: This algorithm takes a secret key sk and a public key pk′ and outputs a shared key 𝑘. 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 (𝑠𝑘 0, 𝑝𝑘 0 ) and (𝑠𝑘 1, 𝑝𝑘 1 ) are the keys of two users, it always holds that ShareKey(𝑝𝑘 1, 𝑠𝑘 0 ) = ShareKey(𝑝𝑘 0, 𝑠𝑘 1 ). To satisfy this requirement, 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 [18, 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 2.10 (Indistinguishability). A NIKE protocol Ψ is said to be indistinguishable if for any PPT adversary A, there is a negligible function 𝜀 such that: h i 1 def 𝐼 𝑁 𝐷 −𝑁 𝐼𝐾𝐸 𝐴𝑑𝑣 Ψ,A (𝜆) = P ExpIND−NIKE (𝜆) = 1 − ≤ 𝜀 (𝜆) Ψ,A 2 where ExpIND−NIKE is the experiment described in Experiment 3. Ψ,A 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 𝑓 : 𝑋 → 𝑌 is said to be injective if 𝑓 (𝑥) = 𝑓 (𝑦) implies 𝑥 = 𝑦 for all 𝑥, 𝑦 ∈ 𝑋 . Definition 2.11 (Secret key to public key injective property). A non-interactive key exchange protocol NIKE Ψ with secret key
Stephan Krenn, Doryan Lesaignoux, and Sebastian Ramacher
Experiment 3 − ExpIND−NIKE (𝜆) Ψ,A 1: 𝑝𝑝 ← Setup(1𝜆 ) $ 2: 𝑏 ← {0, 1} Ψ 𝐺𝑒𝑛𝑈 ,O𝐶𝑜𝑟𝑟𝑢𝑝𝑡𝑈 3: pk∗ , 𝑝𝑘 0 , 𝑝𝑘 1 ← A O ,O (𝑝𝑝)
Let sk𝑏 be the secret key corresponding to pk𝑏 4: 𝑘 ∗ ← ShareKey(pk∗ , sk𝑏 ) 5: 𝑏 ′ ← A (𝑝𝑝, 𝑘 ∗ ) 6: if :
(a) 𝑏 = 𝑏 ′ and (b) pk0, pk1 and pk∗ have not been corrupted. 9: return 1 10: end if 11: return 0 Where the oracles behave as follows: - O𝐺𝑒𝑛𝑈 generates and stores a fresh key pair (sk, pk) and outputs pk. - O𝐶𝑜𝑟𝑟𝑢𝑝𝑡𝑈 , on input a previously generated pk, outputs the corresponding sk. - O Ψ , on input pk, pk′ that were previously generated, looks up sk′ corresponding to pk′ and returns ShareKey(pk, sk′ ). 7: 8:
space 𝑋 and public key space 𝑌 is secret-key-to-public-key injective if there exists an injective mapping 𝜇 : 𝑋 → 𝑌 such that for all (sk, pk) ← Ψ.KeyGen(𝑝𝑝) it holds that pk = 𝜇 (sk).
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 Figure 1 satisfies all these (legally mandated) requirements, a system addressing the challenges mentioned in Section 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 Figure 2 and Appendix B: Users can obtain their own key material from the central authority ( 1 – 3 ), while trusted service providers optionally obtain their own secret key 4 . Using the public key of a SP 5 , users can now locally compute verifiable pseudonyms for SP 6 , while trusted SPs can fetch a user public key 7 to locally compute the pseudonym 8 . The authorities capabilities (e.g., linking pseudonyms 9 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
bPk# : Delegatable Pseudonyms
eID 1
3
2
Central authority
secret + public key
5
SP'
9
public keys
SP''
6
4 7
SP
secret + public key
SP'''
8
Figure 2: Logical information flow for the proposed bPk# architecture
trust into this party, in practice one might implement the algorithm as a multi-party protocol5 , 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. Setup(1𝜆 ) → 𝑝𝑝 is a probabilistic algorithm that, given security parameter 1𝜆 , outputs public parameters 𝑝𝑝 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 3𝐷𝐸𝑆 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 [20, 35] or attribute-based credentials [12], 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 Section 3.1: KeyGen(𝑝𝑝) → (𝑚𝑠𝑘, 𝑚𝑝𝑘) is a probabilistic algorithm that, given public parameters 𝑝𝑝 as input, outputs the master secret key 𝑚𝑠𝑘 and the master public key 𝑚𝑝𝑘. KeyGen𝑢𝑠𝑒𝑟 (𝑚𝑠𝑘) → (𝑢𝑠𝑘, 𝑢𝑝𝑘) is a probabilistic algorithm that, given the master secret key 𝑚𝑠𝑘, outputs a pair of public and private keys (𝑢𝑠𝑘, 𝑢𝑝𝑘) for the user .
Next, users need to be able to generate pseudonyms. To achieve authenticity, they additionally generate a proof showing the wellformedness 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. NymGen𝑢𝑠𝑒𝑟 (𝑢𝑠𝑘, 𝑚𝑝𝑘, 𝑠𝑝𝑝𝑘) → (nym, 𝜋) is an algorithm that, given 𝑢𝑠𝑘, 𝑢𝑝𝑘, 𝑠𝑝𝑝𝑘 and 𝑚𝑝𝑘, outputs the user pseudonym nym and validity proof 𝜋. NymVf (𝑚𝑝𝑘, 𝑠𝑝𝑝𝑘, nym, 𝜋) → 0/1 is a deterministic algorithm that, given the master public key 𝑚𝑠𝑘, a service provider public key 𝑠𝑝𝑝𝑘, a pseudonym nym, a proof 𝜋, outputs 1 or 0 whether 𝜋 is valid for nym or not. NymGen𝑆𝑃 (𝑠𝑝𝑠𝑘, 𝑚𝑝𝑘, 𝑢𝑝𝑘) → nym is a deterministic algorithm that, given the secret key of the service provider 𝑠𝑝𝑠𝑘 and the public key of the user 𝑢𝑝𝑘, outputs the user pseudonym 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. Open(𝜋, 𝑚𝑠𝑘) → 𝑢𝑝𝑘 is a deterministic algorithm that, given a proof 𝜋 and the master secret key 𝑚𝑠𝑘, outputs the user public key 𝑢𝑝𝑘. 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; nonframeability, 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.
KeyGen𝑆𝑃 (𝑚𝑠𝑘) → (𝑠𝑝𝑠𝑘, 𝑠𝑝𝑝𝑘) is a probabilistic algorithm that, given the master secret key 𝑚𝑠𝑘, outputs a pair of public and private keys (𝑠𝑝𝑠𝑘, 𝑠𝑝𝑝𝑘) for the service provider.
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.
5 As demonstrated for example in [34].
Furthermore, as illustrated in Figure 3, service providers and users should always obtain the same pseudonym for a given user (i.e.,
Stephan Krenn, Doryan Lesaignoux, and Sebastian Ramacher
Non−Frameability
(𝑢𝑠𝑘,𝑠𝑝𝑝𝑘 )
CA
U
(𝑠𝑝𝑠𝑘,𝑢𝑝𝑘 )
NymGen𝑢𝑠𝑒𝑟 NymGen𝑆𝑃
SP
nym
Experiment 4 − Exp A
(𝜆)
1: N, KPu , PKu , SKu , PKsp , SKsp , Cu ← ∅ 2: 𝑝𝑝 ← Setup(1𝜆 )
(𝑚𝑠𝑘, 𝑚𝑝𝑘) ← KeyGen(𝑝𝑝) 𝑛𝑦𝑚 𝐺𝑒𝑛𝑈 ,O𝐺𝑒𝑛𝑆𝑃 ,O𝐶𝑜𝑟𝑟𝑢𝑝𝑈 (𝑠𝑝𝑝𝑘, nym∗, 𝜋 ∗ ) ← A O ,O (𝑝𝑝, 𝑚𝑝𝑘) 5: if : // Adversary outputs a pseudonym of a non-existing user 6: (a) NymVf (nym∗, 𝜋 ∗, 𝑚𝑝𝑘, 𝑠𝑝𝑝𝑘) = 1 7: (b) For 𝑢𝑝𝑘 ∗ = Open(𝜋, 𝑚𝑠𝑘), (𝑢𝑝𝑘 ∗, 𝑢𝑠𝑘 ∗ ) ∈ KPu 8: return 1 9: end if 10: if : // Adversary forges a fresh pseudonym for an honest user 11: (a) NymVf (nym∗, 𝜋 ∗, 𝑚𝑝𝑘, 𝑠𝑝𝑝𝑘) = 1 12: (b) For 𝑢𝑝𝑘 ∗ = Open(𝜋, 𝑚𝑠𝑘), ∃(𝑢𝑝𝑘 ∗, 𝑢𝑠𝑘 ∗ ) ∈ KPu 13: (c) (𝑢𝑝𝑘 ∗, 𝑠𝑝𝑝𝑘) ∉ N 14: (d) 𝑢𝑠𝑘 ∗ ∉ 𝐶𝑢 15: return 1 16: end if 17: return 0 3:
4:
Figure 3: Correctness of pseudonym generation knowing 𝑢𝑠𝑘 and 𝑠𝑝𝑝𝑘 should result in the same nym as starting from 𝑢𝑝𝑘 and 𝑠𝑝𝑠𝑘). 3.3.2 Non-Frameability. As discussed earlier, authenticity of usergenerated 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 [8, 35], the central authority must not collude, as our framework does contain secret key material solely held by the user (cf. the discussion in Section 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.
Oracle 1 User generation oracle O𝐺𝑒𝑛𝑈 1:
(𝑢𝑠𝑘, 𝑢𝑝𝑘) = KeyGen𝑢𝑠𝑒𝑟 (𝑚𝑠𝑘)
2: PKu = PKu ∪ {𝑢𝑝𝑘 } 3: SKu = SKu ∪ {𝑢𝑠𝑘 } 4: KPu = KPu ∪ {(𝑢𝑠𝑘, 𝑢𝑝𝑘)} 5: return 𝑢𝑝𝑘
In the experiment, N denotes the set of queried pseudonyms. Let 𝐾𝑃𝑢 be the set of all created pairs of user public and private keys generated by the central authority. We also define the subsets PKu (resp. SKu ) of 𝐾𝑃𝑢 as the set of honestly generated user public (resp. private) keys. Let PKsp , SKsp , and KPsp be the respective sets of service provider keys generated by the central authority. Finally, Cu denotes the set of corrupted users. Definition 3.1 (Non-Frameability). A delegateable pseudonym system is said to be non-frameable, if for every PPT adversary A there exists a negligible function 𝜀 (.) such that: h i Non−Frameability P Exp A (𝜆) = 1 ≤ 𝜀 (𝜆), Non−Frameability
where Exp A
(𝜆) is defined in Experiment 4.
Oracle 2 Service provider generation oracle O𝐺𝑒𝑛𝑆𝑃 Ensure: Service provider public key 𝑠𝑝𝑝𝑘 1: (𝑠𝑝𝑠𝑘, 𝑠𝑝𝑝𝑘) = KeyGen𝑢𝑠𝑒𝑟 (𝑚𝑠𝑘) 2: PKsp = PKsp ∪ {𝑠𝑝𝑝𝑘} 3: SKsp = SKsp ∪ {𝑠𝑝𝑠𝑘 } 4: KPsp = KPsp ∪ {(𝑠𝑝𝑠𝑘, 𝑠𝑝𝑝𝑘)} 5: return 𝑠𝑝𝑝𝑘
Oracle 3 Pseudonym generation oracle O 𝑁 𝑦𝑚 Require: Service provider public key 𝑠𝑝𝑝𝑘, user public key 𝑢𝑝𝑘 Ensure: pseudonym nym and proof 𝜋. 1: if 𝑠𝑝𝑝𝑘 ∉ PKsp or 𝑢𝑝𝑘 ∉ PKu : then return ⊥ 2: end if 3: Find (𝑢𝑠𝑘, 𝑢𝑝𝑘) ∈ KPu 4: Compute (nym, 𝜋) = NymGen𝑢𝑠𝑒𝑟 (𝑢𝑠𝑘, 𝑚𝑝𝑘, 𝑠𝑝𝑝𝑘, 𝑚𝑝𝑘) 5: 𝑁 ← 𝑁 ∪ {(𝑢𝑝𝑘, 𝑠𝑝𝑝𝑘)} 6: return nym, 𝜋
In the security experiment, the adversary is given access to a number of oracles. Intuitively, upon the adversary’s request, O𝐺𝑒𝑛𝑈 creates a new honest user, and hands the corresponding public key 𝑢𝑝𝑘 to A. Similarly, the adversary may request the creation of additional service providers through a call to O𝐺𝑒𝑛𝑆𝑃 , again obtaining only the corresponding public key 𝑠𝑝𝑝𝑘. 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 O 𝑁 𝑦𝑚 ; in case that the indicated service provider or user does not exist, the oracle returns ⊥. Finally, A can corrupt users, thereby obtaining the corresponding secret key 𝑢𝑠𝑘, through O𝐶𝑜𝑟𝑟𝑢𝑝𝑡𝑈 .
they are unable to generate pseudonyms by themselves. Trusted (e.g., publicly hosted) service providers should only receive their 𝑠𝑝𝑠𝑘 within secure hardware, such that key extraction is not possible, either.
We now formally define these oracles in Oracles 1 to 4. Note that no oracle for corrupting service providers exists: as discussed earlier, untrusted service providers do not obtain their secret key, so that
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
bPk# : Delegatable Pseudonyms
Oracle 4 Corrupted user oracle O𝐶𝑜𝑟𝑟𝑢𝑝𝑡𝑈 Require: User public key 𝑢𝑝𝑘 Ensure: User secret key 𝑢𝑠𝑘 1: if 𝑢𝑝𝑘 ∉ PKu then return ⊥ 2: end if 3: Find (𝑢𝑠𝑘, 𝑢𝑝𝑘) ∈ KPu 4: 𝐶𝑢 ← 𝐶𝑢 ∪ {(𝑢𝑠𝑘, 𝑢𝑝𝑘)} 5: return 𝑢𝑠𝑘
Anonymity
Experiment 5 − Exp A
(𝜆)
$ 1: 𝑏 ← {0, 1} 2: LR, N, KPu , PKu , SKu , PKsp , SKsp , Cu , Csp ← ∅ 3: 𝑝𝑝 ← Setup(1𝜆 ) 4:
(𝑚𝑠𝑘, 𝑚𝑝𝑘) ← KeyGen(𝑝𝑝)
5: 𝑏 ′ ← A O
𝐿𝑜𝑅 ,O𝐺𝑒𝑛𝑈 ,O𝐺𝑒𝑛𝑆𝑃 ,O 𝑁 𝑦𝑚 ,O𝐶𝑜𝑟𝑟𝑢𝑝𝑈 ,O𝐶𝑜𝑟𝑟𝑢𝑝𝑡𝑆𝑃 (𝑝𝑝,𝑚𝑝𝑘 )
6: if :
(a) 𝑏 ′ = 𝑏 (b) ∀A = 𝑢𝑝𝑘 0, 𝑢𝑝𝑘 1 , A′ = 𝑢𝑝𝑘 0′ , 𝑢𝑝𝑘 1′ s.t 8: ′ ′ (𝐴, 𝑠𝑝𝑝𝑘), (𝐴 , 𝑠𝑝𝑝𝑘) ∈ LR, we have 𝐴 = 𝐴 or 𝐴 ∩ 𝐴′ = ∅ 9: (c) ∀(𝑢𝑝𝑘, 𝑠𝑝𝑝𝑘) ∈ N, 𝑢𝑝𝑘 ′ ∈ PKu : ( 𝑢𝑝𝑘, 𝑢𝑝𝑘 ′ , 𝑠𝑝𝑝𝑘) or ( 𝑢𝑝𝑘 ′, 𝑢𝑝𝑘 , 𝑠𝑝𝑝𝑘) ∈ LR 10: (d) ∀( 𝑢𝑝𝑘, 𝑢𝑝𝑘 ′ , 𝑠𝑝𝑝𝑘) ∈ LR, 𝑢𝑝𝑘, 𝑢𝑝𝑘 ′ ∉ Cu and 𝑠𝑝𝑝𝑘 ∉ CSP 11: (e) ∀(𝑢𝑝𝑘, 𝑠𝑝𝑝𝑘) ∈ N, 𝑢𝑝𝑘 ∉ Cu and 𝑠𝑝𝑝𝑘 ∉ Csp 12: return 1 13: end if 14: return 0 7:
than random guessing whether by which of two (adversarially chosen) users a specific pseudonym was created. Definition 3.2 (Anonymity). A delegatable pseudonym system is said to be anonymous, if for every PPT adversary A there exists a negligible function 𝜀 (.) such that: h i 1 Anonymity P Exp A (𝜆) = 1 − ≤ 𝜀 (𝜆), 2 Anonymity
where Exp A
(𝜆) is defined in Experiment 5.
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: (𝑏) for the same service provider, the adversary must not query inconsistent inputs, e.g., (𝑢𝑝𝑘 1, 𝑢𝑝𝑘 2 ) and then (𝑢𝑝𝑘 1, 𝑢𝑝𝑘 3 ), as this would trivially allow the adversary to decide which output it receives; (𝑐) similarly, it must not request an honest pseudonym for a service provider that it also used in the LoR oracle, e.g., (𝑢𝑝𝑘 1, 𝑢𝑝𝑘 2 ) to LoR and also obtain a pseudonym for 𝑢𝑝𝑘 1 , as this trivially allows to guess the output it receives; (𝑑) it must not send 𝑢𝑝𝑘’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 (𝑒) it must not request pseudonyms for corrupted service providers or pseudonyms. While the latter is clear similarly to (𝑑), 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 𝑠𝑝𝑠𝑘 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, O 𝐿𝑜𝑅 always returns the 𝑏 th pseudonym and proof for two inputs (𝑢𝑝𝑘, 𝑢𝑝𝑘 ′ ) for a given service provider. Finally, service providers can be corrupted through the O𝐶𝑜𝑟𝑟𝑢𝑝𝑡𝑆𝑃 oracle. We formally define these oracles in Oracles 5 and 6.
4
Construction
In the following we provide a blackbox construction from a set of cryptographic primitives as defined in Section 2 and provide rigorous proofs that it achieves non-frameability and anonymity. Therefore, let Σ be a signature scheme, Λ be an encryption scheme, Ψ be a non-interactive key exchange protocol with secret key to public key injective property, and Π be a non-interactive weakly
Oracle 5 Left or Right oracle O 𝐿𝑜𝑅 Require: Set of two public keys 𝑢𝑝𝑘 0, 𝑢𝑝𝑘 1 and service provider public key 𝑠𝑝𝑝𝑘 Ensure: Pseudonym nym𝑏 1: if 𝑢𝑝𝑘 0 ∉ PKu or 𝑢𝑝𝑘 1 ∉ PKu or 𝑠𝑝𝑝𝑘 ∉ PKsp then return ⊥ 2: end if 3: Find (𝑢𝑠𝑘 𝑖 , 𝑢𝑝𝑘 𝑖 ) ∈ KPu for 𝑖 = 0, 1 4: Compute (nym𝑖 , 𝜋𝑖 ) = NymGen𝑢𝑠𝑒𝑟 (𝑢𝑠𝑘 𝑖 , 𝑚𝑝𝑘, 𝑠𝑝𝑝𝑘) for 𝑖 = 0, 1 5: 𝐿𝑅 ← 𝐿𝑅 ∪ ( 𝑢𝑝𝑘 0 , 𝑢𝑝𝑘 1 , 𝑠𝑝𝑝𝑘) 6: return nym𝑏 , 𝜋𝑏 Oracle 6 Corrupted service provider oracle O𝐶𝑜𝑟𝑟𝑢𝑝𝑡𝑆𝑃 Require: Service provider public key 𝑠𝑝𝑝𝑘 Ensure: Service provider secret key 𝑠𝑝𝑠𝑘 1: if 𝑠𝑝𝑝𝑘 ∉ PKsp then return ⊥ 2: end if 3: Find (𝑠𝑝𝑠𝑘, 𝑠𝑝𝑝𝑘) ∈ KPsp 4: 𝐶𝑠𝑝 ← 𝐶𝑠𝑝 ∪ {(𝑠𝑝𝑠𝑘, 𝑠𝑝𝑝𝑘)} 5: return 𝑠𝑝𝑠𝑘
simulation-sound proof system. Without loss of generality, we assume that the schemes are compatible in the sense that the message spaces of Σ and Λ include the public key space of Ψ. 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
Stephan Krenn, Doryan Lesaignoux, and Sebastian Ramacher
key. Now, when the user generates a pseudonym nym they also compute a proof 𝜋 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 𝑏𝑃𝑘 # Λ,Σ,Ψ,Π is given in Construction 1. We now obtain the following core results regarding the security of our generic construction. Theorem 4.1. Let Λ be a public-key encryption scheme, Σ be an EUF-CMA signature scheme, Ψ be a NIKE scheme satisfying indistinguishability and secret to public key injective properties and Π be a ZKPoK system. Then, 𝑏𝑃𝑘 # Λ,Σ,Ψ,Π achieves non-frameability against an adaptive PPT adversary A. 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 Appendix A.1. Theorem 4.2. Let Λ be an IND-CPA public-key encryption scheme, Σ be an EUF-CMA signature scheme, Ψ be a NIKE scheme satisfying indistinguishability and secret to public key injective properties and Π be a ZKPoK system. Then, 𝑏𝑃𝑘 # Λ,Σ,Ψ,Π achieves anonymity against an adaptive PPT adversary A. 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 𝑠𝑝𝑝𝑘’s. For the full proof, we refer to Appendix A.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
Setup(1𝜆 ) : 1: 𝑝𝑝 Σ ← Σ.Setup(1𝜆 ) 2: 𝑝𝑝 Λ ← Λ.Setup(1𝜆 ) 3: 𝑝𝑝 Π ← Π.Setup(1𝜆 ) 4: 𝑝𝑝 Ψ ← Ψ.Setup(1𝜆 ) 5: return 𝑝𝑝 = {𝑝𝑝 Σ , 𝑝𝑝 Λ , 𝑝𝑝 Π , 𝑝𝑝 Ψ } KeyGen(𝑝𝑝) : 1: (𝑚𝑠𝑘 Σ , 𝑚𝑝𝑘 Σ ) ← Σ.KeyGen(𝑝𝑝 Σ ) 2: (𝑚𝑠𝑘 Λ , 𝑚𝑝𝑘 Λ ) ← Λ.KeyGen(𝑝𝑝 Λ ) 3: 𝑚𝑠𝑘 ← (𝑚𝑠𝑘 Σ , 𝑚𝑠𝑘 Λ ) 4: 𝑚𝑝𝑘 ← (𝑚𝑝𝑘 Σ , 𝑚𝑝𝑘 Λ ) 5: return 𝑚𝑠𝑘, 𝑚𝑝𝑘 KeyGen𝑢𝑠𝑒𝑟 (𝑚𝑠𝑘) : ′ 1: (𝑢𝑠𝑘 , 𝑢𝑝𝑘) ← Ψ.KeyGen(𝑝𝑝 Ψ ) 2: 𝜎 ← Σ.Sign(𝑢𝑝𝑘, 𝑚𝑠𝑘 Σ ) ′ 3: return 𝑢𝑠𝑘 = (𝑢𝑠𝑘 , 𝜎), 𝑢𝑝𝑘 KeyGen𝑆𝑃 (𝑚𝑠𝑘) : 1: (𝑠𝑝𝑠𝑘, 𝑠𝑝𝑝𝑘) ← Ψ.KeyGen(𝑝𝑝 Ψ ) 2: return 𝑠𝑝𝑠𝑘, 𝑠𝑝𝑝𝑘 NymGen𝑢𝑠𝑒𝑟 (𝑢𝑠𝑘, 𝑚𝑝𝑘, 𝑠𝑝𝑝𝑘) : ′ 1: Parse 𝑢𝑠𝑘 as (𝑢𝑠𝑘 , 𝜎) ′ 2: nym ← Ψ.ShareKey(𝑠𝑝𝑝𝑘, 𝑢𝑠𝑘 ) 3: 𝑐 ← Λ.Enc(𝑚𝑝𝑘, 𝑢𝑝𝑘; 𝑟 ) 𝑟 ←$ R ′ 4: 𝜋 ← (𝑐, Π.Prove[(𝑢𝑠𝑘 , 𝑢𝑝𝑘, 𝜎, 𝑟 ) : Σ.Verify(𝑚𝑝𝑘, 𝜎, 𝑢𝑝𝑘) = 1 ∧ 𝑐 = Λ.Enc(𝑚𝑝𝑘, 𝑢𝑝𝑘; 𝑟 ) ∧ 𝑢𝑝𝑘 = 𝜇 (𝑢𝑠𝑘 ′ ) ∧ nym = Ψ.ShareKey(𝑠𝑝𝑝𝑘, 𝑢𝑠𝑘 ′ )]) 5: return nym, 𝜋
NymGen𝑆𝑃 (𝑠𝑝𝑠𝑘, 𝑚𝑝𝑘, 𝑢𝑝𝑘) : 1: return nym ← Ψ.ShareKey(𝑢𝑝𝑘, 𝑠𝑝𝑠𝑘) NymVf (𝑚𝑝𝑘, 𝑠𝑝𝑝𝑘, nym, 𝜋) : 1: return Π.Verify(𝑝𝑝 Π , (𝑚𝑝𝑘, 𝑠𝑝𝑝𝑘, nym), 𝜋) Open(𝜋, 𝑚𝑠𝑘) : 1: Parse 𝜋 as (𝑐, 𝜋 ′ ) 2: return 𝑢𝑝𝑘 ← Λ.Dec(𝑚𝑠𝑘, 𝑐)
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 [7, 10] which are based on Groth’s structure-preserving signatures [30]. 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 needs6 : 6We present the variant that signs a group element in G . By switching the role of G 1 1 and G2 in the construction, the signature scheme would allow signing group elements
in G2 .
Construction 1 𝑏𝑃𝑘 # Λ,Σ,Ψ,Π with public-key key encryption scheme Λ, signature scheme Σ, NIKE Ψ and NIZK Π such that the public-key space of Ψ is (a subset of) the message spaces of Λ and Σ. We also define R as the set in which the random used in the encryption process of Λ is sampled.
• Groth1 .Setup(1𝜆 ) generates public parameters of a bilinear ˆ of prime order 𝑝, where 𝐺 ∈ group (G1, G2, G𝑇 , 𝑒, 𝑝, 𝐺, 𝐺) ˆ G1 and 𝐺 ∈ G2 are generators. It additionally outputs an element 𝑌 ←$ G1 . • Groth1 .KeyGen() samples sk ← Z𝑝∗ and sets pk ← 𝐺ˆ sk . • Groth1 .Sign(sk, msg) samples 𝑟 ← Z𝑝∗ and computes a ˆ 𝑆,𝑇 ) = (𝐺ˆ 𝑟 , (𝑌 · 𝐺 sk ) 1/𝑟 , (𝑌 sk · msg) 1/𝑟 ). signature 𝜎 = (𝑅,
bPk# : Delegatable Pseudonyms
• Groth1 .Rand(𝜎) rerandomizes a valid signature 𝜎 by sampling 𝑟 ′ ← Z𝑝∗ and outputting a randomized signature ′ ′ ′ 𝜎 ′ = (𝑅ˆ ′, 𝑆 ′,𝑇 ′ ) = (𝑅ˆ𝑟 , 𝑆 1/𝑟 ,𝑇 1/𝑟 ) on the same message. • Groth1 .Verify(pk, 𝜎, msg) outputs 1 if and only if it holds ˆ = 𝑒 (𝑌, 𝐺) ˆ · 𝑒 (𝐺, pk) and 𝑒 (𝑇 , 𝑅) ˆ = 𝑒 (𝑌, pk) · that 𝑒 (𝑆, 𝑅) ˆ 𝑒 (msg, 𝐺). For the NIKE we need to also select schemes with public keys in G1 . Under the XDH assumption, note that we can instantiate the Diffie-Hellman [24] NIKE in G1 . Hence, we obtain the following NIKE: • DH.Setup(1𝜆 ) sets 𝑝𝑝 to G1 and 𝐻 ←$ G1 . Returns 𝑝𝑝. • DH.KeyGen() samples sk ←$ Z𝑝∗ and sets pk ← 𝐻 sk .
′
• ElGamal.Setup(1𝜆 ) sets 𝑝𝑝 to G1 and 𝐾 ←$ G1 . Returns 𝑝𝑝. • ElGamal.KeyGen() samples sk ←$ Z𝑝∗ and sets pk ← 𝐾 sk .
NymGen𝑢𝑠𝑒𝑟 (𝑢𝑠𝑘, 𝑚𝑝𝑘, 𝑠𝑝𝑝𝑘) :
Similarly, under the XDH assumption, ElGamal encryption [25] provides a secure public-key encryption scheme in G1 with message space G1 :
• ElGamal.Enc(pk, msg) computes 𝑟 pk𝑟 msg).
←$ Z𝑝∗ , return (𝐾 𝑟 ,
• ElGamal.Dec(sk, (𝑐 1, 𝑐 2 )) returns 𝑐 2𝑐 1−sk .
Protocol Specification
Putting the above building blocks into the generic construction presented in Section 4, we now obtain the concrete instantiation described in Construction 2. Note that the proof goal could be slightly simplified, by replacing ′ 𝑢𝑝𝑘 ′𝑠 by 𝐻 𝑢𝑠𝑘 in all equations, and removing the explicit term. By proving the relation 𝑢𝑝𝑘 = 𝜇 (𝑢𝑠𝑘 ′ ) implicitly, one can reduce the computational complexity of the proof goal by one discrete logarithm, and also reduce the communication complexity by removing 𝑢𝑝𝑘 ′ from 𝜋. 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 FiatShamir transform [27] induce a simulation-sound extractable NIZK provided that the underlying Σ-protocol provides quasi-unique responses [26] and the statement is used as part of the challenge generation [5]. 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 [31] to prove the pairing equations.
5.3
Setup(1𝜆 ) : 1: Generate public parameters of a bilinear group 𝑝𝑝 ′ = ˆ of prime order 𝑝, where 𝐺 ∈ G1 (G1, G2, G𝑇 , 𝑒, 𝑝, 𝐺, 𝐺) and 𝐺ˆ ∈ G2 are generators 2: Sample 𝑌 ←$ G1 , 𝐻 ←$ G1 , and 𝐾 ←$ G1 . 3: return 𝑝𝑝 = (𝑝𝑝 ′ , 𝑌, 𝐻, 𝐾). KeyGen(𝑝𝑝) : 1: (𝑚𝑠𝑘 Groth1 , 𝑚𝑝𝑘 Groth ) ← Groth1 .KeyGen() 1 2: (𝑚𝑠𝑘 ElGamal , 𝑚𝑝𝑘 ElGamal ) ← ElGamal.KeyGen() 3: return 𝑚𝑠𝑘 ← (𝑚𝑠𝑘 Groth1 , 𝑚𝑠𝑘 ElGamal ) and 𝑚𝑝𝑘 ← (𝑚𝑝𝑘 Groth1 , 𝑚𝑝𝑘 ElGamal ). KeyGen𝑢𝑠𝑒𝑟 (𝑝𝑝, 𝑚𝑠𝑘) : (𝑢𝑠𝑘 ′, 𝑢𝑝𝑘) ← DH.KeyGen() = (𝑢𝑠𝑘 ′, 𝐻 𝑢𝑠𝑘 ) for 𝑢𝑠𝑘 ′ ← Z𝑝∗ ˆ 𝑆,𝑇 ) = (𝐺ˆ 𝑟 , (𝑌 · 2: 𝜎 ← Groth1 .Sign(𝑢𝑝𝑘, 𝑚𝑠𝑘 Groth1 ) = (𝑅, 𝑚𝑠𝑘 𝑚𝑠𝑘 1/𝑟 1/𝑟 Groth1 ) Groth1 · 𝑢𝑝𝑘) 𝐺 , (𝑌 ) for 𝑟 ← Z𝑝∗ ′ 3: return 𝑢𝑠𝑘 = (𝑢𝑠𝑘 , 𝜎) and 𝑢𝑝𝑘. KeyGen𝑆𝑃 (𝑝𝑝, 𝑚𝑠𝑘) :
• DH.ShareKey(pk′, sk) computes shk ← pk′sk .
5.2
Construction 2 Instantiating 𝑏𝑃𝑘 # with ElGamal encryption, Groth signatures, Diffie-Hellman key exchange, and Schnorr proofs.
Efficiency Evaluation
1:
∗ 1: return DH.KeyGen() = (𝑠𝑝𝑠𝑘, 𝐻 𝑠𝑝𝑠𝑘 ) for 𝑠𝑝𝑠𝑘 ← Z𝑝 ′ 𝑢𝑠𝑘 ′ 1: nym ← DH.ShareKey(𝑠𝑝𝑝𝑘, 𝑢𝑠𝑘 ) = 𝑠𝑝𝑝𝑘
= (𝑐 1, 𝑐 2 ) ←$ ElGamal.Enc(𝑚𝑝𝑘 ElGamal, 𝑢𝑝𝑘; 𝑟 ) = (𝐾 𝑟 , 𝑚𝑝𝑘 𝑟ElGamal𝑢𝑝𝑘) with 𝑟 ←$ Z𝑝∗ 3: 𝜎 ′ ← Groth1 .Rand(𝜎; 𝑟 ′ ) = (𝑅ˆ ′, 𝑆 ′,𝑇 ′ ) = ′ ′ (𝑅ˆ𝑟 , 𝑆 1/𝑟 ,𝑇 1/𝑟 ) with 𝑟 ′ ←$ Z𝑝∗ . ∗ 4: (𝑅ˆ ′′ , 𝑆 ′′ ,𝑇 ′′ ) ← (𝑅ˆ ′ , 𝑆 ′1/𝛼 ,𝑇 ′1/𝛽 ) for 𝛼, 𝛽 ←$ Z𝑝 2: 𝑐
5: 𝑢𝑝𝑘
′ ← 𝑢𝑝𝑘 1/𝑠 for 𝑠 ← Z∗ $ 𝑝
6: Produce a Schnorr-style proof:
𝜋 ′ ← Π.Prove[(𝑟, 𝑠, 𝑢𝑠𝑘 ′, 𝜎 ′ ) : ˆ · 𝑒 (𝐺, 𝑚𝑝𝑘 𝑒 (𝑆 ′′, 𝑅ˆ ′′ )𝛼 = 𝑒 (𝑌, 𝐺) Groth1 ) ∧ ˆ 𝑠∧ 𝑒 (𝑇 ′′, 𝑅ˆ ′′ ) 𝛽 = 𝑒 (𝑌, 𝑚𝑝𝑘 Groth1 ) · 𝑒 (𝑢𝑝𝑘 ′, 𝐺) 𝑐 1 = 𝐾 𝑟 ∧ 𝑐 2 = 𝑢𝑝𝑘 ′𝑠 · 𝑚𝑝𝑘 𝑟ElGamal ∧ ′
′
𝑢𝑝𝑘 ′𝑠 = 𝐻 𝑢𝑠𝑘 ∧ nym = 𝑠𝑝𝑝𝑘𝑢𝑠𝑘 ] ′ 7: 𝜋 ← (𝜋 ′ , 𝑐, 𝑅ˆ ′′ , 𝑆 ′′ ,𝑇 ′′ , 𝑢𝑝𝑘 ) 8: return (nym, 𝜋) NymGen𝑆𝑃 (𝑠𝑝𝑠𝑘, 𝑚𝑝𝑘, 𝑢𝑝𝑘) : 1: return DH.ShareKey(𝑢𝑝𝑘, 𝑠𝑝𝑠𝑘). NymVf (𝑚𝑝𝑘, 𝑠𝑝𝑝𝑘, nym, 𝜋) : ′ 1: Parse 𝜋 as (𝜋 ′ , 𝑐, 𝑅ˆ ′′ , 𝑆 ′′ ,𝑇 ′′ , 𝑢𝑝𝑘 ). 2: return the verification result of 𝜋 ′ Open(𝜋, 𝑚𝑠𝑘) : ′ 1: Parse 𝜋 as (𝜋 ′ , 𝑐, 𝑅ˆ ′′ , 𝑆 ′′ ,𝑇 ′′ , 𝑢𝑝𝑘 ) 2: return 𝑢𝑝𝑘 ← ElGamal.Dec(𝑚𝑠𝑘 ElGamal , 𝑐)
The above pairing-based instantiation was implemented7 in Rust 1.85 using the BLS12-381 bilinear pairing via the ark-bls12-381
crate8 . To demonstrate the efficiency of our construction, we have
7 https://anonymous.4open.science/r/bpkplus-4CE0/
8 https://crates.io/crates/ark_bls12_381, version 0.5.0.
Stephan Krenn, Doryan Lesaignoux, and Sebastian Ramacher
benchmarked the implementation on an Intel Core i7-1265U with 16 GB of RAM running Ubuntu 24.04. Since all algorithms except NymGen and NymVf consist of at most 3 efficient group operations, we present the results of NymGen and NymVf in Figures 4 and 5. From the benchmark results we can observe that over 100 runs the runtime over NymGen averages at 4.94 ± 0.02 ms and NymVf averages at 7.61 ± 0.03 ms. 6
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 Appendix C.
Density (a.u.)
5
7
4
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 20ms for all operations on standard hardware.
3 2 1 0 4.6
4.8
5
5.2
Conclusion
5.4
Average Time (ms)
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., [3, 6, 36, 38], selecting compatible proof systems and building blocks to obtain a practically efficient instantiation poses an interesting open problem.
Figure 4: Benchmark results for NymGen. 5 4.5 4
Density (a.u.)
3.5 3 2.5 2 1.5 1 0.5 0 7.5
8
8.5
Average Time (ms)
Figure 5: Benchmark results for NymVf . 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 G1 or G2 . Furthermore, observe that the secret key of Groth1 is only applied to group elements in G1 . Hence, we can follow the same approach as in [32] which use existing implementations of RSA and elliptic curve groups to implement G1 operations on a secure element whereas all operations in G2 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 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
An orthogonal interesting extension inspired, e.g., by [14], 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
References [1] A-SIT Plus GmbH. 2021. ID Austria: Technisches Whitepaper - Hintergrundinformationen. https://eid.egiz.gv.at/wp-content/uploads/2021/12/ID-AustriaTechnische-Hintergrundinformationen-v1.4-1.pdf [2] Andreas Abraham, Karl Koch, Stefan More, Sebastian Ramacher, and Miha Stopar. 2021. Privacy-Preserving eID Derivation to Self-Sovereign Identity Systems with Offline Revocation. In TrustCom. IEEE, 506–513. [3] Martin R. Albrecht, Valerio Cini, Russell W. F. Lai, Giulio Malavolta, and Sri Aravinda Krishnan Thyagarajan. 2022. Lattice-Based SNARKs: Publicly Verifiable, Preprocessing, and Recursively Composable - (Extended Abstract). In CRYPTO 2022, Part II (LNCS, Vol. 13508), Yevgeniy Dodis and Thomas Shrimpton (Eds.). Springer, Cham, 102–132. doi:10.1007/978-3-031-15979-4_4 [4] Foteini Baldimtsi, Jan Camenisch, Maria Dubovitskaya, Anna Lysyanskaya, Leonid Reyzin, Kai Samelin, and Sophia Yakoubov. 2017. Accumulators with
bPk# : Delegatable Pseudonyms
Applications to Anonymity-Preserving Revocation. In 2017 IEEE European Symposium on Security and Privacy. IEEE Computer Society Press, 301–315. doi:10.1109/EuroSP.2017.13 [5] David Bernhard, Olivier Pereira, and Bogdan Warinschi. 2012. How Not to Prove Yourself: Pitfalls of the Fiat-Shamir Heuristic and Applications to Helios. In ASIACRYPT 2012 (LNCS, Vol. 7658), Xiaoyun Wang and Kazue Sako (Eds.). Springer, Berlin, Heidelberg, 626–643. doi:10.1007/978-3-642-34961-4_38 [6] Ward Beullens, Vadim Lyubashevsky, Ngoc Khanh Nguyen, and Gregor Seiler. 2023. Lattice-Based Blind Signatures: Short, Efficient, and Round-Optimal. In ACM CCS 2023, Weizhi Meng, Christian Damsgaard Jensen, Cas Cremers, and Engin Kirda (Eds.). ACM Press, 16–29. doi:10.1145/3576915.3616613 [7] Jan Bobolz, Fabian Eidens, Stephan Krenn, Sebastian Ramacher, and Kai Samelin. 2021. Issuer-Hiding Attribute-Based Credentials. In CANS 21 (LNCS, Vol. 13099), Mauro Conti, Marc Stevens, and Stephan Krenn (Eds.). Springer, Cham, 158–178. doi:10.1007/978-3-030-92548-2_9 [8] Jonathan Bootle, Andrea Cerulli, Pyrros Chaidos, Essam Ghadafi, and Jens Groth. 2016. Foundations of Fully Dynamic Group Signatures. In ACNS 16International Conference on Applied Cryptography and Network Security (LNCS, Vol. 9696), Mark Manulis, Ahmad-Reza Sadeghi, and Steve Schneider (Eds.). Springer, Cham, 117–136. doi:10.1007/978-3-319-39555-5_7 [9] Julien Bringer, Hervé Chabanne, Roch Lescuyer, and Alain Patey. 2014. Efficient and Strongly Secure Dynamic Domain-Specific Pseudonymous Signatures for ID Documents. In Financial Cryptography and Data Security - 18th International Conference, FC 2014, Christ Church, Barbados, March 3-7, 2014, Revised Selected Papers (Lecture Notes in Computer Science, Vol. 8437), Nicolas Christin and Reihaneh Safavi-Naini (Eds.). Springer, 255–272. doi:10.1007/978-3-662-45472-5_16 [10] Jan Camenisch, Manu Drijvers, and Maria Dubovitskaya. 2017. Practical UC-Secure Delegatable Credentials with Attributes and Their Application to Blockchain. In ACM CCS 2017, Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu (Eds.). ACM Press, 683–699. doi:10.1145/3133956. 3134025 [11] Jan Camenisch, Markulf Kohlweiss, and Claudio Soriente. 2009. An Accumulator Based on Bilinear Maps and Efficient Revocation for Anonymous Credentials. In PKC 2009 (LNCS, Vol. 5443), Stanislaw Jarecki and Gene Tsudik (Eds.). Springer, Berlin, Heidelberg, 481–500. doi:10.1007/978-3-642-00468-1_27 [12] Jan Camenisch, Stephan Krenn, Anja Lehmann, Gert Læssøe Mikkelsen, Gregory Neven, and Michael Østergaard Pedersen. 2016. Formal Treatment of PrivacyEnhancing Credential Systems. In SAC 2015 (LNCS, Vol. 9566), Orr Dunkelman and Liam Keliher (Eds.). Springer, Cham, 3–24. doi:10.1007/978-3-319-31301-6_1 [13] Jan Camenisch and Anja Lehmann. 2015. (Un) linkable pseudonyms for governmental databases. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. 1467–1479. [14] Jan Camenisch and Anja Lehmann. 2017. Privacy-preserving user-auditable pseudonym systems. In 2017 IEEE European Symposium on Security and Privacy (EuroS&P). IEEE, 269–284. [15] Jan Camenisch and Anna Lysyanskaya. 2002. Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials. In CRYPTO 2002 (LNCS, Vol. 2442), Moti Yung (Ed.). Springer, Berlin, Heidelberg, 61–76. doi:10.1007/3540-45708-9_5 [16] Jan Camenisch and Markus Stadler. 1997. Efficient Group Signature Schemes for Large Groups (Extended Abstract). In CRYPTO’97 (LNCS, Vol. 1294), Burton S. Kaliski, Jr. (Ed.). Springer, Berlin, Heidelberg, 410–424. doi:10.1007/BFb0052252 [17] Jan Camenisch and Els Van Herreweghen. 2002. Design and Implementation of The Idemix Anonymous Credential System. In ACM CCS 2002, Vijayalakshmi Atluri (Ed.). ACM Press, 21–30. doi:10.1145/586110.586114 [18] David Cash, Eike Kiltz, and Victor Shoup. 2008. The Twin Diffie-Hellman Problem and Applications. In EUROCRYPT 2008 (LNCS, Vol. 4965), Nigel P. Smart (Ed.). Springer, Berlin, Heidelberg, 127–145. doi:10.1007/978-3-540-78967-3_8 [19] David Chaum. 1985. Security Without Identification: Transaction Systems to Make Big Brother Obsolete. Commun. ACM 28, 10 (1985), 1030–1044. doi:10. 1145/4372.4373 [20] David Chaum and Eugène van Heyst. 1991. Group Signatures. In EUROCRYPT’91 (LNCS, Vol. 547), Donald W. Davies (Ed.). Springer, Berlin, Heidelberg, 257–265. doi:10.1007/3-540-46416-6_22 [21] Özgür Dagdelen. 2013. The cryptographic security of the German electronic identity card. (2013). [22] David Derler and Daniel Slamanig. 2019. Key-homomorphic signatures: definitions and applications to multiparty signatures and non-interactive zeroknowledge. DCC 87, 6 (2019), 1373–1413. doi:10.1007/s10623-018-0535-9 [23] Yves Deswarte and Sébastien Gambs. 2010. A Proposal for a Privacy-preserving National Identity Card. Trans. Data Priv. 3, 3 (2010), 253–276. [24] Whitfield Diffie and Martin E. Hellman. 1976. New Directions in Cryptography. IEEE Transactions on Information Theory 22, 6 (1976), 644–654. doi:10.1109/TIT. 1976.1055638 [25] Taher ElGamal. 1984. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. In CRYPTO’84 (LNCS, Vol. 196), G. R. Blakley and David Chaum (Eds.). Springer, Berlin, Heidelberg, 10–18. doi:10.1007/3-540-39568-7_2
[26] Sebastian Faust, Markulf Kohlweiss, Giorgia Azzurra Marson, and Daniele Venturi. 2012. On the Non-malleability of the Fiat-Shamir Transform. In INDOCRYPT 2012 (LNCS, Vol. 7668), Steven D. Galbraith and Mridul Nandi (Eds.). Springer, Berlin, Heidelberg, 60–79. doi:10.1007/978-3-642-34931-7_5 [27] Amos Fiat and Adi Shamir. 1987. How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In CRYPTO’86 (LNCS, Vol. 263), Andrew M. Odlyzko (Ed.). Springer, Berlin, Heidelberg, 186–194. doi:10.1007/3-540-477217_12 [28] Eduarda S. V. Freire, Dennis Hofheinz, Eike Kiltz, and Kenneth G. Paterson. 2013. Non-Interactive Key Exchange. In PKC 2013 (LNCS, Vol. 7778), Kaoru Kurosawa and Goichiro Hanaoka (Eds.). Springer, Berlin, Heidelberg, 254–271. doi:10.1007/978-3-642-36362-7_17 [29] Shafi Goldwasser, Silvio Micali, and Charles Rackoff. 1985. The Knowledge Complexity of Interactive Proof-Systems (Extended Abstract). In 17th ACM STOC. ACM Press, 291–304. doi:10.1145/22145.22178 [30] Jens Groth. 2015. Efficient Fully Structure-Preserving Signatures for Large Messages. In ASIACRYPT 2015, Part I (LNCS, Vol. 9452), Tetsu Iwata and Jung Hee Cheon (Eds.). Springer, Berlin, Heidelberg, 239–259. doi:10.1007/978-3-66248797-6_11 [31] Jens Groth and Amit Sahai. 2008. Efficient Non-interactive Proof Systems for Bilinear Groups. In EUROCRYPT 2008 (LNCS, Vol. 4965), Nigel P. Smart (Ed.). Springer, Berlin, Heidelberg, 415–432. doi:10.1007/978-3-540-78967-3_24 [32] Lucjan Hanzlik and Daniel Slamanig. 2021. With a Little Help from My Friends: Constructing Practical Anonymous Credentials. In ACM CCS 2021, Giovanni Vigna and Elaine Shi (Eds.). ACM Press, 2004–2023. doi:10.1145/3460120.3484582 [33] Jonathan Katz and Yehuda Lindell. 2014. Introduction to Modern Cryptography, Second Edition. CRC Press. https://www.crcpress.com/Introduction-to-ModernCryptography-Second-Edition/Katz-Lindell/p/book/9781466570269 [34] Markulf Kohlweiss, Mary Maller, Janno Siim, and Mikhail Volkhov. 2021. Snarky Ceremonies. In ASIACRYPT 2021, Part III (LNCS, Vol. 13092), Mehdi Tibouchi and Huaxiong Wang (Eds.). Springer, Cham, 98–127. doi:10.1007/978-3-030-920784_4 [35] Stephan Krenn, Kai Samelin, and Christoph Striecks. 2019. Practical GroupSignatures with Privacy-Friendly Openings. In Proceedings of the 14th International Conference on Availability, Reliability and Security, ARES 2019, Canterbury, UK, August 26-29, 2019. ACM, 10:1–10:10. doi:10.1145/3339252.3339256 [36] Benoît Libert, Khoa Nguyen, Alain Passelègue, and Radu Titiu. 2020. SimulationSound Arguments for LWE and Applications to KDM-CCA2 Security. In ASIACRYPT 2020, Part I (LNCS, Vol. 12491), Shiho Moriai and Huaxiong Wang (Eds.). Springer, Cham, 128–158. doi:10.1007/978-3-030-64837-4_5 [37] Anna Lysyanskaya, Ronald L. Rivest, Amit Sahai, and Stefan Wolf. 1999. Pseudonym Systems. In SAC 1999 (LNCS, Vol. 1758), Howard M. Heys and Carlisle M. Adams (Eds.). Springer, Berlin, Heidelberg, 184–199. doi:10.1007/3-540-465138_14 [38] Vadim Lyubashevsky, Ngoc Khanh Nguyen, and Maxime Plançon. 2022. LatticeBased Zero-Knowledge Proofs and Applications: Shorter, Simpler, and More General. In CRYPTO 2022, Part II (LNCS, Vol. 13508), Yevgeniy Dodis and Thomas Shrimpton (Eds.). Springer, Cham, 71–101. doi:10.1007/978-3-031-15979-4_3 [39] Deepak Maram, Harjasleen Malvai, Fan Zhang, Nerla Jean-Louis, Alexander Frolov, Tyler Kell, Tyrone Lobban, Christine Moy, Ari Juels, and Andrew Miller. 2021. CanDID: Can-Do Decentralized Identity with Legacy Compatibility, SybilResistance, and Accountability. In 2021 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, 1348–1366. doi:10.1109/SP40001.2021.00038 [40] Toru Nakanishi, Hiroki Fujii, Yuta Hira, and Nobuo Funabiki. 2009. Revocable Group Signature Schemes with Constant Costs for Signing and Verifying. In PKC 2009 (LNCS, Vol. 5443), Stanislaw Jarecki and Gene Tsudik (Eds.). Springer, Berlin, Heidelberg, 463–480. doi:10.1007/978-3-642-00468-1_26 [41] Christian Paquin and Greg Zaverucha. 2023. U-Prove Cryptographic Specification V1.1 (Revision 5). Technical Report. Microsoft Corporation, Redmond, WA. [42] Karl-Christian Posch, Reinhard Posch, Arne Tauber, Thomas Zefferer, and Bernd Zwattendorfer. 2011. Secure and Privacy-Preserving eGovernment - Best Practice Austria. In Rainbow of Computer Science (LNCS, Vol. 6570). Springer, 259–269. [43] Thomas Rössler. 2008. Giving an interoperable e-ID solution: Using foreign e-IDs in Austrian e-Government. Comput. Law Secur. Rev. 24, 5 (2008), 447–453. [44] Stammzahlregisterbehörde. 2025. Personal communication. [45] Arne Tauber and Thomas Rössler. 2009. Professional Presentation in Austrian E-Government. In EGOV (LNCS, Vol. 5693). Springer, 388–398. [46] Kevin Theuermann. 2019. Selected Topics IT-Security 1 (E-Government) – Austrian E-Government Infrastructure. https://www.isec.tugraz.at/wp-content/ uploads/2019/09/L08-2019-E-Government-Infrastructure.pdf [47] Bernd Zwattendorfer and Daniel Slamanig. 2013. On Privacy-Preserving Ways to Porting the Austrian eID System to the Public Cloud. In SEC (IFIP AICT, Vol. 405). Springer, 300–314. [48] Bernd Zwattendorfer and Daniel Slamanig. 2015. Design strategies for a privacyfriendly Austrian eID system in the public cloud. Comput. Secur. 52 (2015), 178–193. [49] Bernd Zwattendorfer and Daniel Slamanig. 2016. The Austrian eID ecosystem in the public cloud: How to obtain privacy while preserving practicality. J. Inf.
Stephan Krenn, Doryan Lesaignoux, and Sebastian Ramacher
Secur. Appl. 27-28 (2016), 35–53.
A
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.
A.1
Non-frameability (Theorem 4.1)
Proof. A successful adversary A for non-frameability against our scheme is able to produce a valid proof Π that opens to a honest 𝑢𝑝𝑘. Game 0: This is the original non-frameability game. Game 1: As Game 0 but the generation of parameter for the ZKPoK system and the proofs are simulated in O 𝑁 𝑦𝑚 . By reduction, we can show that an adversary A able to distinguish this replacement can be used by an adversary B to break the simulation sound property of Π. We give B the access to O 𝑁 𝑦𝑚 . All other values are generated honestly. B gives to O 𝑁 𝑦𝑚 a statement and get a proof. Then he passes the proof to A. If A notices a difference, so does B with the same probability. Thus, we have : P(𝐺 0 ) − P(𝐺 1 ) ≤ 𝑀 −𝑆𝑜𝑢𝑛𝑑 (𝜆). 𝐴𝑑𝑣 𝑆𝐼 Π,A Game 2: As Game 1, but we abort if we are not able to extract a witness for a valid statement. That is, we abort if we cannot extract 𝑢𝑠𝑘 ∗, 𝑢𝑝𝑘 ∗, 𝜎 ∗ and 𝑟 ∗ such that the following statements are true: (1)
• Setup∗ (1𝜆 ): 𝑝𝑝 Π , 𝜏 ← S1 (1𝜆 ) 2: return 𝑝𝑝 = {𝑝𝑝 Σ , 𝑝𝑝 Λ , 𝑝𝑝 Π , 𝑝𝑝 Ψ }, 𝜏 ∗ • NymGen𝑢𝑠𝑒𝑟 (𝑢𝑠𝑘, 𝑢𝑝𝑘, 𝑠𝑝𝑝𝑘, 𝑚𝑝𝑘, 𝜏): 1:
′ 1: nym ← Ψ.ShareKey(𝑠𝑝𝑝𝑘, 𝑢𝑠𝑘 )
2: 𝑐 ← Λ.Enc(𝑚𝑝𝑘, 𝑢𝑝𝑘; 𝑟 ) with 𝑟 ←$ R 3: 𝜋 ∗ ← (𝑐, S2 (𝑝𝑝, 𝜏, 𝑥 ∗ )) 4: return nym, 𝜋 ∗
Figure 6: Modification of Setup and NymGen𝑢𝑠𝑒𝑟 for Game 1.
Σ.Verify(𝑚𝑝𝑘, 𝜎 ∗, 𝑢𝑝𝑘 ∗ ) = 1 where 𝜎 ∗ is part of 𝑢𝑠𝑘 ∗
(2) 𝑐 ∗ = Λ.Enc(𝑚𝑝𝑘, 𝑢𝑝𝑘 ∗ ; 𝑟 ∗ )
• O 𝑁 𝑦𝑚 (𝑢𝑝𝑘, 𝑠𝑝𝑝𝑘) :
(3) 𝑢𝑝𝑘 ∗ = 𝜇 (𝑢𝑠𝑘 ′∗ )
4:
(4) nym∗ = Ψ.ShareKey(𝑠𝑝𝑝𝑘, 𝑢𝑠𝑘 ′∗ )
Game 3: As the previous game, but we abort if 𝑢𝑝𝑘 ∗ has not been generated by the central authority, i.e., it does not belong to an honestly generated user; otherwise we abort. Now (1), we know that 𝜎 ∗ is a valid signature on 𝑢𝑝𝑘 ∗ . Therefore, the probability to abort is bounded by the probability that A breaks the unforgeability 𝐸𝑈 𝐹 −𝐶𝑀𝐴 (𝜆). of Σ, and thus P(𝐺 2 ) − P(𝐺 3 ) ≤ 𝐴𝑑𝑣 Σ,A Game 4: As Game 3, but we abort if A creates a proof 𝜋 which point to a user public key that was never generated by the central authority. By assumption, the adversary knows 𝜎 ∗ . Since 𝜎 ∗ is part of 𝑢𝑠𝑘 ∗ and cannot be forged in an efficient time, one can be deduced that the only way for the adversary to know the signature of 𝑢𝑝𝑘 is to corrupt 𝑢𝑠𝑘. P(𝐺 3 ) − P(𝐺 4 ) = 0 follows. This proves that our scheme is non-frameable.
□
Anonymity (Theorem 4.2)
Proof. We define a sequence of games to show that the advantage of an adversary A to break the anonymity experiment is negligible. Game 0: This is the original anonymity game.
∗ nym, 𝜋 ∗ ← NymGen𝑢𝑠𝑒𝑟 (𝑢𝑠𝑘, 𝑢𝑝𝑘, 𝑠𝑝𝑝𝑘, 𝑚𝑝𝑘, 𝜏)
• O 𝐿𝑜𝑅 ({𝑢𝑝𝑘 0, 𝑢𝑝𝑘 1 }, 𝑠𝑝𝑝𝑘) :
By the weak simulation-sound extractability property of our proof system, we know that this can only happen with negligible proba𝑒𝑎𝑘 −𝐸𝑥𝑡 (𝜆). bility, and thus P(𝐺 1 ) − P(𝐺 2 ) ≤ 𝐴𝑑𝑣𝑊 Π,A
A.2
Game 1: As Game 0 but the ZKPoP is simulated in NymGen𝑢𝑠𝑒𝑟 using 𝑆𝐼𝑀 = {S1, S2 }. First, we modify the setup by using S1 to generate the public parameters and a simulated trapdoor 𝜏. Then, we simulate the proof in NymGen𝑢𝑠𝑒𝑟 with S2 and 𝜏 as in Figure 6. We update O 𝐿𝑜𝑅 and O 𝑁 𝑦𝑚 by replacing 𝜋 with a simulated proof 𝜋 ∗ as in Figure 7. We can show by reduction that an adversary A able to distinguish this modification in our scheme can be used by an adversary B to break zero-knowledge property of Π. B is given access to a prove-oracle that output a proof from a statement in input. Then, it passes the statement (the statements used are always legit) to the prove-oracle. Then, B passes the generated proofs to A. If A is able to detect a difference, so does B with the 𝐾 (𝜆). same probability. Thus, we have : P(𝐺 0 ) − P(𝐺 1 ) ≤ 𝐴𝑑𝑣 𝑍Π,A
5:
∗ nym𝑏 , 𝜋 ∗ ← NymGen𝑢𝑠𝑒𝑟 (𝑢𝑠𝑘 𝑏 , 𝑢𝑝𝑘 𝑏 , 𝑠𝑝𝑝𝑘, 𝑚𝑝𝑘, 𝜏)
Figure 7: Modification of line 4 of O 𝑁 𝑦𝑚 and O 𝐿𝑜𝑅 described in Oracles 3 and 5. Game 2: As in Game 1, but we replace 𝑢𝑝𝑘 by 0 in the encryption process inside NymGen𝑢𝑠𝑒𝑟 (see Figure 8). Updates on O 𝐿𝑜𝑅 and O 𝑁 𝑦𝑚 follows and all other values are generated as in the prior hop. Notice that the adversary does not have any access to an open-oracle since this operation is only done by the CA. Thus, It is straightforward to see that, by reduction, if an adversary A able to distinguish this modification in our scheme can be used by an adversary B to break the IND-CPA security of Λ. Thus, we have : 𝐼 𝑁 𝐷 −𝐶𝑃𝐴 (𝜆). P(𝐺 1 ) − P(𝐺 2 ) ≤ 𝐴𝑑𝑣 Λ,A ∗ • NymGen𝑢𝑠𝑒𝑟 (𝑢𝑠𝑘, 𝑢𝑝𝑘, 𝑠𝑝𝑝𝑘, 𝑚𝑝𝑘): ′ 1: nym ← Ψ.ShareKey(𝑠𝑝𝑝𝑘, 𝑢𝑠𝑘 ) ∗ 2: 𝑐 ← Λ.Enc(𝑚𝑝𝑘, 0 ; 𝑟 ) 3: 𝜋 ∗ ← (𝑐 ∗ , S2 (𝑝𝑝 Π , 𝜏, 𝑥 ∗ )) 4: return nym, 𝜋 ∗
Figure 8: Modification of NymGen𝑢𝑠𝑒𝑟 for Game 2.
bPk# : Delegatable Pseudonyms
Game 3: As Game 2, but in NymGen𝑢𝑠𝑒𝑟 , we generate nym by using a non-zero random element 𝛼 ∈ K instead of 𝑢𝑠𝑘 where K is the set in which 𝑢𝑠𝑘 is defined. For consistency, we set up a list 𝐿 that map 𝑢𝑝𝑘 to 𝛼 and is updated when a user public key is used for the first time. Those changes are detailed in Figure 9. We can proceed by reduction to show that if an adversary A is able to distinguish this replacement, A can be used by an adversary B to 𝐼 𝑁 𝐷 (𝜆) break the indistinguishability of Ψ. P(𝐺 2 ) − P(𝐺 3 ) ≤ 𝐴𝑑𝑣 Ψ,A follows. ∗ • NymGen𝑢𝑠𝑒𝑟 (𝑢𝑠𝑘, 𝑢𝑝𝑘, 𝑠𝑝𝑝𝑘, 𝑚𝑝𝑘):
if 𝑢𝑝𝑘 ∉ 𝐿 then 𝛼 ←$ K ∗ 𝐿[𝑢𝑝𝑘] ← 𝛼 else 𝛼 ← 𝐿[𝑢𝑝𝑘] end if nym∗ ← Ψ.ShareKey(𝑠𝑝𝑝𝑘, 𝛼 ) 𝑐 ∗ ← Λ.Enc(0, 𝑚𝑝𝑘; 𝑟 ) 𝜋 ∗ ← (𝑐 ∗, S2 (𝑝𝑝 Π , 𝜏, 𝑥 ∗ )) return nym∗, 𝜋 ∗ Figure 9: Modification of NymGen𝑢𝑠𝑒𝑟 for Game 3. The outputs of O 𝐿𝑜𝑅 are now independent of the challenge bit 𝑏. This proves that our scheme achieves anonymity. □
B
Sequence Diagrams
In Figure 10, 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.
C
Rotation key and Revocation
The signature in the user’s secret key, i.e., 𝜎 ← Σ.Sign(𝑢𝑝𝑘, 𝑚𝑠𝑘 Σ ), could be extended to 𝜎 ← Σ.Sign((𝑢𝑝𝑘, uid, epoch), 𝑚𝑠𝑘 Σ ), where uid is a stable user identifier attached to a user’s public key, and epoch is a counter increasing on a regular basis. Upon authentication, users would now prove knowledge of a valid signature for
the current epoch without disclosing 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 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 [4, 11, 15] or allow/deny lists [40]. 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.
Stephan Krenn, Doryan Lesaignoux, and Sebastian Ramacher
User
CA
User
SP
CA
SP
User creation
User creation
Initial registration in Austria
Initial registration in Austria KeyGen()
KeyGen() (sk, pk) stored
sk stored
Key request
Request key Auth. (sk, pk)
Authentication
Authentication
Request
Request Auth. Request
nym ← NymGen() Auth. Derive bPk from user sk
𝑛𝑦𝑚 Verify(nym)
bPk Verify(bPk)
Access allowed if Accept
Accept or reject Access allowed if Accept
Request pseudonym
Request pseudonym
Request pseudonym for user
Request pseudonym for user
Proof of eligibility
Proof of eligibility
Derive bPk from user sk
Derive bPk from user sk
nym
nym
Compute pseudonym Derive bPk from user sk sp
Figure 10: High-level sequence diagrams for the existing (left) and proposed (right) bPk system.