bpK#: Delegatable Pseudonyms And Their Applications to National eID Systems

Source: arXiv:2605.30212 · Published 2026-05-28 · By Stephan Krenn, Doryan Lesaignoux, Sebastian Ramacher

TL;DR

This paper addresses privacy, availability, and authenticity challenges in Austria's national electronic identity (eID) system pseudonyms, called bPks, which rely on a fully centralized architecture. The authors propose bPk#, a distributed and delegatable pseudonym system where users and certain authorized service providers can locally compute verifiable pseudonyms, significantly reducing metadata leakage to the central authority and improving availability. Their system maintains all key functionalities required by the Austrian legal framework, including centralized key generation, pseudonym linking, and controlled deanonymization, but adds formal provable security guarantees absent in the prior design.

The paper provides the first formal framework defining delegatable pseudonym systems, specifying correctness, privacy, authenticity, and delegation properties. It then presents a generic cryptographic construction combining digital signatures, zero-knowledge proofs, and non-interactive key exchange protocols, and proves its security under well-defined assumptions. A concrete instantiation using pairing-based primitives achieves practical efficiency with pseudonym generation and verification each requiring under 10 milliseconds on midrange 2022 hardware. Overall, the work is a major step forward both in the formal security foundations and practical deployment readiness of national eID pseudonym architectures that balance privacy, availability, and legal mandates.

Key findings

• The current Austrian bPk system performs over 2.5 billion queries annually on a fully centralized authority, presenting availability and privacy risks.
• bPk# enables users to delegate pseudonym generation locally with verifiable proofs, reducing metadata exposed to the central authority.
• Certain service providers, e.g., public agencies, can also generate pseudonyms within their domain, enhancing resilience to central authority outages.
• Formal security definitions for delegatable pseudonym systems are introduced, covering authenticity, privacy against collusion, and delegation restrictions.
• Concrete instantiation using pairing-based cryptography produces pseudonyms and validity proofs in under 5 ms on average; verification takes under 10 ms (midrange 2022 hardware).
• The system supports mandatory legal features: central key generation at user registration, pseudonym linking by authority, and deanonymization in abuse cases.
• The design achieves non-frameability ensuring malicious users cannot forge pseudonyms for others' identities, supported by provable EUF-CMA security of signature scheme.
• Privacy guarantees prevent colluding service providers from linking pseudonyms across domains unless authorized translation by the central authority occurs.

Threat model

The adversary can corrupt subsets of users or service providers but does not control the central authority, which remains fully trusted and legally accountable. The adversary aims to forge pseudonyms linked to identities they do not own, link pseudonyms across domains without authorization, or learn metadata of authentication patterns. Service providers are considered partially trusted entities with domain-restricted key access. The model excludes attackers capable of breaking underlying cryptographic primitives or corrupting the master key.

Methodology — deep read

The authors begin by analyzing the current Austrian pseudonym system (bPk), its centralized design, and mandated functionalities including central key generation at birth, domain-specific pseudonym derivation via encrypt-then-hash, linking by authority, and deanonymization for abuse cases. They identify limitations regarding availability (single point of failure), privacy (central authority learns authentication patterns), and authenticity (users could generate unauthentic pseudonyms that cannot be easily verified by service providers).

They then define a formal framework modeling delegatable pseudonym systems with explicit syntax: system-wide public parameters; master secret/public keys generated by the central authority; user and service provider keypairs derived from the master secret key; algorithms for user and SP pseudonym generation (NymGen) and verification (NymVf); and deanonymization (Open) by the central authority. The threat model assumes a central authority trusted to generate keys, adversaries that may corrupt users or service providers but not the authority itself; attack goals include forging pseudonyms and linking user pseudonyms without authorization.

Their generic cryptographic construction composes standard primitives: digital signatures to bind pseudonyms to user keys, non-interactive zero-knowledge proofs to prove pseudonym formation correctness without revealing secrets, and non-interactive key exchange (NIKE) protocols to derive shared symmetric keys between users and service providers enabling pseudonym computation. The system ensures authenticity through unforgeable signatures and proof soundness, privacy via encryption and zero-knowledge, and delegation by restricting SP pseudonym computations to their own domain keys.

The training regime corresponds to setting security parameters and instantiating building blocks under standard hardness assumptions (e.g., discrete log in bilinear groups) with proofs in the random oracle model. They implement a concrete variant using pairing-based cryptography, including BLS signatures and efficient NIZK proof systems.

