Cryptology ePrint Archive: Report 2015/954

Online-Offline Homomorphic Signatures for Polynomial Functions

Kaoutar Elkhiyaoui and Melek Önen and Refik Molva

Abstract: The advent of cloud computing has given rise to a plethora of work on verifiable delegation of computation. Homomorphic signatures are a powerful tool that can be tailored for verifiable computation, as long as they are efficiently 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 degree, 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 signature is provably secure and its size grows only linearly with the degree of the evaluated polynomial.

Category / Keywords: cryptographic protocols / Homomorphic Signatures, Online-Offline Signatures

Date: received 30 Sep 2015

Contact author: elkhiyao at eurecom fr

Available format(s): PDF | BibTeX Citation

Version: 20151001:074315 (All versions of this report)

Short URL: ia.cr/2015/954

Discussion forum: Show discussion | Start new discussion