For Digital Signatures, It’s Lattice or Picnics?
--
And then there were three: CRYSTALS Dilithium, Falcon and Rainbow — well two, because Rainbow has been cracked. 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].
What is Picnic?
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 [2].
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 result, and where none of the elements can see the working out at intermediate stages. Overall Picnic uses the MPC-in-the-head method defined in [1]. The great advantage of this method is that we only use symmetric key methods (block ciphers and hashing functions).
To generate her signing key, Peggy (the prover) generates a random symmetric key. This will be her private key (sk). She then creates a publicly available plaintext block and then encrypts this with her symmetric key into a public ciphertext block. These two elements become then become her public key, as…
