Paper 2016/792

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

David Derler and Daniel Slamanig

Abstract

Key-homomorphic properties of cryptographic objects 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 generalize larger classes of existing signature schemes, which makes it possible to infer general statements about signature schemes from those classes by simply making black-box use of the respective properties. We then apply our definitional framework to show elegant and simple compilers from classes of 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 arguments of knowledge, 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. Moreover, we introduce the notion of multikey-homomorphic signatures. Such schemes provide homomorphic properties on the message space of signatures under different keys. We discuss key-homomorphisms in this context, present some first constructive results from key-homomorphic schemes and discuss potential applications.

Note: improved presentation