Casanova and A Post Quantum World

Casanova and A Post Quantum World

Well, we’ve all seen the signs that say “The Best Coffee Ever!”, but when it comes to a post-quantum world of digital signatures, a paper that promises the shortest signature ever just grabs your attention [here]:

It uses a multivariate method [here]. There are a number of multivariate methods including UOV [here] and Rainbow [here]. The shortest ever signature is used in the GeMSS (Great Multivariate Short Signature) method. It was created by Casanova et al uses the HFEv- method [here]:

We can see in Figure 1 that GeMSS has the smallest private key (16 bytes), and the smallest signature size (33 bytes) for 128-bit security. The downside is that large public key size, and which rivals the other multivariant method: Rainbow:

Unfortunately, GeMSS just needs too much memory, and failed to reach the final round of the NIST PCQ standard. While Rainbow made the final, GeMSS only managed to be considered as an alternative. As Rainbow is unlikely to win against the lattice methods (Falcon and Dilithium), GeMSS has a chance to win as an alternative method against Picnic and SPHINCS+:

It is almost certain that a lattice method will win the digital signature method, as they have good all-round performance and key sizes. With the alternative methods, we have GeMSS (Multivariant), Picnic (Symmetric) and SPHINCS+ (Hash-based). If we look at these on their own:

                              Public Private Sign
Sphincs SHA256-128f Simple       32    64  17,088        
Sphincs SHA256-192f Simple       48    96  35,664       
Sphincs SHA256-256f Simple       64   128  49,856         
Picnic 3 Full                    49    73  71,179         
GeMSS 128                   352,188    16  33 
GeMSS 192                 1,237,964    24  53        

We can see that GeMSS wins for its signature sizes, but Sphincs and Picnic win on the public and private key sizes. So, I’d say GeMSS does not have a chance, as it would not be well supported on devices which a limited amount of memory. But, if you want the shortest signature ever, best with Casanova et al. Here is my demo of the method: