UPPRESSO: Untraceable and Unlinkable Privacy-PREserving Single Sign-On Services

arXiv:2110.10396 · cs.CR · Submitted 2021-10-20 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "UPPRESSO: Untraceable and Unlinkable Privacy-PREserving Single Sign-On Services".

Jane: The paper was written by Chengqian Guo, Jingqiang Lin, Quanwei Cai, Wei Wang, Wentian Zhu et al. from Yuncheng Vocational and Technical University, China and School of Cyber Security, University of Science and Technology of China and Beijing Zitiao Network Technology Co., Ltd, China and School of Computer Science & Technology, University of Chinese Academy of Sciences and JD.com Silicon Valley R&D Center, USA and Department of Electrical Engineering & Computer Science, the University of Kansas, USA and Beijing Certification Authority Co., Ltd, China.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Jane: We also have Lu with us today — senior AI researcher at Tsinghua.

Tom: We also have Meng with us today — lead engineer at a mysterious AI startup.

Jane: We also have Lalam with us today — the in-house Large Language Model.

Tom: Alright, let's get started.

Paper discussion segment 1: Tom: Alright, we're looking at a paper called "UPPRESSO: Untraceable and Unlinkable Privacy-PREserving Single Sign-On Services." The title itself is quite a mouthful, but it’s hitting on that massive tension between convenience and privacy.

Jane: It really is, Tom. Think about how many times you've clicked "Sign in with Google" or "Sign in with Apple" just to avoid making a new account. It's incredibly easy, but the trade-off is that those providers can see every single site you visit whenever you use their login.

Tom: Exactly, and this research comes from a huge group of experts across China and the US, including folks from the University of Science and Technology of China and JD.com. They're tackling both sides of that coin: the provider tracking your movements and different sites being able to collude to build a profile on you.

Jane: So, instead of just saying "privacy is hard," they’re proposing a way to keep your identity hidden even from the very service that's helping you log in. It sounds like they want to decouple who you are from where you're going.

Lu: That decoupling is where the real magic happens in this research! They aren't just adding a layer of encryption; they are fundamentally changing how identities are constructed so that no single entity has the full picture. Imagine a digital world where your presence is like a shadow that changes shape depending on which door you walk through.

Meng: I see the vision, Lu, but I'm thinking about the actual implementation details here. If we change how identity works, how does this actually integrate with existing web standards like OIDC or SAML? It would be useless if every developer had to rewrite their entire authentication stack from scratch just to use this.

Lalam: The beauty is that it aims to work within the current cultural landscape of the internet. If we can achieve this without forcing users to install weird browser extensions, we're looking at a massive shift in how much autonomy people feel they have online. It could move us away from this era of constant surveillance toward a more respectful digital social contract.

Tom: That's a huge point, Meng, because the paper claims it works on standard browsers without any plug-ins. We should look at how they actually pull that off in the next segment.

Paper discussion segment 2: Jane: Now that we know what they're aiming for, let's talk about how UPPRESSO actually functions according to their summary. They use this clever idea of identity transformations to create these "ephemeral" identities.

Tom: Right, so instead of sending your real ID to a website, the system uses math to create a temporary version of you that only works for that specific login and that specific site. It’s like using a different disposable key for every single door in a building.

Jane: And because these keys are generated through these complex transformations, even if two different websites compare notes, they can't figure out they're looking at the same person. The paper calls this preventing "RP-based identity linkage."

Lu: It’s brilliant because it exploits the math of elliptic curves to ensure that the relationship between your real self and these temporary keys is one-way. You can go from a real ID to a fake one, but you can't work backward from the fake one to find out who is actually behind it!

Meng: I was looking at their methodology for this, and they’re using an "identity-transformation approach." They use the user's secret and some random numbers to calculate these pseudo-identities. It’s a heavy lift for a browser, but they seem to have optimized it quite well.

Lalam: This is going to change the way we think about digital footprints. If every interaction is unique and disconnected, the very concept of a "persistent online profile" starts to crumble, which empowers individuals to explore different communities without fear of being tracked back to their primary identity.

Tom: They even tested this! They built a prototype on top of MITREid Connect, which is an open-source system people actually use.

Jane: And the results showed that it works with reasonable overhead, meaning it won't make your computer crawl while you're trying to log in. Let's move on to the specific improvements they suggest over previous attempts.

