Paper 2016/792

Key-Homomorphic Signatures: Definitions and Applications to Multiparty Signatures and Non-Interactive Zero-Knowledge

David Derler and Daniel Slamanig


Key-homomorphic properties of cryptographic objects, i.e., homomorphisms on their key space, have proven to be useful, both from a theoretical as well as a practical perspective. Important cryptographic objects such as pseudorandom functions or (public key) encryption have been studied previously with respect to key-homomorphisms. Interestingly, however, signature schemes have not been explicitly investigated in this context so far. 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.

Note: The journal version of this paper does not to include the part on multikey-homomorphic signatures. We include it in this full version as Appendix A. 04.03.21: Fix a bug in Def 15.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Minor revision. Designs, Codes and Cryptography
key-homomorphic signaturesring signatures(universal) designated verifier signaturesmultisignaturesmulti-user signaturesmultikey-homomorphic signatures
Contact author(s)
david @ dfinity org
daniel slamanig @ ait ac at
2021-03-04: last of 9 revisions
2016-08-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {David Derler and Daniel Slamanig},
      title = {Key-Homomorphic Signatures: Definitions and Applications to Multiparty Signatures and Non-Interactive Zero-Knowledge},
      howpublished = {Cryptology ePrint Archive, Paper 2016/792},
      year = {2016},
      doi = {10.1007/s10623-018-0535-9},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.