Paper 2015/954

Online-Offline Homomorphic Signatures for Polynomial Functions

Kaoutar Elkhiyaoui, Melek Önen, and Refik Molva


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: \begin{inparaenum}[(i)] \item Any third party can verify the correctness of the delegated computation, \item and this third party is not required to have access to the dataset on which the computation was performed. \end{inparaenum} In this paper, we design a homomorphic signature suitable for multivariate polynomials of bounded degree, which draws upon the algebraic properties of \emph{eigenvectors} and \emph{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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Homomorphic SignaturesOnline-Offline Signatures
Contact author(s)
melek onen @ eurecom fr
2017-06-12: revised
2015-10-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Kaoutar Elkhiyaoui and Melek Önen and Refik Molva},
      title = {Online-Offline Homomorphic Signatures for Polynomial Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2015/954},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.