Let’s Go For A Post-Quantum Picnic

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 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 illustrated in Figure 1.

While many zero-knowledge proof methods use the Fiat-Shamir or Schnorr approach, Picnic uses a MPC-in-the-head approach by using an MPC method where Peggy takes an arbitrary circuit (made up of AND and XOR gates) and where it goes through the main steps involved in the MPC, and then shows the working out to Victor (the verifier). The LowMC circuit has been selected as it allows Peggy to compute a zero-knowledge proof for Victor to show that she knows her secret key (sk). LowMC defines a family of block ciphers that can be used in multi-party computations (MPC) and fully homomorphic encryption methods.

Key pair generation and signing

In the method (as illustrated in Figure 2), 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 knowledge of sk so that C=LowMC(sk,p), and where the message m and public key pk are integrated with the proof for the signature. With this, the signature is basically a proof of knowledge of sk using the message as nonce value.

Head-to-head

Picnic and SPHINCS+ both produce small public and private keys. For Picnic 3, we have a 49 byte public key and a 73 byte private key, and which easily beats Dilithium, Falcon and Rainbow. But, its weakness is the size of the signature, and which is 71kB as appose to just 2–4K for Dilithium:

Coding

Here is the coding for Picnic [here]:

#include stdio.h
#include stdint.h
#include stdlib.h
#include time.h

#include "api.h"
#include "picnic.h"


#define MLEN 59


char *showhex(uint8_t a[], int size) ;
int randombytes (unsigned char* random_array, unsigned long long num_bytes);

char *showhex(uint8_t a[], int size) {


    char *s = malloc(size * 2 + 1);

    for (int i = 0; i < size; i++)
        sprintf(s + i * 2, "%02x", a[i]);

    return(s);
}

int main(void)
{
  size_t j;
  int ret;

  uint8_t m[MLEN + CRYPTO_BYTES];
  uint8_t m2[MLEN + CRYPTO_BYTES];
 // uint8_t sm[MLEN + CRYPTO_BYTES];
  uint8_t pk[CRYPTO_PUBLICKEYBYTES];
  uint8_t sk[CRYPTO_SECRETKEYBYTES];
 unsigned char sm[sizeof(m) + CRYPTO_BYTES];
 long long unsigned int smlen = sizeof(sm);

    unsigned char mprime[50] = { 0 };
 
    long long unsigned int mlen = sizeof(mprime);


    randombytes(m, MLEN);

    crypto_sign_keypair(pk, sk);

  printf("NAME: %s\n", CRYPTO_ALGNAME);
  printf("CRYPTO_PUBLICKEYBYTES = %d\n", CRYPTO_PUBLICKEYBYTES);
  printf("CRYPTO_SECRETKEYBYTES = %d\n", CRYPTO_SECRETKEYBYTES);
  printf("CRYPTO_BYTES = %d\n", CRYPTO_BYTES);

//  printf("Signature Length + Msg = %ld\n", smlen);

  printf("\nAlice Public key: %s\n",showhex(pk,CRYPTO_PUBLICKEYBYTES));
  printf("Alice Secret key: %s\n",showhex(sk,CRYPTO_SECRETKEYBYTES));

  printf("\nMessage: %s\n",showhex(m,MLEN));


    crypto_sign(sm, &smlen, m, MLEN, sk);
    ret = crypto_sign_open(m2, &mlen, sm, smlen, pk);


    if(ret) {
      fprintf(stderr, "Verification failed\n");
      return -1;
    }

/*
    if(smlen != MLEN + CRYPTO_BYTES) {
      fprintf(stderr, "Signed message lengths wrong\n");
      return -1;
    }  */

    if(mlen != MLEN) {
      fprintf(stderr, "Message lengths wrong\n");
      return -1;
    }
    for(j = 0; j < MLEN; ++j) {
      if(m2[j] != m[j]) {
        fprintf(stderr, "Messages don't match\n");
        return -1;
      }
    }


 
  

  printf("Signature (Showing 1/128th of signature): %s\n",showhex(sm,smlen/128));
  return 0;
}

int randombytes (unsigned char* random_array, unsigned long long num_bytes)
{
 // unsigned char *random_array = malloc (num_bytes);

  size_t i;

srand ((unsigned int) time (NULL));

  for (i = 0; i < num_bytes; i++)
  {
    random_array[i] = rand ();
  }

  return 0;
}

