Online-offline homomorphic signatures for polynomial functions
Kaoutar Elkhiyaoui · Graduate School and Research Center in Digital Science (EURECOM) · 2017
Abstract. The advent of cloud computing has given rise to a plethora of work on verifiable delegation of computation. Homomorphic signatures are a power-ful tool that can be tailored for verifiable computation, as long as they are effi-ciently verifiable. The main advantages of homomorphic signatures are twofold: (i) public verifiability: Any third party can verify the correctness of the delegated computation; (ii) statelessness: The verifier is not required to have access to the dataset on which the computation was performed. Thus in this paper, we design a homomorphic signature suitable for multivariate polynomials of bounded de-gree, and which draws upon the algebraic properties of eigenvectors and leveled multilinear maps. The proposed signature yields an efficient verification process (in an amortized sense) and supports offline-online signing. Furthermore, our sig-nature is provably secure and its size grows only linearly with the degree of the evaluated polynomial. 1