Cryptology ePrint Archive: Report 2021/350

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

Konstantinos Chalkias and Francois Garillot and 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.

Category / Keywords: public-key cryptography / Schnorr, EdDSA, signatures, aggregation

Original Publication (with minor differences): CT-RSA 2021: The Cryptographer's Track at the RSA Conference

Date: received 16 Mar 2021, last revised 22 Mar 2021

Contact author: valeria nikolaenko at gmail com, valerini at fb com, kostascrypto at fb com, francois at garillot net, kondi y at northeastern edu

Available format(s): PDF | BibTeX Citation

Version: 20210322:222529 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]