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


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
Published by the IACR in ASIACRYPT 2018
foundationsdigital signatures
Contact author(s)
sherman @ ie cuhk edu hk
2018-11-02: last of 4 revisions
2016-08-31: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.