Let’s Go For A Post-Quantum Picnic

And then there were three: CRYSTALS Dilithium, Falcon and Rainbow. These are the finalists for the NIST standard for Post Quantum Cryptography (PQC) of digital signatures. Basically, they will replace RSA and ECC in an era of quantum computers, and provide the core of trust on the Internet. Dilithium and Falcon are lattice methods, and Rainbow uses multivariate quadratic polynomials. So while lattice looks like a winner because of its speed of computation and key size, there is a competition for an alternative winner.

Two of the alternative winner finalists are SPHINCS+ and Picnic. These methods have a core advantage of using symmetric key approaches to digital signing, and where symmetric key methods are robust against quantum computers and generally fast in their operation. With SPHINCS+ we use hashes to produce the signature, and with Picnic, we use symmetric key cipher blocks and hashes. The third alternative finalist is GeMSS (Great Multivariate Short Signature) and which is a multivariate based approach (and similar in its method to Rainbow).

So let’s go for a Picnic [2, 3].

Picnic

Picnic uses non-interactive zero-knowledge proofs of knowledge and MPC (Multiparty Computation). With MPC we can split a problem into a number of computing elements, and these can be worked on in order to produce the…