💻 computer science

PRETTINESS -- Privacy pResErving aTTrIbute maNagEment SyStem

This paper proposes and formally verifies a generic, end-to-end privacy-preserving credential revocation system for the European Digital Identity Wallet, which relies on a single server and secure channels to enable flexible revocation while maintaining security in the universal composability model.

Original authors: Jelizaveta Vakarjuk, Alisa Pankova

Published 2026-03-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jelizaveta Vakarjuk, Alisa Pankova

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a digital wallet filled with your most important documents: your driver's license, your fishing permit, your gym membership, and your medical records. In the current digital world, you are the only one holding this wallet. If you lose your phone, you lose your identity. If your phone gets hacked, your identity is stolen.

The paper you provided introduces PRETTINESS (a clever acronym for Privacy pResErving aTTrIbute maNagEment SyStem). Think of PRETTINESS as a high-tech, invisible vault that helps you manage these documents without ever letting the vault keeper see what's inside.

Here is the breakdown of how it works, using simple analogies:

1. The Problem: The "Backpack" vs. The "Cloud"

Currently, most digital ID systems are like a backpack. You carry all your credentials on your phone.

The Risk: If your phone breaks or gets stolen, you lose everything.
The Privacy Issue: To prove you are who you say you are, you often have to show your whole backpack to a stranger (like a bouncer at a club). They see your name, age, address, and license number all at once, even if they only needed to see your age.

2. The PRETTINESS Solution: The "Invisible Vault"

PRETTINESS suggests moving your digital backpack into a centralized cloud vault (called the AMS or Attribute Management Service).

The Twist: Usually, if you put your stuff in a cloud vault, the vault owner can see everything. PRETTINESS changes the rules. The vault owner (the server) holds your documents, but they are locked in a special box that only you can open.
The Magic: The server helps you manage the box, but it cannot peek inside. It's like a librarian who holds your books but is magically blindfolded so they can't read the titles.

3. How It Keeps You Safe: The "Two-Key Lock"

How do we stop the vault owner from stealing your keys? PRETTINESS uses a Two-Key Lock System (Threshold Cryptography).

Imagine your secret key is a giant combination lock.

Key Part A: You keep this on your phone.
Key Part B: The server keeps this on its computer.

To unlock your documents or sign a digital form, both keys must turn at the same time.

If your phone is stolen: The thief has Key A, but without Key B (the server), they can't open the lock.
If the server is hacked: The hackers have Key B, but without Key A (your phone), they can't open the lock.
The "Clone Detector": If someone tries to copy your phone's memory to use it in two places at once, the system detects the "clone" and locks the vault immediately, like a security guard spotting a duplicate ID card.

4. The "Selective Disclosure" Trick

This is the coolest part. Imagine you are at a bar. The bartender needs to know you are over 21, but they don't need to know your home address or your shoe size.

Old Way: You hand over your whole ID card. The bartender sees everything.
PRETTINESS Way: You ask the Vault to open only the "Age" window. The server helps you prove you are over 21 without ever revealing your name or address. The server doesn't even know which window you opened; it just knows you opened a window.

5. The "Emergency Brake" (Revocation)

Sometimes, you need to cancel a credential. Maybe you lost your license, or the government revokes your fishing permit.

User Revocation: You can press the "Cancel" button on your own credential instantly, without needing to call the government.
Issuer Revocation: If the government revokes your license, they can press "Cancel" from their side.
The Privacy Shield: Even when a license is revoked, the server doesn't know which specific license was cancelled or who cancelled it. It just updates the list of "bad tokens" in the background.

6. The "Covert" Security Promise

The paper assumes the server might be a bit sneaky (a "covert adversary"). It might try to peek or cheat, but only if it thinks it won't get caught.

PRETTINESS builds a "snitch" into the system. If the server tries to hide a revocation or peek at your data, the system creates a digital "smoking gun" that can be shown to a judge later.
Because the server knows it can be caught and proven guilty, it behaves honestly.

Summary

PRETTINESS is a system that lets you store your digital ID in the cloud for safety, but uses advanced math (like a two-person lock) to ensure:

No one (not even the cloud provider) can read your data.
You can prove specific facts (like "I am over 21") without showing your whole ID.
If your phone is stolen, the thief can't use your ID.
If the server tries to cheat, it leaves a trail of evidence.

It's the digital equivalent of having a bank vault that you control, where the bank teller helps you open the door but is legally and magically forbidden from looking at what's inside.

Technical Summary: PRETTINESS - Privacy-Preserving Attribute Management System

1. Problem Statement

The European regulatory landscape, specifically the eIDAS2 regulation and the European Digital Identity (EUDI) Wallet framework, mandates robust privacy guarantees for digital identity management. Key requirements include selective disclosure of attributes, unlinkability of transactions, and secure backup capabilities.

Current proposed solutions (e.g., those in the EUDI Architecture and Reference Framework) largely rely on decentralized models where users store credentials locally on their mobile devices. This approach presents significant challenges:

Storage and Backup: Users are solely responsible for backing up credentials. Loss of the device results in permanent loss of identity data.
Device Constraints: Mobile devices often lack the computational power for complex cryptographic operations required for large-scale attribute management.
Security Risks: If a device is compromised (malware, physical theft), all stored attributes and private keys are exposed.
Revocation Complexity: Efficiently revoking credentials without compromising user privacy or requiring constant online interaction with the issuer is difficult in purely decentralized systems.

There is a need for a system that balances the usability of centralized storage (for backup and management) with the privacy guarantees of decentralized systems (ensuring the central server cannot learn user data or track transactions).

2. Methodology

The authors propose PRETTINESS (Privacy pResErving aTTrIbute maNagEment SyStem), a hybrid architecture that offloads storage and management to a central Attribute Management Service (AMS) while maintaining strict privacy guarantees through advanced cryptographic techniques.

