Online-offline homomorphic signatures for polynomial functions

Elkhiyaoui, Kaoutar; Önen, Melek; Molva, Refik

The advent of cloud computing has given rise to a plethora of work on
verifiable delegation of computation. Homomorphic signatures are powerful
tools that can be tailored for verifiable computation, as long as they are efficiently
verifiable. The main advantages of homomorphic signatures for verifiable
computation are twofold: (i) Any third party can verify the correctness
of the delegated computation, (ii) and this third party is not required to have
access to the dataset on which the computation was performed. In this paper,
we design a homomorphic signature suitable for multivariate polynomials of
bounded degree, 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 online-offline signing.
Furthermore, our signature is provably secure and its size grows only linearly
with the degree of the evaluated polynomial.

Digital Security
Eurecom Ref:
© EURECOM. Personal use of this material is permitted. The definitive version of this paper was published in and is available at :