Cryptology ePrint Archive: Report 2018/191

Signatures with Flexible Public Key: Introducing Equivalence Classes for Public Keys

Michael Backes and Lucjan Hanzlik and Kamil Kluczniak and Jonas Schneider

Abstract: We introduce a new cryptographic primitive called signatures with flexible public key (SFPK). We divide the key space into equivalence classes induced by a relation $\mathcal{R}$. A signer can efficiently change his or her key pair to a different representatives of the same class, but without a trapdoor it is hard to distinguish if two public keys are related. Our primitive is motivated by structure-preserving signatures on equivalence classes (SPSEQ), where the partitioning is done on the message space. Therefore, both definitions are complementary and their combination has various applications.

We first show how to efficiently construct static group signatures and self-blindable certificates by combining the two primitives. 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, but is secure in the same setting.

In its own right, our primitive has stand-alone applications in the cryptocurrency domain, where it can be seen as a straightforward formalization of so-called stealth addresses. Finally, it can be used to build the first efficient ring signature scheme in the plain model without trusted setup, where signature size depends only sub-linearly on the number of ring members. Thus, we solve an open problem stated by Malavolta and Schr{\"{o}}der at ASIACRYPT'2017.

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

Original Publication (with major differences): IACR-ASIACRYPT-2018

Date: received 16 Feb 2018, last revised 20 Sep 2018

Contact author: schneider at cs uni-saarland de

Available format(s): PDF | BibTeX Citation

Note: An extended abstract of this paper will appear at ASIACRYPT 2018.

Version: 20180920:120613 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]