MPC-in-the-Head In Contention To Replace RSA, ECDSA and EdDSA For Signatures

MPC-in-the-Head In Contention To Replace RSA, ECDSA and EdDSA For Signatures

Small keys and a relatively large signature

And so NIST has set up Round 1 of the Additional Signatures for PQCs [here]. These are grouped as follows:

• Multivariate Signatures (10): 3WISE, DME-Sign, HPPC (Hidden Product of Polynomial Composition), MAYO, PROV (PRovable unbalanced
   Oil and Vinegar), QR-UOV, SNOVA, TUOV (Triangular Unbalanced
   Oil and Vinegar), UOV (Unbalanced Oil and Vinegar), and VOX.
• MPC-in-the-Head Signatures (7): Biscuit, MIRA, MiRitH (MinRank in the Head), MQOM (MQ on my Mind), PERK, RYDE, and SDitH (Syndrome Decoding in the Head).
• Lattice-based Signatures (6): EagleSign, EHTv3 and EHTv4, HAETAE, HAWK, HuFu (Hash-and-Sign Signatures From Powerful Gadgets), and SQUIRRELS ( Square Unstructured Integer Euclidean Lattice Signature).
• Code-based Signatures (5): CROSS (Codes and Restricted Objects Signature), Enhanced pqsigRM, FuLeeca, LESS (Linear Equivalence), MEDS (Matrix Equivalence Digital Signature).
• Symmetric-based Signatures (4): AIMer, Ascon-Sign, FAEST, and SPHINCS-alpha.
• Other Signatures (4): ALTEQ, eMLE-Sig 2.0 (Embedded Multilayer Equations with Heavy Layer Randomization), KAZ-SIGN (Kriptografi Atasi Zarah), Preon, and Xifrat1-Sign.I
• Isogeny Signatures (1): SQIsign.

In the first round, two lattice methods were chosen (Dilithium and FALCON) and SPHINCS+ (hash-based signature). We can see that there are six lattice methods that have been put forward. As NIST is probably going to be looking for a non-lattice method to provide additional signatures. Thus the two most popular methods are multivariate signatures and MPC-in-a-head. My personal favouriate is multivariate signatures, and the basic theory is here:

So, let’s have a look at the next most popular method: MPC-in-the-Head.

MPC-in-the-Head Signatures

In the previous round we saw Picnic and which is an MPC-in-the-Head approach [2, 3]. 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 a nonce value.

Speed

In terms of speed, we see that for key generation, Pinic is the fastest of all the methods in Round 1, but it is weaker for signing and verifying. The lattice method of Dilithium is a good all-rounder [here]:

With key sizes, we see that Picnic has small key sizes. With Picnic 1 we have 33 bytes for the public key, 49 bytes for the private key, but 34,036 bytes for the signature [here]:

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:

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:

https://asecuritysite.com/pqc/picnic01

Conclusions

Picnic is fairly fast and produces small keys, but the digital signature size is large. If we replace the RSA or ECDSA signature in TLS, then for a 34K signature, we would need over 23 packets to send the signature — which will have a large overhead. It is yet to be seen if the new MPC-in-the-head methods can reduce the signature size.

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].