Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations/digital signatures

Date: received 29 Aug 2016, last revised 9 Dec 2016

Contact author: russell at ie cuhk edu hk

Available format(s): PDF | BibTeX Citation

Version: 20161209:194104 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]