Paper 2021/1651
A compiler for multikey homomorphic signatures for Turing machines
Somayeh Dolatnezhad Samarin, Dario Fiore, Daniele Venturi, and Morteza Amini
Abstract
At SCN 2018, Fiore and Pagnin proposed a generic compiler (called ``Matrioska'') allowing to transform sufficiently expressive singlekey homomorphic signatures (SKHSs) into multikey homomorphic signatures (MKHSs) under falsifiable assumptions in the standard model. Matrioska is designed for homomorphic signatures that support programs represented as circuits. The MKHS schemes obtained through Matrioska support the evaluation and verification of arbitrary circuits over data signed from multiple users, but they require the underlying SKHS scheme to work with circuits whose size is exponential in the number of users, and thus can only support a constant number of users. In this work, we propose a new generic compiler to convert an SKHS scheme into an MKHS scheme. Our compiler is a generalization of Matrioska for homomorphic signatures that support programs in any model of computation. When instantiated with SKHS for circuits, we recover the Matrioska compiler of Fiore and Pagnin. As an additional contribution, we show how to instantiate our generic compiler in the Turing Machines (TM) model and argue that this instantiation allows to overcome some limitations of Matrioska:  First, the MKHS we obtain require the underlying SKHS to support TMs whose size depends only linearly in the number of users.  Second, when instantiated with an SKHS with succinctness $poly(\lambda)$ and fast enough verification time, e.g., $S \cdot \log T + n \cdot poly(\lambda)$ or $T +n \cdot poly(\lambda)$ (where $T$, $S$, and $n$ are the running time, description size, and input length of the program to verify, respectively), our compiler yields an MKHS in which the time complexity of both the prover and the verifier remains $poly(\lambda)$ even if executed on programs with inputs from $poly(\lambda)$ users. While we leave constructing an SKHS with these efficiency properties as an open problem, we make one step towards this goal by proposing an SKHS scheme with verification time $poly(\lambda) \cdot T$ under falsifiable assumptions in the standard model.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. Minor revision. Theoretical Computer Science
 DOI
 10.1016/j.tcs.2021.08.002
 Keywords
 homomorphic signaturesmultikey homomorphic signaturesTuring machinesverifiable computation
 Contact author(s)
 dario fiore @ imdea org
 History
 20211217: received
 Short URL
 https://ia.cr/2021/1651
 License

CC BYNCND
BibTeX
@misc{cryptoeprint:2021/1651, author = {Somayeh Dolatnezhad Samarin and Dario Fiore and Daniele Venturi and Morteza Amini}, title = {A compiler for multikey homomorphic signatures for Turing machines}, howpublished = {Cryptology {ePrint} Archive, Paper 2021/1651}, year = {2021}, doi = {10.1016/j.tcs.2021.08.002}, url = {https://eprint.iacr.org/2021/1651} }