Paper 2016/834

A Zoo of Homomorphic Signatures: Multi-Key and Key-Homomorphism

Russell W. F. Lai and Raymond K. H. Tai and Harry W. H. Wong and Sherman S. M. Chow

Abstract

Homomorphic signatures (HS) allow evaluation of signed messages by producing a signature on a function of messages signed by the same key. Motivated by the vast potential of applications, we initiate the study of multi-key HS (M-HS) which allows evaluation of signatures under different keys in the \emph{insider corruption model}, where some or even all the signers are corrupt. We also study other multi-key extensions, namely, hierarchical HS (M-HiHS) for delegation of signing power over any supersets of a specified set of messages, and key-message-HS (M-KMHS) for evaluation of signatures under different keys with respect to both keys and messages. We thus also introduce the concept of key-homomorphism in signatures, which leads to the notion of multi-key key-HS (M-KHS) for evaluation of signatures with respect to keys only. Notion-wise, our result shows that M-HS can act as a central notion since all its seemingly different extensions are almost all equivalent (except one which assumes collision-resistant hash functions). In particular, this suggests that key-homomorphism and message-homomorphism in signatures are identical in nature. As a sample application, we show that M-KHS implies decentralized attribute-based signatures (D-ABS). Our work also provides the first (leveled) fully KHS and the first (D-)ABS for circuits from standard assumptions. Surprisingly, there is a huge gap between homomorphism in a single space and in two spaces. Indeed all existing (leveled) fully homomorphic signature schemes support only a single signer. In the multi-space setting, we construct M-HS from the adaptive zero-knowledge succinct non-interactive argument of knowledge (ZK-SNARK) (and other standard assumptions). We also show that two-key HS implies functional signatures. Our study equips the literature with a suite of signature schemes allowing different kinds of flexible evaluations.