### Multi-Key Homomorphic Signatures Unforgeable under Insider Corruption

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

##### Abstract

Homomorphic signatures (HS) allows the derivation of the signature of the message-function pair $(m, g)$, where $m = g(m_1, \ldots, m_K)$, given the signatures of each of the input messages $m_k$ signed under the same key. Multi-key HS (M-HS) introduced by Fiore et al. (ASIACRYPT'16) further enhances the utility by allowing evaluation of signatures under different keys. While the unforgeability of existing M-HS notions unrealistically assumes that all signers are honest, we consider the setting where an arbitrary number of signers can be corrupted, which is typical in natural applications (e.g., verifiable multi-party computation) of M-HS. Surprisingly, there is a huge gap between M-HS with and without unforgeability under corruption: While the latter can be constructed from standard lattice assumptions (ASIACRYPT'16), we show that the former must rely on non-falsifiable assumptions. Specifically, we propose a generic construction of M-HS with unforgeability under corruption from adaptive zero-knowledge succinct non-interactive arguments of knowledge (ZK-SNARK) (and other standard assumptions), and then show that such M-HS implies adaptive zero-knowledge succinct non-interactive arguments (ZK-SNARG). Our results leave open the pressing question of what level of authenticity can be guaranteed in the multi-key setting under standard assumptions.

Available format(s)
Publication info
Keywords
foundationsdigital signatures
Contact author(s)
sherman @ ie cuhk edu hk
History
2018-11-02: last of 4 revisions
See all versions
Short URL
https://ia.cr/2016/834

CC BY

BibTeX

@misc{cryptoeprint:2016/834,
author = {Russell W.  F.  Lai and Raymond K.  H.  Tai and Harry W.  H.  Wong and Sherman S.  M.  Chow},
title = {Multi-Key Homomorphic Signatures Unforgeable under Insider Corruption},
howpublished = {Cryptology ePrint Archive, Paper 2016/834},
year = {2016},
note = {\url{https://eprint.iacr.org/2016/834}},
url = {https://eprint.iacr.org/2016/834}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.