The Simplest Multi-key Linearly Homomorphic Signature Scheme

Oct 17, 2019 12:00 AM

Who: Elena Pagnin from Aarhus University, Denmark \
When: 10:00 - 11:00 Thursday {{ | date_to_long_string }}\
Where: Room 8103, EDIT building.\
Title: {{ page.title }}

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 inpairing groups. We provide a discussion on such trade-offs that can be useful to other implementers of pairing-based protocols.

Previous Talks

{: .t60 } {% include list-posts tag=‘csstalk’%}