Core Architectural Components

Hybrid Trust Model:
- User: Holds a share of the secret key and a PIN.
- AMS (Server): Stores encrypted credentials and assists in operations but is assumed to be covertly corrupted. This means the server may attempt to cheat (e.g., hide a revocation) but will not do so if there is a non-negligible probability of being detected and proven to a third party.
- Issuer: Issues credentials and can revoke them.
- Relying Party (RP): Verifies credentials.
Cryptographic Building Blocks:
- Threshold Cryptography: The system utilizes threshold signatures and threshold decryption. The secret key is split between the user's device and the AMS.
  - Blindness: Operations are "blind," meaning the AMS participates in signing/decryption without learning the specific message (credential attributes) or the context (which credential is being presented).
  - Clone Detection: The system employs a mechanism to detect if a user's device has been cloned. If the server detects simultaneous signing attempts from different devices using the same key share, it can block further operations, protecting against device theft.
- Selective Disclosure: Attributes are stored in encrypted form on the AMS. During presentation, the user decrypts only the specific attributes requested by the RP, leaving others encrypted.
- Revocation Mechanism: Uses a specialized functionality ( $F_{rev}$ $F_{r e v}$ ) where both the user and the issuer hold revocation tokens.
  - The AMS maintains the revocation list but cannot link a specific revocation to a specific user unless it colludes with the RP or the user is corrupted.
  - Cheating Detection: If the AMS attempts to silence a revocation (e.g., hide that a license was revoked), the user and the verifier can jointly prove this cheating to an external judge.
Formal Security Model:
- The system is modeled using the Universal Composability (UC) framework.
- An Ideal Functionality ( $F_{ideal}$ ) is defined to capture the desired security properties (completeness, soundness, unforgeability, selective disclosure, and revocation).
- A simulator is constructed to prove that the real protocol is indistinguishable from the ideal functionality, even in the presence of an adversary who can corrupt the user (up to certain levels) or the AMS (covertly).

Workflow Overview

Issuance: The user requests attributes. The AMS facilitates the connection with the Issuer. The Issuer encrypts attributes under the user's public key (split between user and AMS) and signs the credential. The AMS stores the encrypted blob.
Presentation: The user requests a presentation. The AMS assists in decrypting only the requested attributes and generating a signature for the RP. The AMS sees the fact of a presentation but not the content or the identity of the RP (unless colluding).
Revocation: The user or Issuer can revoke a credential by invalidating a token. The AMS updates the revocation list but cannot determine which user's credential was revoked unless it colludes with the party that presented it.

3. Key Contributions

Privacy-Preserving Centralized Storage: PRETTINESS is the first system to successfully offload credential storage to a central server without compromising user privacy against that server. It solves the "backup vs. privacy" dilemma.
Covert Adversary Model for AMS: The paper introduces a practical threat model where the AMS is "covertly corrupted." It assumes the server is reputable and will not cheat if it risks being caught and proven guilty, rather than assuming it is fully honest (honest-but-curious) or fully malicious.
Server-Supported Threshold Cryptography with Clone Detection: The integration of blind threshold signatures and decryption with clone detection mechanisms ensures that even if a device is stolen, the attacker cannot use the credentials without the server's cooperation, and the server can detect and block the attack.
Formal UC Security Proof: The system is rigorously proven secure in the Universal Composability model, providing strong guarantees that the protocol remains secure even when composed with other protocols.
Flexible Revocation: Supports revocation by both the user and the issuer without requiring the issuer to track user presentations, preserving unlinkability.

4. Results and Efficiency Evaluation

The authors conducted a comprehensive efficiency analysis based on benchmarks of the underlying cryptographic primitives (RSA, SHA-256, and specific threshold protocols).

Scenario: 100 credentials per user, 10 attributes per credential, 1 million revoked tokens in the system.
Performance Metrics:
- Issuing: ~8.1 seconds (dominated by decryption of attributes to verify content).
- Presentation: ~5.7 seconds (dominated by decryption of selected attributes and revocation checks).
- Verification: ~4.7 seconds.
- Database Update (Revocation List): ~0.7 seconds for the user (if optimized to download only relevant entries) but up to 32MB of data transfer for a full list update.
Bottlenecks:
- Network Latency: The primary overhead is communication between the user, AMS, and Issuer.
- Revocation List Size: Downloading the full revocation database (32MB for 1M tokens) is a bottleneck for users on poor networks. The authors propose optimizing this by allowing users to download only entries relevant to them.
Comparison: The system is shown to be feasible for practical use, with computation times in the range of seconds, which is acceptable for identity verification scenarios (e.g., border control, building access).

5. Significance

The PRETTINESS system addresses a critical gap in the implementation of the European Digital Identity Wallet (EUDI).

Regulatory Compliance: It directly addresses the requirements of eIDAS2 regarding backup, selective disclosure, and privacy, offering a solution that is more robust than the currently proposed decentralized-only approaches.
Practicality: By leveraging a central server for storage and management, it reduces the burden on user devices and ensures data availability (backup), which is a major pain point for current decentralized identity solutions.
Security Innovation: The use of covert adversaries and clone detection provides a realistic security model that balances the need for a trusted infrastructure with strong privacy guarantees, moving beyond the theoretical "honest-but-curious" assumption.
Future Impact: This work lays the groundwork for scalable, privacy-preserving identity management systems that can be deployed across the EU and potentially globally, ensuring that users retain control over their data while benefiting from centralized infrastructure reliability.

In conclusion, PRETTINESS demonstrates that it is possible to build a highly secure, privacy-preserving attribute management system that utilizes a central server for storage and management without sacrificing user privacy or control, provided that advanced cryptographic techniques and a realistic threat model are employed.