They evaluate efficiency on midrange 2022 hardware measuring average pseudonym generation time under 5 ms and verification under 10 ms, demonstrating practical suitability. Security proofs rigorously show indistinguishability, soundness, and unforgeability properties formalized in the definitions. The code for the reference implementation was released alongside the paper, allowing reproducibility.

An end-to-end example: Upon birth, a user's keypair is generated by the authority. When authenticating to a service provider, the user locally derives a pseudonym for that domain using their secret key and the SP's public key via the NIKE to get a shared secret. The user then constructs a validity proof for this pseudonym via a NIZK and sends it alongside the pseudonym. The SP verifies the proof using the user's public key and their own keys, accepting only valid pseudonyms. If needed, the authority can deanonymize or translate pseudonyms by reversing the process with the master secret key.

The methodology is rigorous in defining cryptographic primitives, modeling legal/functional requirements, and clearly separating trust assumptions. The paper acknowledges that certain tradeoffs exist between decentralization and legal compliance given the mandatory central authority involvement. Some details on deployment integration and handling revocation/key rotation appear later but are not detailed here.

Technical innovations

• Formal definition and modeling of delegatable pseudonym systems combining central authority and user/SP local pseudonym generation with authenticity proofs.
• A generic cryptographic construction using digital signatures, non-interactive zero-knowledge proofs, and non-interactive key exchange enabling delegation and verifiable pseudonym formation.
• Provision of the first formal security proofs of pseudonym authenticity, privacy, non-frameability, and delegation under realistic threat models for national eID pseudonyms.
• Concrete instantiation with efficient pairing-based cryptographic building blocks achieving sub-10 ms pseudonym generation and verification times on midrange hardware.

Baselines vs proposed

• Current Austrian bPk centralized system: availability limited by single authority; metadata fully known by authority vs proposed bPk#: distributed delegation reduces metadata exposure and improves availability.
• Pseudonym generation latency prior: not specified, but centralized and reliant on authority response vs proposed: ~5 ms generation and ~10 ms verification on standard 2022 hardware.
• No formal security definitions or proofs existed prior vs formal provable security guarantees in bPk# construction.

Limitations

• The solution requires trust in a central authority for master key generation and key escrow, limiting full decentralization and user self-sovereignty.
• No built-in revocation or key rotation mechanisms are integrated, though Section 6 mentions discussion of these issues.
• The design assumes honest key generation for service providers and users; rogue key attacks or insider compromise are not fully mitigated.
• The formal security proofs are in the random oracle model and depend on standard assumptions which may not capture all real-world attack vectors.
• The approach is tailored to legal constraints of Austrian eID; adaptation to other countries may require regulatory changes.
• No empirical adversarial testing or measurement under network or denial-of-service conditions was reported.

Open questions / follow-ons

• How to efficiently integrate revocation and key rotation into the delegatable pseudonym framework while preserving privacy and authenticity?
• Can the model be extended to reduce reliance on a single central authority or enable distributed key generation meeting legal mandates?
• How does the system perform under real network conditions, scaling to billions of requests, and resilience against denial-of-service attacks?
• What are the concrete auditing and legal enforcement mechanisms to regulate delegated service provider key usage and prevent misuse?

Why it matters for bot defense

For bot-defense and CAPTCHA practitioners, bPk# offers valuable insights on constructing privacy-preserving, delegatable pseudonym schemes with strong formal security guarantees. Its approach to limiting metadata exposure to a central authority while maintaining verifiable authenticity of user identifiers is relevant for designing authentication flows resistant to large-scale abuse or data leakage. The delegation capability to domain-specific service providers also suggests models for partial trust and dynamic pseudonym assignment in federated authentication systems.

Although designed for national eID systems, the cryptographic constructions combining zero-knowledge proofs and NIKE protocols to prove authenticity of delegated identity tokens could inspire robust bot detection and defense mechanisms, especially where privacy and auditing need balance. However, practical integration would require addressing revocation and real-time verification latency in high-throughput environments typical of CAPTCHA usage.

Cite

@article{arxiv2605_30212,
  title={ bpK#: Delegatable Pseudonyms And Their Applications to National eID Systems },
  author={ Stephan Krenn and Doryan Lesaignoux and Sebastian Ramacher },
  journal={arXiv preprint arXiv:2605.30212},
  year={ 2026 },
  url={https://arxiv.org/abs/2605.30212}
}

Read the full paper

• arXiv:2605.30212 (abstract)
• arXiv:2605.30212 (PDF)