Paper discussion segment 3: Tom: So, we’ve heard about the "what," but let’s talk about why this is better than what we already have. They mention that older solutions usually only solved one half of the problem—either they stopped the provider from tracking you, or they stopped sites from linking you, but rarely both.

Jane: That's true, Tom. Some older methods required a "trusted third party" or a special server to act as a middleman to hide your identity. UPPRESSO tries to do it all within the user's own browser using these scripts.

Tom: And they specifically address that "honest-but-curious" provider problem. That’s the idea that the login provider isn't necessarily trying to hack you, but they are definitely watching everything you do for data collection.

Jane: By using a "user-r script" and a "user-i script," they split the communication. The user's browser handles the heavy lifting of calculating these pseudo-identities so that the IdP only sees an ephemeral version of the user, not their real identity or where they are actually going.

Lu: This is a massive leap forward because it removes that extra "trusted server" requirement! By making the math happen locally in the browser, you eliminate a whole potential point of failure and surveillance. It’s decentralized intelligence at its finest!

Meng: From an engineering standpoint, I'm impressed by how they handle the "RP designation." They ensure that a token meant for Website A can't be intercepted and used to log into Website B. They do this by incorporating the RP's identity into the math itself. It’s a very robust way to prevent replay attacks.

Lalam: We are moving toward a future where privacy isn't an "extra" feature you have to hunt for in your settings, but is baked into the very fabric of how we move through digital spaces. This protocol could be the blueprint for a more private internet culture.

Tom: They even proved it mathematically with these complex security games involving ECDLP and ECDDH problems to show that even if companies collude, they're still stuck.

Jane: It's a very thorough piece of work, so let's bring this all together for our wrap-up.

Conclusion: Tom: We’ve covered a lot of ground today with "UPPRESSO: Untraceable and Unlinkable Privacy-PREserving Single Sign-On Services." It’s a sophisticated approach to one of the oldest problems in the digital age.

Jane: It really is. They've shown that you can have the convenience of single sign-on without giving up your entire online life to a handful of massive corporations.

Lu: This research opens up so many creative possibilities for anonymous social interaction and secure digital voting! I can't wait to see how this evolves.

Meng: It’s a solid, practical contribution that actually considers the constraints of modern web browsers and existing protocols. That's what makes it meaningful for real-world deployment.

Lalam: Ultimately, this is about restoring agency to the individual and ensuring that our digital identities remain ours alone, regardless of how we choose to use them.

Tom: Thanks for joining us on this deep dive! We'll be back next time with another look at what's coming off the arXiv presses.

Jane: See you then! Goodbye!

Chengqian Guo, Jingqiang Lin, Quanwei Cai, Wei Wang, Wentian Zhu, Jiwu Jing, Qiongxiao Wang, Bin Zhao, Fengjun Li

Yuncheng Vocational and Technical University, China · School of Cyber Security, University of Science and Technology of China · Beijing Zitiao Network Technology Co., Ltd, China · School of Computer Science & Technology, University of Chinese Academy of Sciences · JD.com Silicon Valley R&D Center, USA · Department of Electrical Engineering & Computer Science, the University of Kansas, USA · Beijing Certification Authority Co., Ltd, China

cs.CR

Submitted: 2021-10-20

Updated: 2026-09-22

Project page: http://mitreid-connect.github.io/index.html

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 92/100

The gist: "Single sign-on (SSO) allows a user to maintain only the credential for an identity provider (IdP) to log into multiple relying parties (RPs).

Key concepts

UPPRESSO: A system proposing untraceable and unlinkable privacy-preserving single sign-on services. It aims to hide a user's identity from login providers while allowing them to access services.
Identity Transformations: The method used by UPPRESSO where the system uses math to create temporary, pseudo-identities for specific logins and sites. This makes it difficult for different websites to link those temporary identities back to the user's real identity.
RP-based Identity Linkage Prevention: A security feature ensuring that a token meant for one website cannot be intercepted and used to log into another. UPPRESSO incorporates the Relying Party's identity into the mathematical calculations to prevent this linkage.

Terminology

