Matrioska: A Compiler for Multi-key Homomorphic Signatures

Dario Fiore, Elena Pagnin

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceedingForskningPeer review

4 Citeringar (SciVal)

Sammanfattning

Multi-Key Homomorphic Signatures (MK-HS) 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 σC,y vouching for the correctness of y as the output of the function C on the signed data. Interestingly, MK-HS 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 σ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 MK-HS 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.
Originalspråkengelska
Titel på gästpublikationSecurity and Cryptography for Networks
Undertitel på gästpublikation11th International Conference, SCN 2018, Amalfi, Italy, September 5–7, 2018, Proceedings
RedaktörerDario Catalano, Roberto De Prisco
FörlagSpringer
Sidor43-62
ISBN (elektroniskt)978-3-319-98113-0
ISBN (tryckt)978-3-319-98112-3
DOI
StatusPublished - 2018
Externt publiceradJa
Evenemang11th International Conference on Security and Cryptography for Networks, SNC 2018 - Amalfi, Italien
Varaktighet: 2018 sep 52018 sep 7

Publikationsserier

NamnLecture Notes in Computer Science
FörlagSpringer
Volym11035
ISSN (tryckt)0302-9743
ISSN (elektroniskt)1611-3349

Konferens

Konferens11th International Conference on Security and Cryptography for Networks, SNC 2018
Land/TerritoriumItalien
OrtAmalfi
Period2018/09/052018/09/07

Ämnesklassifikation (UKÄ)

  • Datavetenskap (datalogi)

Fingeravtryck

Utforska forskningsämnen för ”Matrioska: A Compiler for Multi-key Homomorphic Signatures”. Tillsammans bildar de ett unikt fingeravtryck.

Citera det här