Foundations of Anonymous Signatures: Formal Definitions, Simplified Requirements, and a Construction Based on General Assumptions

In today's systems, privacy is often at odds with utility: users that reveal little information about themselves get restricted functionality, and service providers mistrust them. In practice, systems tip to either full anonymity (e.g. Monero), or full utility (e.g. Bitcoin). Well-known cryptographic primitives for bridging this gap exist: anonymous credentials (AC) let users disclose a subset of their credentials' attributes, revealing to service providers "just what they need"; group signatures (GS) allow users to authenticate anonymously, to be de-anonymized "just when deemed necessary". However, these primitives are hard to deploy.

Current AC and GS variants reach specific points in the privacy-utility tradeoff, which we point as counter-productive engineering-wise, as it requires full and error-prone re-engineering to adjust the tradeoff. Also, so far, GS and AC have been studied separately by theoretical research.

We take the first steps toward unifying and generalizing both domains, with the goal of bringing their benefits to practice, in a flexible way. We give a common model capturing their core properties, and use functional placeholders to subsume intermediate instantiations of the privacy-utility tradeoff under the same model. To prove its flexibility, we show how concrete variants of GS, AC (and others, like ring signatures) can be seen as special cases of our scheme – to which we refer as universal anonymous signatures (UAS). In practice, this means that instantiations following our construction can be configured to behave as variant X of a GS scheme, or as variant Y of an AC scheme, by tweaking a few functions.