Paper 2016/834

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.