Beyond Linear - Pairing-Based Multi-Key Homomorphic Signatures for Verifiable Statistics

Abstract

Multi-key homomorphic signatures (MKHS) address the challenge of verifying outsourced computations. Multiple independent parties each sign their own data and upload it to an untrusted server, allowing anyone to outsource computations over the signed data by request. In response to a query, the server returns both the computed result and a compact signature certifying its correctness, which can be verified using only the public keys of the participating signers. Existing implemented MKHS only support evaluation of linear functions. In this thesis, we address the problem of constructing implementable pairing-based MKHS schemes that support functions beyond linear, by extending the multi-key linearly homomorphic signature scheme of Aranha and Pagnin [Latincrypt, 2019]. We begin by reproving its security in the Type 3 pairing setting, bringing it in line with current cryptographic practices. Building on this, we present mkqhs-br, a pairing-based MKHS supporting bounded rank quadratic evaluation, proven secure under the co-CDH∗ assumption. We then give two independent extensions of mkqhs-br: (i) mkqhs-ebr, which compresses evaluated signature sizes, and (ii) mkqhs-br-m2, which extends the supported function class, enabling applications such as variance and least-squares computations. The extensions are compatible and can be combined, yielding a practical construction for statistical applications.