RSA Blind Signatures with Public Metadata
Authors: Ghous Amjad (Google), Kevin Yeo (Google), Moti Yung (Google)
Volume: 2025
Issue: 1
Pages: 37–57
DOI: https://doi.org/10.56553/popets-2025-0004
Abstract: Anonymous tokens are, essentially, digital signature schemes that enable issuers to provide users with signatures without learning the user inputs or the final signatures. These primitives allow applications to propagate trust while simultaneously protecting the user identity. They have become a core component for improving the privacy of several real-world applications including ad measurements, authorization protocols, spam detection, and VPNs. In certain applications, it is natural to associate signatures with specific public metadata, ensuring that trust is only propagated with respect to only a certain set of users and scenarios. To solve this, we study the notion of anonymous tokens with public metadata. We present a variant of RSA blind signatures with public metadata where issuers may only generate signatures that verify for a certain choice of public metadata that is a modification of a scheme by Abe and Fujisaki. Our protocol exclusively uses standard cryptography with widely available implementations. We prove security from the one-more RSA assumptions with multiple exponents that we introduce. Furthermore, we provide evidence that the concrete security bounds should be nearly identical to standard RSA blind signatures. We show that our protocol incurs minimal overhead over standard RSA blind signatures and report anonymous telemetry for a real-world deployment to showcase its scalability. Following our work, our protocol has been proposed as a technical specification in an IRTF internet draft.
Keywords: Anonymous Tokens, RSA Blind Signatures, Public Metadata
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
