Linearly Homomorphic Signature Schemes

Abstract

Digital signatures are used everywhere around us. They are well-studied and have been standardized since 1994. In 2002, Johnson et al. introduced the notion of homomorphic digital signatures, allowing one to perform computations on signed data. These signatures are especially useful for linear network coding, a technique used to improve throughput and resilience of networks, and in verifiable cloud computing. However, homomorphic signatures are not standardized and less well-studied, which creates a challenge when choosing one of the published schemes. Moreover, most schemes remain unimplemented, and it is insufficient to compare their theoretical performance for real-world applications. Those schemes that are implemented are not directly comparable since they use different instantiations of the same primitives or they are implemented in different programming languages.
In this thesis, we set out to find out how we can assess the performance of homomorphic signa- ture schemes. To this end, we have implemented eleven pairing-based linearly homomorphic signature schemes. All signature schemes have been implemented on the BLS12-381 curve to constitute a fair comparison. We assess the performance of the signature schemes based on their signing, verifying and combining performance, as well as the sizes of their keys and signatures. Furthermore, we analyse the impact that additional features such as supporting a multi-party setting have on the performance of a signature scheme. Based on our exper- imental results, we make recommendations for three types of applications: For constrained devices, the scheme Li20 is the most suitable due to its compact signing key and efficient sign- ing operation. For network coding, which requires fast verification, fast combining, and small signatures, we also recommend the scheme by Li et al. Finally, for a multi-party, privacy- preserving scheme, we recommend the scheme by Sch18 and Sch19, which preserve input privacy of homomorphically combined signatures. We find that we can assess the perfor- mance of a homomorphic signature scheme based on the speed of the signing, verifying and combining operation. Our implementation is publicly available.