Paper 2018/616

Matrioska: A Compiler for Multi-Key Homomorphic Signatures

Dario Fiore and Elena Pagnin


Multi-Key Homomorphic Signatures (MKHS) enable clients in a system to sign and upload messages to an untrusted server. At any later point in time, the server can perform a computation $C$ on data provided by $t$ different clients, and return the output $y$ and a short signature $\sigma{C, y}$ vouching for the correctness of $y$ as the output of the function $f$ on the signed data. Interestingly, MKHS enable verifiers to check the validity of the signature using solely the public keys of the signers whose messages were used in the computation. Moreover, the signatures $\sigma{C, y}$ are succinct, namely their size depends at most linearly in the number of clients, and only logarithmically in the total number of inputs of $C$. Existing MKHS are constructed based either on standard assumptions over lattices (Fiore et al., ASIACRYPT'16), or on non-falsifiable assumptions (SNARKs) (Lai et al., ePrint'16). In this paper, we investigate connections between single-key and multi-key homomorphic signatures. We propose a generic compiler, called \matrioska, which turns any (sufficiently expressive) single-key homomorphic signature scheme into a multi-key scheme. Matrioska establishes a formal connection between these two primitives and is the first alternative to the only known construction under standard falsifiable assumptions. Our result relies on a novel technique that exploits the homomorphic property of a single-key HS scheme to compress an arbitrary number of signatures from $t$ different users into only $t$ signatures.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. MAJOR revision.SCN 11th Conference on Security and Cryptography for Networks
Multi-Key Homomorphic SignaturesCompiler
Contact author(s)
elenap @ chalmers se
2018-12-14: revised
2018-06-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Dario Fiore and Elena Pagnin},
      title = {Matrioska: A Compiler for Multi-Key Homomorphic Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2018/616},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.