Paper 2023/784

History-Free Sequential Aggregate Signatures from Generic Trapdoor Functions

Alessio Meneghetti, University of Trento
Edoardo Signorini, Telsy
Abstract

A sequential aggregate signature (SAS) scheme allows multiple users to sequentially combine their respective signatures in order to reduce communication costs. Historically, early proposals required the use of trapdoor permutation (e.g., RSA). In recent years, a number of attempts have been made to extend SAS schemes to post-quantum assumptions. Many post-quantum signatures have been proposed in the hash-and-sign paradigm, which requires the use of trapdoor functions and appears to be an ideal candidate for sequential aggregation attempts. However, the hardness in achieving post-quantum one-way permutations makes it difficult to obtain similarly general constructions. Direct attempts at generalizing permutation-based schemes have been proposed, but they either lack formal security or require additional properties on the trapdoor function, which are typically not available for multivariate or code-based functions. In this paper, we propose a history-free sequential aggregate signature based on generic trapdoor functions, generalizing existing techniques. We prove the security of our scheme in the random oracle model by adopting the probabilistic hash-and-sign with retry paradigm, and we instantiate our construction with three post-quantum schemes, comparing their compression capabilities. Finally, we discuss how direct extensions of permutation-based SAS schemes are not possible without additional properties, showing the insecurity of two existing multivariate schemes when instantiated with Unbalanced Oil and Vinegar.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
sequential aggregate signaturepost-quantum cryptographyhash-and-sign
Contact author(s)
alessio meneghetti @ unitn it
edoardo signorini @ telsy it
History
2023-05-30: approved
2023-05-29: received
See all versions
Short URL
https://ia.cr/2023/784
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/784,
      author = {Alessio Meneghetti and Edoardo Signorini},
      title = {History-Free Sequential Aggregate Signatures from Generic Trapdoor Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2023/784},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/784}},
      url = {https://eprint.iacr.org/2023/784}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.