A sample run of Picnic shows that the public key size is just 49 bytes, the secret key is 73 bytes, and the digital signature of 71,1179 bytes [here]:

NAME: picnicl3full
CRYPTO_PUBLICKEYBYTES = 49
CRYPTO_SECRETKEYBYTES = 73
CRYPTO_BYTES = 71179

Alice Public key: 0befe6cd9b6298fb28b875877bd0197f1f0306846d6acfcf490c17dec49021434b1778b7c957ceb31ebdab2bbd02b5c40e
Alice Secret key: 0b0c17dec49021434b1778b7c957ceb31ebdab2bbd02b5c40eefe6cd9b6298fb28b875877bd0197f1f0306846d6acfcf490c17dec49021434b1778b7c957ceb31ebdab2bbd02b5c40e

Message: 0c17dec49021434b1778b7c957ceb31ebdab2bbd02b5c40eff304211c2c13f45e17723c80e0b50bfec679df8226606ceaddba24d7ad4d5973420c6
Signature (Showing 1/128th of signature): 3b0d01000c17dec49021434b1778b7c957ceb31ebdab2bbd02b5c40eff304211c2c13f45e17723c80e0b50bfec679df8226606ceaddba24d7ad4d5973420c699185102220a6a94a04222064298054622469652911926a189665595aa5a068a0818291a0a4416614860502659552996666282151692a666a86a0a92486954282522809a11a4606418664665a4281856969140c99a5ce4f10595cc914919cbb542f391d5a3b603942cb1cbc0c2413e5c9e7f92a3f03b2e9733773beecdaadf9d89195c4548dc011be0a67ed282a1c10e09fc5285ebf68936196c058fdc0805b5695eb54daeb50ef5f8c550dda600173f344c7fd29f2b17821d7aa662c10b8cfbdedff941d2ed143c512e4732e1932a28cab803bcf4455e83401e1cef9684fcebb29cef2b05f39491b7d8499099e4e824504273cd59a47f0eed02fada506e2fc93f465fa799e022f593fdbaa16f9b7504c8ddc0c90a873588ae3b61bd2c81fd86c4c9f9200fb4876a37de821bc80191304f0d5509ec8828def45e2a14c49bab2f3a3649a2d6dcf36a67a06188730d4c5e667fb2bd691073e9e13e62fee98a8501f789d23b3ed8858d333ff89085c9152992c384984cf39f38be3b05b10b4fb20a79b54183be611e7668df5b02b28cfc1829a60ed02d3b8c65d2db619c1e12a53198a924c34978efdfd284b5b5b35a7867d8b3b415dfb349f4a80a7b5e0aad036b9d132aa2488653297d69f6835b2d478969c180a4d1ceec282ee087

The full code is here:

Conclusions

Picnic is fast and produces small keys, but the digital signature size is large. It’s a great method, but some devices would struggle with the size of the signature it produces. And so, it’s not in the winner final, but I don’t think it will win in the alternative final too. But, in a range of applications it is a winner, and it unlikely to go away.

And so its … GeMSS v SPHINCS+ v Picnic. For betting, it is difficult as they have strengths and weakensses. GeMSS has a small signature size, but large keys, Picnic has small keys but a large signature, and SPHINCS+ has a simlar key size and signature size to Picnic. So I’d say:

• Picnic. 6/4 (co-fav).
• SPHINCS+. 6/4 (co-fav).
• GeMSS. 3/1.

References

[1] Ishai, Y., Kushilevitz, E., Ostrovsky, R., & Sahai, A. (2007, June). Zero-knowledge from secure multiparty computation. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing (pp. 21–30).

[2] Chase, M., Derler, D., Goldfeder, S., Orlandi, C., Ramacher, S., Rechberger, C., … & Zaverucha, G. (2017, October). Post-quantum zero-knowledge and signatures from symmetric-key primitives. In Proceedings of the 2017 acm sigsac conference on computer and communications security (pp. 1825–1842). [here].

[3] Chase, M., Picnic Post-Quantum Signatures from Zero Knowledge Proofs [slides]

[4] Kannwischer, M. J., Rijneveld, J., Schwabe, P., & Stoffelen, K. (2019). pqm4: Testing and Benchmarking NIST PQC on ARM Cortex-M4 [here].