The Simplest Multi-key Linearly Homomorphic Signature Scheme
Aranha, Diego and Pagnin, Elena LU
(2019)
6th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2019
In Lecture Notes in Computer Science
11774.
p.280-300
- 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 [7]) to the multi-key setting and relies on basic tools of pairing-based cryptography. Compared to existing multi-key homomorphic... (More)
- 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. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/9d083f99-b476-4532-bc05-bd083177fb80
- author
- Aranha, Diego
and Pagnin, Elena
LU
- publishing date
- 2019-09-09
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- keywords
- Multi-key homomorphic signatures, Cryptographic pairings, Efficient software implementation
- host publication
- Progress in Cryptology – LATINCRYPT 2019 : 6th International Conference on Cryptology and Information Security in Latin America, Santiago de Chile, Chile, October 2–4, 2019, Proceedings - 6th International Conference on Cryptology and Information Security in Latin America, Santiago de Chile, Chile, October 2–4, 2019, Proceedings
- series title
- Lecture Notes in Computer Science
- editor
- Schwabe, Peter and Thériault, Nicolas
- volume
- 11774
- pages
- 280 - 300
- publisher
- Springer
- conference name
- 6th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2019
- conference location
- Santiago de Chile, Chile
- conference dates
- 2019-10-02 - 2019-10-04
- external identifiers
-
- scopus:85072867595
- ISSN
- 1611-3349
- 0302-9743
- ISBN
- 978-3-030-30530-7
- 978-3-030-30529-1
- DOI
- 10.1007/978-3-030-30530-7_14
- language
- English
- LU publication?
- no
- id
- 9d083f99-b476-4532-bc05-bd083177fb80
- date added to LUP
- 2021-01-26 15:04:36
- date last changed
- 2025-10-18 14:41:06
@inproceedings{9d083f99-b476-4532-bc05-bd083177fb80,
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 [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.}},
author = {{Aranha, Diego and Pagnin, Elena}},
booktitle = {{Progress in Cryptology – LATINCRYPT 2019 : 6th International Conference on Cryptology and Information Security in Latin America, Santiago de Chile, Chile, October 2–4, 2019, Proceedings}},
editor = {{Schwabe, Peter and Thériault, Nicolas}},
isbn = {{978-3-030-30530-7}},
issn = {{1611-3349}},
keywords = {{Multi-key homomorphic signatures; Cryptographic pairings; Efficient software implementation}},
language = {{eng}},
month = {{09}},
pages = {{280--300}},
publisher = {{Springer}},
series = {{Lecture Notes in Computer Science}},
title = {{The Simplest Multi-key Linearly Homomorphic Signature Scheme}},
url = {{http://dx.doi.org/10.1007/978-3-030-30530-7_14}},
doi = {{10.1007/978-3-030-30530-7_14}},
volume = {{11774}},
year = {{2019}},
}