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

We introduce a new cryptographic primitive called signatures with flexible public key \((\mathsf{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 (\(\mathsf{SPS\text {-}EQ}\)), where the partitioning is done on the message space. Therefore, both definitions are complementary and their combination has various applications.