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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision.CT-RSA 2021: The Cryptographer's Track at the RSA Conference
Keywords
SchnorrEdDSAsignaturesaggregation
Contact author(s)
valeria nikolaenko @ gmail com
valerini @ fb com
kostascrypto @ fb com
francois @ garillot net
kondi y @ northeastern edu
History
2021-03-22: last of 2 revisions
2021-03-18: received
See all versions
Short URL
https://ia.cr/2021/350
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/350,
      author = {Konstantinos Chalkias and Francois Garillot and Yashvanth Kondi and Valeria Nikolaenko},
      title = {Non-interactive half-aggregation of EdDSA and variants of Schnorr signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2021/350},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/350}},
      url = {https://eprint.iacr.org/2021/350}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.