Nadia — 11× in this paper · explained in 2 episodes
Elias — 10× in this paper · explained in 2 episodes
Verification — 10× in this paper · explained in 2 episodes
Core — 4× in this paper · explained in 2 episodes
Adversarial scenarios — 2× in this paper · explained in 1 episode
ACM Conference on Computer and Communications Security — 1× in this paper
Benchmarking — 1× in this paper · explained in 3 episodes
European Symposium on Research in Computer Security — 1× in this paper
Federated Learning — 1× in this paper · explained in 15 episodes
National Institute of Standards and Technology — 1× in this paper

Summary

"Single sign-on (SSO) allows a user to maintain only the credential for an identity provider (IdP) to log into multiple relying parties (RPs). However, SSO introduces privacy threats, as (a) a curious IdP could track a user’s all visits to RPs, and (b) colluding RPs could learn the user’s online profile by linking her identities across these RPs. This paper presents a privacy-preserving SSO scheme, called UPPRESSO, to protect an honest user’s online profile against (a) an honest-but-curious IdP and (b) malicious RPs colluding with other users. UPPRESSO proposes an identity-transformation approach to generate untraceable ephemeral pseudo-identities for an RP and a user from which the target RP derives a permanent account for the user, while the transformations also provide unlinkability. This approach protects the identities of the user and the target RPs in a login flow, while working compatibly with widely-deployed SSO protocols and providing services accessed from a commercial-off-the-shelf browser without plug-ins or extensions. We built a prototype of UPPRESSO on top of MITREid Connect, an open-source SSO system. The extensive evaluations show that it fulfills the security and privacy requirements of SSO with reasonable overheads."

"UPPRESSO implements privacy-preserving SSO that ensures security, while preventing both IdP-based login tracing and RP-based identity linkage. These requirements are satisfied through transformed identities in the identity tokens. In UPPRESSO a user initiates the login by negotiating an ephemeral pseudo-identity PIDRP with the target RP and sending an identity-token request for PIDRP to an IdP. After successfully authenticating the user as IDU, the IdP calculates an ephemeral PIDU based on IDU and PIDRP and then issues an identity token that binds PIDU and PIDRP, instead of IDU and IDRP. On receiving the token, the RP transforms PIDU into an account that is unique at each RP but identical across multiple logins to this RP. The relationships among the (pseudo-)identities are depicted in Figure 2: Red and green blocks represent permanent and ephemeral (pseudo-)identities, respectively, and labeled arrows denote the transformations of (pseudo-)identities."

"The identity transformations are as follows:

• FAcct∗(IDU, IDRP) = Acct, determining a user’s account at an RP. Given IDU and IDRP, Acct is unique to other accounts at this RP.

• FPIDRP(IDRP) = PIDRP, calculated by the user. In the IdP’s view, FPIDRP is a one-way function and PIDRP is indistinguishable from random variables.

• FPIDU(IDU, PIDRP) = PIDU, calculated by the IdP. In the target RP’s view, FPIDU is a one-way function and PIDU is indistinguishable from random variables.

• FAcct(PIDU, PIDRP) = Acct, calculated by the target RP. That is, in the user’s multiple logins visiting the RP, Acct = FAcct∗(IDU, IDRP) is always derived."

"The UPPRESSO protocol involves several stages:

System Initialization: An IdP generates a key pair (SK, PK) to sign and verify identity tokens and RP certificates.
RP Registration: Each RP registers at the IdP to obtain IDRP and its RP certificate CertRP as follows: 1. An RP pre-installs PK by trusted means. It sends a registration request, including the endpoint to receive identity tokens and other information. 2. The IdP randomly selects r ∈ Zn and assigns a unique point [r]G to the RP as its identity. IDRP = [r]G is publicly known; r is known to nobody due to the ECDLP. 3. The IdP signs CertRP = [IDRP, EnptRP, ∗]SK.
User Registration: Each user sets up her unique username and corresponding credential for the IdP. The IdP assigns a unique random identity IDU = u to the user (known only to the IdP).
SSO Login:

