PCQ is (No) 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.

The three alternative winner finalists are SPHINCS+, GeMSS and Picnic. With SPHINCS+ we use hashes to produce the signature, and with Picnic, we use symmetric key cipher blocks and hashes. So let’s go for a Picnic [2, 3].

Picnic is one of the alternative finalists for the NIST standard for PQC (Post Quantum Cryptography) [1]. In the method, we generate a random plaintext block (p), and a random secret key (sk). Next we compute C=LowMC(sk,p), and then determine the public key of pk=(C,p). To sign we define knowledge the knowlege of sk so that C=LowMC(sk,p), and where the message m and public key pk are integrated wit the proof for the signature. With this the signature is basically a proof of knowledge of sk using the message as nonce value. LowMC defines a family of block ciphers that can be used in multi-party computations (MPC) and fully homomorphic encryption methods…