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.
Category / Keywords: key-homomorphic signatures, ring signatures, (universal) designated verifier signatures, simulation sound extractable argument systems, multisignatures, multi-user signatures, multikey-homomorphic signatures Date: received 19 Aug 2016, last revised 6 Feb 2017 Contact author: david derler at iaik tugraz at Available format(s): PDF | BibTeX Citation Note: improved presentation Version: 20170206:094256 (All versions of this report) Short URL: ia.cr/2016/792 Discussion forum: Show discussion | Start new discussion