## Cryptology ePrint Archive: Report 2018/191

Signatures with Flexible Public Key: A Unified Approach to Privacy-Preserving Signatures (Full Version)

Michael Backes and Lucjan Hanzlik and Kamil Kluczniak and Jonas Schneider

Abstract: We introduce a new cryptographic primitive called signatures with flexible public key. We divide the key space into equivalence classes induced by a relation $\mathcal{R}$. A signer can efficiently change his key pair to a different representative of the same class, but without a trapdoor it is hard to distinguish if two public keys are related.

This primitive offers a unified approach to the modular construction of signature schemes with privacy-preserving components. Namely, we show how to build the first ring signature scheme in the plain model without trusted setup, where signature size depends only sub-linearly on the number of ring members. Moreover, we show how to combine our primitive with structure-preserving signatures on equivalence classes (SPSEQ) to construct static group signatures and self-blindable certificates. When properly instantiated, the result is a group signature scheme that has a shorter signature size than the current state-of-the-art scheme by Libert, Peters, and Yung from Crypto'15.

In its own right, our primitive has stand-alone applications in the cryptocurrency domain. In particular it enables the straightforward implementation of so-called stealth addresses.

Category / Keywords: flexible public key, equivalence classes, stealth addresses, ring signatures, group signatures