Paper 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.