The simplest multi-key linearly homomorphic signature scheme

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

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
EditorsPeter Schwabe, Nicolas Thériault
Number of pages21
Place of publicationCham
Publication year2019
ISBN (print)9783030305291
ISBN (Electronic)978-3-030-30530-7
Publication statusPublished - 2019
Event6th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2019 - Santiago de Chile, Chile
Duration: 2 Oct 20194 Oct 2019


Conference6th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2019
BySantiago de Chile
SeriesLecture Notes in Computer Science

    Research areas

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

See relations at Aarhus University Citationformats

ID: 168719717