Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Matrioska: A Compiler for Multi-key Homomorphic Signatures

Fiore, Dario and Pagnin, Elena LU orcid (2018) 11th International Conference on Security and Cryptography for Networks, SNC 2018 In Lecture Notes in Computer Science 11035. p.43-62
Abstract
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
and
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
Security and Cryptography for Networks : 11th International Conference, SCN 2018, Amalfi, Italy, September 5–7, 2018, Proceedings - 11th International Conference, SCN 2018, Amalfi, Italy, September 5–7, 2018, Proceedings
series title
Lecture Notes in Computer Science
editor
Catalano, Dario and De Prisco, Roberto
volume
11035
pages
43 - 62
publisher
Springer
conference name
11th International Conference on Security and Cryptography for Networks, SNC 2018
conference location
Amalfi, Italy
conference dates
2018-09-05 - 2018-09-07
external identifiers
  • scopus:85053595122
ISSN
1611-3349
0302-9743
ISBN
978-3-319-98113-0
978-3-319-98112-3
DOI
10.1007/978-3-319-98113-0_3
language
English
LU publication?
no
id
24aa2668-3f4c-49fa-950a-ddf943f4ac3f
date added to LUP
2021-01-26 15:58:49
date last changed
2024-05-02 03:24:03
@inproceedings{24aa2668-3f4c-49fa-950a-ddf943f4ac3f,
  abstract     = {{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.}},
  author       = {{Fiore, Dario and Pagnin, Elena}},
  booktitle    = {{Security and Cryptography for Networks : 11th International Conference, SCN 2018, Amalfi, Italy, September 5–7, 2018, Proceedings}},
  editor       = {{Catalano, Dario and De Prisco, Roberto}},
  isbn         = {{978-3-319-98113-0}},
  issn         = {{1611-3349}},
  language     = {{eng}},
  pages        = {{43--62}},
  publisher    = {{Springer}},
  series       = {{Lecture Notes in Computer Science}},
  title        = {{Matrioska: A Compiler for Multi-key Homomorphic Signatures}},
  url          = {{http://dx.doi.org/10.1007/978-3-319-98113-0_3}},
  doi          = {{10.1007/978-3-319-98113-0_3}},
  volume       = {{11035}},
  year         = {{2018}},
}