Paper 2021/350

Non-interactive half-aggregation of EdDSA and variants of Schnorr signatures

Konstantinos Chalkias, Francois Garillot, Yashvanth Kondi, and Valeria Nikolaenko

Abstract

Schnorr's signature scheme provides an elegant method to derive signatures with security rooted in the hardness of the discrete logarithm problem, which is a well-studied assumption and conducive to efficient cryptography. However, unlike pairing-based schemes which allow arbitrarily many signatures to be aggregated to a single constant sized signature, achieving significant non-interactive compression for Schnorr signatures and their variants has remained elusive. This work shows how to compress a set of independent EdDSA/Schnorr signatures to roughly half their naive size. Our technique does not employ generic succinct proofs; it is agnostic to both the hash function as well as the specific representation of the group used to instantiate the signature scheme. We demonstrate via an implementation that our aggregation scheme is indeed practical. Additionally, we give strong evidence that achieving better compression would imply proving statements specific to the hash function in Schnorr's scheme, which would entail significant effort for standardized schemes such as SHA2 in EdDSA. Among the others, our solution has direct applications to compressing Ed25519-based blockchain blocks because transactions are independent and normally users do not interact with each other.