A compiler for multi-key homomorphic signatures for Turing machines

At SCN 2018, Fiore and Pagnin proposed a generic compiler (called “Matrioska”) allowing to transform sufficiently expressive single-key homomorphic signatures (SKHSs) into multi-key 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(λ) and fast enough verification time, e.g., S⋅log⁡T+n⋅poly(λ) or T+n⋅poly(λ) (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(λ) even if executed on programs with inputs from poly(λ) 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(λ)⋅T under falsifiable assumptions in the standard model.