A survey of post-quantum signatures based on the Fiat-Shamir heuristic

One of the leading topic regarding cryptography of the last years is doubtless the security against quantum computing. We analyzed protocols from the last thirty years of the state of art. Such protocols rely on NP-complete problem called Syndrome decoding to implement an interactive identification protocol. Afterwards, once the security is established, the use of the Fiat-Shamir (FS) heuristic permits to transform them in non-interactive digital signatures protocols. Our aim is to give guidelines to approach the SD protocol as well as FS heuristic for the first time, along with the creation of a standard suite of optimization to include in all the future implementations. Concretely, we studied the most relevant protocols, gathered optimization in macro groups based on the impact they have on the protocol, constructed a suite of optimization that can be considered the standard minimum of the state of art and tested standard performances of these protocols.

Uno degli argomenti principali riguardo la crittografia negli ultimi anni è senza dubbio la sicurezza rispetto alla computazione quantistica. Abbiamo analizzato protocolli appartenenti agli ultimi trenta anni dello stato dell'arte. Tali protocolli si basano su un noto problema NP-complete chiamato decodifica di sindrome (SD) per implementare protocolli di identificazione interattiva. Succesivamente, una volta stabilita la sicurezza, l'uso dell'euristica di Fiat-Shamir (FS) permette di transformarli in protocolli di firme non interattivi. Il nostro obiettivo è quello di tracciare linee guida per approcciare sia SD che FS per la prima volta assieme alla creazione di una suite standard di ottimizzazioni da includere in nuove implementazioni. Concretamente abbiamo studiato i protocolli più rilevanti, raccolto ottimizzazioni in macro gruppi differenziati dall'impatto che questi hanno sul protocollo, costruito una suite di ottimizzazioni che può essere lo standard minimo per lo stato dell'arte e abbiamo testato performance standard dei suddetti protocolli.