PCQ is (No) Picnic

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 [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 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 [5] defines a family of block ciphers that can be used in multi-party computations (MPC) and fully homomorphic encryption methods.

Key pair generation/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 a nonce value.

MPC-in-a-head

With this we have N parties and a private input of xi_, and we need to compute f(x1,…,xn), so that if (n−1) entities share their details, it will not reveal anything. Thus to provide that Peggy knows x such that:

F(x)=1

we can select values to define that:

x_1⊕x_2⊕…+x_n=x

We then run a MPC to compute:

F(x1⊕x2⊕…+xn)

The verifier (Victor) selects a value of i and the prover reveals all the values apart from i. If you want to find out more about LowMC, try here:

Performance evaluation

The following provides an analysis of the PCQ methods for digital signing in relation to key and signature sizes:

The three alternative methods are Sphincs+, Picnic and GeMSS. We can see that Sphincs and Picnic have relatively small keys, but a large signature than GeMSS.

Coding

The following is an implementation of 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:

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

Conclusions

I think that GeMSS produces signatures that are too large, so my betting odds for the alternative method is:

4/5 (fav) Sphincs
5/4 Picnic
5/1 GeMSS (the private key and the signature sizes are relatively small, but the public is rather large).

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.

[5] Dinur, I., Kales, D., Promitzer, A., Ramacher, S., & Rechberger, C. (2019, May). Linear equivalence of block ciphers with partial non-linear layers: application to LowMC. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (pp. 343–372). Springer, Cham [paper].