We close this gap and initiate the study of key-homomorphic signatures, which turns out to be an interesting and versatile concept. In doing so, we firstly propose a definitional framework for key-homomorphic signatures distilling various natural flavours of key-homomorphic properties. Those properties aim to classify existing signature schemes and thus allow to infer general statements about signature schemes from those classes by simply making black-box use of the respective properties. We apply our definitional framework to show elegant and simple compilers from classes of signature schemes admitting different types of key-homomorphisms to a number of other interesting primitives such as ring signature schemes, (universal) designated verifier signature schemes, simulation-sound extractable non-interactive zero-knowledge (NIZK) arguments, and multisignature schemes. Additionally, using the formalisms provided by our framework, we can prove a tight implication from single-user security to key-prefixed multi-user security for a class of schemes admitting a certain key-homomorphism.
Finally, we discuss schemes that provide homomorphic properties on the message space of signatures under different keys in context of key-homomorphisms and present some first constructive results from key-homomorphic schemes.
Category / Keywords: public-key cryptography / key-homomorphic signatures, ring signatures, (universal) designated verifier signatures, simulation-sound extractable non-interactive zero-knowledge, multisignatures, multi-user signatures, multikey-homomorphic signatures Original Publication (with minor differences): Designs, Codes and Cryptography