4th Anonymity Day Workshop

Anonymity Days is a workshop series for disseminating recent advances in anonymity research. It will occur twice a year at Brown University, Tufts University, or Columbia University, rotating between the three venues. Our target audience is theory and security researchers/graduate students interested in sharing and learning the newest anonymity results, but everyone is welcome! If you plan to attend, register below (free).

• Location: Room 601 (The Lantern), Joyce Cummings Center, Tufts University

• Date and Time: June 3, 9:30 - 3:30

• Location: Room 601 (The Lantern), Joyce Cummings Center, Tufts University

• Address: 177 College Ave, Medford, MA 02155

• Date and Time: June 3, 9:30 AM – 3:30 PM

• Parking: Visitor parking information for the Tufts Medford/Somerville campus can be found here: https://access.tufts.edu/visitor-parking 

Register

Agenda:

• 9:30 - 10:00 | Coffee & pastries, followed by opening remarks by Megumi Ando (Tufts University)

• 10:00 - 10:50 | "Discrimination through optimization: Measuring fairness and bias in social network ad delivery" by Alan Mislove (Northeastern University)

• 11:00 - 11:50 | "Lattice-Based Rate-Limited Tokens in the Random Oracle Model" by Victor Youdom Kemmoe (Brown University)

• 12:00 - 1:30 | Lunch (provided)

• 1:30 - 2:20 | "Structural Compliance: Making Software Systems Inherently Lawful" by Sebastian Zimmeck (Wesleyan University)

• 2:30 - 3:20 | "A Tale of BBS Credentials" by Stefano Tessaro (University of Washington)

Abstracts

"Discrimination through optimization: Measuring fairness and bias in social network ad delivery" ............... by Alan Mislove (Northeastern University)

The enormous financial success of online advertising platforms is partially due to the precise targeting and delivery features they offer.  These platforms routinely claim to be able to identify which platform users are most likely to meet advertisers’ objectives, and steer ads towards those users via their ad delivery algorithms.  This is typically accomplished by estimating the “relevance” of ads to users, but raises a number of concerns about bias, discrimination, and impacts on historically disadvantaged groups and society as a whole.  Unfortunately, the manner in which platforms calculate such relevance estimates is opaque and challenging to study, and platforms are often resistant to sharing information publicly.

In this talk, I discuss work my group has done to address this challenge.  I first develop a measurement methodology using Facebook’s advertiser interface that can measure the influence of Facebook’s choices about how to deliver ads.  I then demonstrate that ad delivery can be significantly skewed by protected classes on Facebook, due to the platform’s own predictions about the “relevance” of ads to different groups of users. I show significant skew in delivery along gender and racial lines for “real” ads for employment and housing opportunities despite neutral targeting parameters.  Overall, our findings demonstrate previously unknown mechanisms that can lead to potentially discriminatory ad delivery, even when advertisers set their targeting parameters to be highly inclusive.

"Lattice-Based Rate-Limited Tokens in the Random Oracle Model" by Victor Youdom Kemmoe (Brown University)

An anonymous credential allows a user to prove that she is authorized in an anonymous and unlinkable fashion. A rate-limited token is an anonymous credential that can only be used a limited number of times in any particular context; this means that even though we do not know which users are gaining access to a resource, there is a limit to how many resources one user may consume. Such tokens are becoming an increasingly attractive way to balance privacy with authorized access. Although a general architecture for how to obtain rate-limited tokens from digital signatures, pseudorandom functions (PRFs), and non-interactive zero-knowledge proofs (NIZKs) has been known for over twenty years, efficiently instantiating it with post-quantum- secure signatures and proofs has, until now, remained an open problem. In this work, we present the first lattice-based construction of rate-limited tokens and tackle the practical challenges associated with using lattice-based building blocks in this setting. A central difficulty lies in the absence of lattice-based PRFs that support efficient NIZK proofs of correct evaluation. We show that, in the random oracle model, a weak PRF—where adversaries are restricted to querying random inputs—suffices. We further present a weak PRF construction that both admits efficient NIZK proofs and remains secure—even when adversaries have partial control over the randomness—and extend this guarantee more generally to key-homomorphic PRFs. 

Another contribution, which is of independent interest, is the first lattice-based construction of partially binding commitments, a primitive introduced by Goel et al. (Eurocrypt 2022) that was previously known only under discrete-log assumptions. We give a practical construction that enables succinct disjunctive proofs via a variant of the self-stacking compiler of Goel et al. Along the way, we develop a new technique for batching CNF proofs of Σ-protocols, which allows one to efficiently prove that a value is the output of a PRF on one of a set of inputs. As a direct application, this yields logarithmic-size lattice-based ring signatures based on Fiat–Shamir-with- Aborts Σ-protocols (Lyubashevsky, Eurocrypt 2012). Finally, we observe for the first time that the anonymous counting tokens of Benhamouda, Raykova, and Seth (Asiacrypt 2023) can be obtained from anonymous rate-limited tokens. This yields a construction whose communication complexity is independent of the number of tokens that need to be issued.

Joint work with Anna Lysyanskaya and Ngoc Khanh Nguyen

"Structural Compliance: Making Software Systems Inherently Lawful" by Sebastian Zimmeck (Wesleyan University)

As software systems—ranging from the web and mobile platforms to large language models—become increasingly central to our personal and professional lives, the gap between legal requirements and technical implementation presents a significant challenge. Without ensuring that these systems behave lawfully, for example, protecting user privacy, we cannot realize their full potential, particularly in sensitive domains such as health, employment, or finance. In this talk, I introduce the concept of Structural Compliance: a paradigm for designing and implementing systems that inherently adhere to legal norms. Drawing on case studies such as Global Privacy Control and causal structuring of AI models, I will explore how to bridge the divide between core legal requirements and system architecture. We will discuss how technical standards can act as a flexible bridge, allowing laws to become self-enforcing without stifling innovation. Ultimately, structural compliance aims to protect individual autonomy by ensuring that the rule of law is a built-in property of our digital infrastructure.

"A Tale of BBS Credentials" by Stefano Tessaro (University of Washington)

BBS is a simple pairing-based signature scheme that has emerged as a favored instantiation of the paradigm of signatures with efficient protocols for anonymous credentials. It enables both lightweight credential presentation proofs and blind issuance, and now sits at the center of several standardization efforts. The goal of this talk is to review the somewhat unusual history of BBS signatures, with a particular focus on recent works that revisit their security, clarify their concrete security guarantees, and have helped guide standardization. I will also discuss pairing-free instantiations of BBS (e.g., in the server-aided setting), and compare BBS to alternatives. This talk is based on joint works with Rutchathon Chairattana-Apirom, Franklin Harding, Dennis Hofheinz, Anna Lysyanskaya, and Chenzhi Zhu.

Organizers:

• Megumi Ando (Tufts University)

• Anna Lysyanskaya (Brown University)

• Tal Malkin (Columbia University)

• Eli Upfal (Brown University) 

• Michael Rivera (Tufts University)

Previous Anonymity Day Workshops

• 2nd Anonymity Day Workshop (Tufts University)

• 3rd Anonymity Day Workshop (Columbia University)

This workshop has been supported by NSF grants CCF-2312241, CCF-2312242, and CCF-2312243 and the Tufts Cybersecurity Center for the Public Good.