A sponge-based approach to speed up post-quantum signature schemes

Digital signatures are fundamental asymmetric primitives in modern cryptography, crucial for ensuring the authenticity and integrity of documents in most security protocols. However, many signature schemes in use today are vulnerable to attack by quantum computers, mainly due to Shor's algorithm. As a direct consequence, there has been a significant increase in research focusing on the design of post-quantum cryptographic schemes, and the National Institute of Standards and Technology (NIST) has launched a call for proposals to standardize post-quantum cryptography. In this Master's thesis, we focus on hash-based signature schemes such as WOTS, which is a foundation block for modern hash-based signature schemes. While the security of these schemes is generally well understood due to the reduction of security to the assumed properties of the hash function used, one of the main challenges is the generation of hash chains. This process in the WOTS algorithm accounts for approximately 98% of the computational time required to generate and verify a signature. Therefore, our goal is to improve the efficiency of hash chain generation in hash-based signature schemes. To achieve this, we introduce a new construction called SpongeGr, along with its duplex version, SpongeGr-D, based on sponge functions. The integration of SpongeGr-D into WOTS allows a reduction in the time needed to sign a message of up to 56% compared to state-of-the-art solutions.

Le firme digitali sono primitive asimmetriche fondamentali nella crittografia moderna, cruciali per garantire l'autenticità e l'integrità dei documenti nella maggior parte dei protocolli di sicurezza. Tuttavia, molti schemi di firma oggi in uso sono vulnerabili agli attacchi dei computer quantistici, soprattutto a causa dell'algoritmo di Shor. Come diretta conseguenza, c'è stato un significativo aumento della ricerca incentrata sulla progettazione di schemi crittografici post-quantistici e il National Institute of Standards and Technology (NIST) ha lanciato un invito a presentare proposte per standardizzare la crittografia post-quantistica. In questa tesi, ci concentriamo sugli schemi di firma basati su hash, come ad esempio WOTS, che rappresenta il fondamento dei più moderni schemi di firma basati su hash. Mentre la sicurezza di questi schemi è generalmente ben compresa grazie alla riduzione della sicurezza alle proprietà assunte della funzione hash utilizzata, una delle sfide principali è la generazione di catene hash. Questo processo nell'algoritmo WOTS rappresenta circa il 98% del tempo computazionale necessario per generare e verificare una firma. Il nostro obiettivo è quindi quello di migliorare l'efficienza della generazione delle catene di hash negli schemi di firma basati sugli hash. Per raggiungere questo obiettivo, introduciamo una nuova costruzione chiamata SpongeGr, insieme alla sua versione duplex, SpongeGr-D, basata su funzioni spugna. L'integrazione di SpongeGr-D in WOTS consente una riduzione del tempo per firare un messaggio fino al 56% rispetto alle soluzioni più avanzate.