RP Identity Transformation: The user-i script chooses a random number t ∈ Zn and sends it to the user-r script through postMessage. The user-r script forwards t to the RP. The RP verifies t and replies with CertRP and requested attribute scope. The user-i script verifies CertRP, extracts IDRP and EnptRP, and calculates PIDRP = [t]IDRP = [tr]G.
Identity-Token Generation: The user-i script sends an identity-token request for PIDRP to the IdP. The IdP authenticates the user, calculates PIDU = [IDU]PIDRP = [utr]G, and signs [PIDRP, PIDU, Issuer, Validity, Attr]SK.
Acct Calculation: The RP receives the identity token and calculates Acct = [t−1 mod n]PIDU = [u r]G."

"Experimental evaluations show that UPPRESSO introduces reasonable overheads. In a virtual private cloud setting (IdP, RP, and user browsers deployed on the cloud), the average time for an SSO login is 174 ms. When accessed remotely (user browser running locally to visit cloud servers), the average time is 421 ms."

Identity-token requesting: MITREid Connect (63 ms), UPPRESSO (179 ms), SPRESSO (190 ms).
Identity-token generation: MITREid Connect (50 ms), UPPRESSO (50 ms), SPRESSO (200 ms).
Identity-token acceptance: MITREid Connect (63 ms), UPPRESSO (51 ms), SPRESSO (150 ms).
Total: MITREid Connect (312 ms), UPPRESSO (471 ms), SPRESSO (510 ms). [Note: The text provides two sets of values for total time; the summary reflects the stated findings in Section 6.2 and Figure 6]."

The UPPRESSO prototype implemented identity transformations on the NIST P256 elliptic curve where n ≈ 2 256, with RSA-2048 and SHA-256 serving as the digital signature and hash algorithms, respectively. "The IdP was developed on top of MITREid Connect, a Java implementation of OIDC, with minimal code modifications. Only three lines of code were added for calculating PIDU and 20 lines were added to modify the method of forwarding identity tokens." We developed a Java-based RP SDK with about 500 lines of code on the Spring Boot framework. The cryptographic computations such as CertRP verification and PIDRP negotiation are performed based on jsrsasign, an open-source JavaScript library.

Improvements for AI systems

To improve AI systems using the principles from UPPRESSO, I would focus on architecting a new class of privacy-preserving, decentralized identity management for autonomous agents and distributed AI ecosystems.

Here are the specific improvements and their capabilities:

Integrated Identity Transformation Layer for Multi-Agent Systems (MAS)

By implementing the Identity Transformation approach (using ephemeral pseudo-identities like PIDU and PIDRP), I would replace static API keys or fixed agent IDs with a dynamic identity layer.

Improved AI System Capability: An AI agent could interact with multiple specialized service providers (e.g., a medical database, a travel booking engine, and a financial tool) without any single provider being able to link the agent's activities across services. The agents would maintain unlinkable profiles while still allowing each service to recognize them as a returning user via locally-unique accounts (Acct).

Zero-Knowledge Attribute Verification for Federated Learning

I would adapt the UPPRESSO concept of Selective IdP-confirmed attribute provision to the data-sharing layer of federated learning.

Improved AI System Capability: When training models on sensitive user data, the central aggregator could verify that a participant meets specific criteria (e.g., user is over 18 or user resides in a specific jurisdiction) using transformed, ephemeral credentials. This allows for high-fidelity data filtering and demographic-aware training without the central server ever receiving the actual raw attributes or being able to trace which specific user provided which data point.

Privacy-Preserving User Agent Orchestration for LLM Agents

I would implement the UPPRESSO User-R/User-I script architecture within an LLM agent's browser/execution environment to manage cross-origin communications via the postMessage API and targetOrigin restrictions.

Improved AI System Capability: An autonomous LLM agent tasked with web navigation could access sensitive third-party websites without leaking its primary identity or its browsing history to the Identity Provider (IdP). The system would prevent IdP-based login tracing, meaning a centralized identity service used by the agent cannot build a behavioral profile of the agent's interests, political leanings, or consumer habits based on the sites it visits.

Decentralized Credential Management for Autonomous Economic Agents

I would utilize the paper's method of deriving permanent accounts from ephemeral tokens to manage reputation and credit in decentralized AI marketplaces.

Improved AI System Capability: An AI agent could perform micro-transactions and build a reputation score at a specific marketplace (e.g., an compute provider) using an ephemeral pseudo-identity. This prevents a malicious marketplace from colluding with other providers to track the agent's entire economic footprint, while still allowing the agent to maintain locally-unique service history and loyalty benefits at each individual vendor.