Paper 2019/830

The Simplest Multi-key Linearly Homomorphic Signature Scheme

Diego F. Aranha and Elena Pagnin

Abstract

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) 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. LATINCRYPT 2019
Keywords
Multi-key homomorphic signaturescryptographic pairingsefficient software implementation
Contact author(s)
elena @ cs au dk
dfaranha @ eng au dk
History
2019-07-18: received
Short URL
https://ia.cr/2019/830
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/830,
      author = {Diego F.  Aranha and Elena Pagnin},
      title = {The Simplest Multi-key Linearly Homomorphic Signature Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2019/830},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/830}},
      url = {https://eprint.iacr.org/2019/830}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.