PRIMA: Privacy-Preserving Identity and Access Management at Internet-Scale

Muhammad Rizwan Asghar, Michael Backes, Milivoj SimeonovskiICC 2016 · OpenReview

TL;DR

This paper introduces PRIMA, a novel system for federated identity management that significantly enhances user privacy. PRIMA achieves this by eliminating direct communication between identity providers and service providers during authentication, preventing user profiling and enabling controlled disclosure of personal information.

What Problem Does This Paper Address?

The internet's shift towards federated identity management, where a single identity provider (IdP) handles user credentials for multiple service providers (SPs), offers convenience. However, this model creates a significant privacy risk: IdPs can track users' online activities across various services, potentially profiling them and selling this data. Current solutions like OpenID and OpenID Connect, while improving usability, still require IdPs to be involved in every authentication, making user activity traceable. This paper tackles the challenge of maintaining the benefits of federated identity while robustly protecting user privacy from potentially "curious" IdPs.

Methods

PRIMA is a universal credential-based authentication system. Its core innovation lies in decoupling the authentication process from direct IdP-SP interaction. Key techniques include:

  • Credential Issuance: The IdP issues a unique digital credential (dID) to the user, containing signed attributes and verification keys. This credential is self-contained and doesn't require the IdP's presence for verification by the SP.
  • Controlled Disclosure: PRIMA leverages cryptographic constructions (inspired by Oblivion) to allow users to selectively disclose attributes. This means users can prove they meet certain criteria (e.g., "over 18") without revealing their exact age or other sensitive details.
  • Inference Engine: A novel module that transforms raw user attributes into logical proofs. This allows users to satisfy SP requirements (like age verification) without exposing the underlying data, further enhancing privacy.
  • Decoupled Authentication: During authentication, the user presents their credential to the SP. If the SP requires attribute verification, the user requests a signed nonce from the IdP (which is then passed to the SP). Crucially, the IdP signs the nonce without knowing which SP the user is authenticating with, thus breaking the link.

Datasets

Not discussed in the paper. The evaluation is based on a custom experimental setup.

Key Insights and Ideas

  • Breaking the IdP-SP Link is Crucial for Privacy: The paper highlights that the fundamental privacy threat in federated identity stems from the IdP's ability to correlate authentication requests with specific SPs. PRIMA's design directly addresses this by ensuring the IdP never knows the target SP during the authentication phase.
  • Selective Disclosure is More Than Just Hiding Data: The inference engine is a key differentiator, enabling users to prove conditions about their attributes (e.g., "age > 18") rather than just revealing specific values. This is a more sophisticated form of privacy protection.
  • Incremental Deployability is Key: The authors emphasize that PRIMA is designed to complement existing federated identity infrastructure, making adoption more feasible without requiring a complete overhaul.

Key Results

The performance analysis demonstrates PRIMA's efficiency and scalability:

  • IdP Performance: An IdP can process between 1,426 and 3,332 authentication requests per second, depending on the key size (1024-bit vs. 2048-bit).
  • Attribute Certification: The IdP takes approximately 2.64 ms (1024-bit key) to 18.92 ms (2048-bit key) per attribute for signing during the registration phase.
  • Attribute Verification: The SP can verify 50 attributes in about 0.67 ms (1024-bit key) to 1.53 ms (2048-bit key).

These results suggest that PRIMA is efficient enough for internet-scale deployment.

Limitations and Future Work

  • Honest-but-Curious IdP Assumption: The system assumes the IdP is honest in its operations but may be curious about user behavior. The SP is not fully trusted.
  • User Space Not Compromised: The system assumes the user's device and credentials are not compromised.
  • Future Work: The authors plan to conduct user studies to assess the system's usability and formally define its security and privacy properties. They also aim to explore more advanced revocation mechanisms.

Summary updated

Abstract

The management of identities on the Internet has evolved from the traditional approach (where each service provider stores and manages identities) to a federated identity management system (where the identity management is delegated to a set of identity providers). On the one hand, federated identity ensures usability and provides economic benefits to service providers. On the other hand, it poses serious privacy threats to users as well as service providers. The current technology, which is prevalently deployed on the Internet, allows identity providers to track the user's behavior across a broad range of services. In this work, we propose PRIMA, a universal credential-based authentication system for supporting federated identity management in a privacy-preserving manner. Basically, PRIMA does not require any interaction between service providers and identity providers during the authentication process, thus preventing identity providers to profile users' behavior. Moreover, throughout the authentication process, PRIMA provides a mechanism for controlled disclosure of the users' private information. We have conducted comprehensive evaluations of the system to show the feasibility of our approach. Our performance analysis shows that an identity provider can process 1,426 to 3,332 requests per second when the key size is varied from 1024 to 2048-bit, respectively.
BibTeX
@inproceedings{asghar2016prima,
  author = {Muhammad Rizwan Asghar and Michael Backes and Milivoj Simeonovski},
  title = {{PRIMA: Privacy-Preserving Identity and Access Management at Internet-Scale}},
  booktitle = {ICC},
  year = {2016},
  url = {https://openreview.net/forum?id=0WsBfpX_py},
}
Figure