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 (partial-signature) history-free SAS within the probabilistic hash-and-sign with retry paradigm, generalizing existing techniques to generic trapdoor functions. We prove the security of our scheme in the random oracle model 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 lack of security of two existing multivariate schemes.

History-Free Sequential Aggregation of Hash-and-Sign Signatures / Meneghetti, Alessio; Signorini, Edoardo. - 14643:(2024), pp. 187-223. (Intervento presentato al convegno Cryptographer's Track at the RSA Conference 2024 tenutosi a San Francisco (USA) nel 6th-9th May 2024) [10.1007/978-3-031-58868-6_8].

History-Free Sequential Aggregation of Hash-and-Sign Signatures

Meneghetti, Alessio;
2024-01-01

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 (partial-signature) history-free SAS within the probabilistic hash-and-sign with retry paradigm, generalizing existing techniques to generic trapdoor functions. We prove the security of our scheme in the random oracle model 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 lack of security of two existing multivariate schemes.
2024
Topics in Cryptology – CT-RSA 2024
Cham, Svizzera
Springer
9783031588679
9783031588686
Meneghetti, Alessio; Signorini, Edoardo
History-Free Sequential Aggregation of Hash-and-Sign Signatures / Meneghetti, Alessio; Signorini, Edoardo. - 14643:(2024), pp. 187-223. (Intervento presentato al convegno Cryptographer's Track at the RSA Conference 2024 tenutosi a San Francisco (USA) nel 6th-9th May 2024) [10.1007/978-3-031-58868-6_8].
File in questo prodotto:
File Dimensione Formato  
MenSig24.pdf

embargo fino al 06/05/2025

Descrizione: post-print
Tipologia: Post-print referato (Refereed author’s manuscript)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 755.63 kB
Formato Adobe PDF
755.63 kB Adobe PDF   Visualizza/Apri
978-3-031-58868-6_8.pdf

Solo gestori archivio

Descrizione: paper
Tipologia: Versione editoriale (Publisher’s layout)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 408.84 kB
Formato Adobe PDF
408.84 kB Adobe PDF   Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11572/412670
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact