The Simplest Multi-key Linearly Homomorphic Signature Scheme

Diego Aranha, Elena Pagnin

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceedingResearchpeer-review

5 Citations (SciVal)


We consider the problem of outsourcing computation on data authenticated by different users. Our aim is to describe and implement the simplest possible solution to provide data integrity in cloud-based scenarios. Concretely, our multi-key linearly homomorphic signature scheme (MKLHS) allows users to upload signed data on a server, and at any later point in time any third party can query the server to compute a linear combination of data authenticated by different users and check the correctness of the returned result. Our construction generalizes Boneh et al.’s linearly homomorphic signature scheme (PKC’09 [7]) to the multi-key setting and relies on basic tools of pairing-based cryptography. Compared to existing multi-key homomorphic signature schemes, our MKLHS is a conceptually simple and elegant direct construction, which trades-off privacy for efficiency. The simplicity of our approach leads us to a very efficient construction that enjoys significantly shorter signatures and higher performance than previous proposals. Finally, we implement MKLHS using two different pairing-friendly curves at the 128-bit security level, a Barreto-Lynn-Scott curve and a Barreto-Naehrig curve. Our benchmarks illustrate interesting performance trade-offs between these parameters, involving the cost of exponentiation and hashing in pairing groups. We provide a discussion on such trade-offs that can be useful to other implementers of pairing-based protocols.
Original languageEnglish
Title of host publicationProgress in Cryptology – LATINCRYPT 2019
Subtitle of host publication6th International Conference on Cryptology and Information Security in Latin America, Santiago de Chile, Chile, October 2–4, 2019, Proceedings
EditorsPeter Schwabe, Nicolas Thériault
ISBN (Electronic)978-3-030-30530-7
ISBN (Print)978-3-030-30529-1
Publication statusPublished - 2019 Sep 9
Externally publishedYes
Event6th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2019 - Santiago de Chile, Chile
Duration: 2019 Oct 22019 Oct 4

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference6th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2019
CitySantiago de Chile

Subject classification (UKÄ)

  • Communication Systems


  • Multi-key homomorphic signatures
  • Cryptographic pairings
  • Efficient software implementation


Dive into the research topics of 'The Simplest Multi-key Linearly Homomorphic Signature Scheme'. Together they form a unique fingerprint.

Cite this