MPC-in-the-Head post-quantum signature scheme: public and private key sizes are small, but signature size is too large

1. Introduction

Preface blog:

  • Digital signature schemes of the future: Dilithium, FALCON and SPHINCS+

NIST has established PQC Additional Signatures Round 1. For details, see:

  • Post-Quantum Cryptography: Digital Signature Schemes – Round 1 Additional Signatures

The current finalists are:

  • 1) 10 signature schemes based on multi-variables:
    • 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)
    • VOX
  • 2) 7 signature schemes based on MPC-in-the-Head:
    • Biscuit
    • MIRA
    • MiRitH (MinRank in the Head)
    • MQOM (MQ on my Mind)
    • PERK
    • RYDE
    • SDitH (Syndrome Decoding in the Head)
  • 3) 6 signature schemes based on Lattice:
    • EagleSign
    • EHTv3 and EHTv4
    • HAETAE
    • HAWK
    • HuFu (Hash-and-Sign Signatures From Powerful Gadgets)
    • SQUIRRRELS (Square Unstructured Integer Euclidean Lattice Signature)
  • 4) Five signature schemes based on Code:
    • CROSS (Codes and Restricted Objects Signature)
    • Enhanced pqsigRM
    • FuLeeca
    • LESS (Linear Equivalence)
    • MEDS (Matrix Equivalence Digital Signature)
  • 5) 4 signature schemes based on Symmetric:
    • AIMer
    • Ascon-Sign
    • FAEST
    • SPHINCS-alpha
  • 6) 1 signature scheme based on Isogeny:
    • SQIsign
  • 7) 5 other signature schemes:
    • ALTEQ
    • eMLE-Sig 2.0 (Embedded Multilayer Equations with Heavy Layer Randomization)
    • KAZ-SIGN (Kriptografi Atasi Zarah)
    • Preon
    • Xifrat1-Sign.I

In the first round, 2 lattice signature schemes (Dilithium and FALCON) and 1 domain hash-based signature scheme (SPHINCS+) have been selected.
There are already 6 Lattice-based signature schemes in this round. NIST will probably look for non-lattice solutions to provide additional signatures. There are currently 2 popular options:

  • Multivariate-based signature scheme: For details, see Multivariate Cryptography Comes Storming Back for PQC [Look out for this]
  • Signature scheme based on MPC-in-the-head: Taking Picnic as an example, the private key and public key sizes are small, but the signature size is large. If used to replace RSA or ECDSA in TLS, for a 34K signature, more than 23 packets are needed to send the signature, which is a huge overhead.

2. Signature scheme based on MPC-in-the-head

In the previous round, Picnic was a signature scheme based on MPC-in-the-head.
Picnic uses:

  • ZKP
  • + MPC: A certain problem can be divided into multiple calculation elements, and then the results can be generated collaboratively without exposing any elements in the intermediate stage.

The advantage of the Picnic scheme is that it only requires the use of a symmetric key scheme (block encryption and hash function).

As shown in the picture above, Peggy (Prover):

  • In order to generate a signature key, a random symmetric key needs to be generated as its private key sk.
  • Create a publicly available plaintext block and encrypt the plaintext block using its symmetric key to obtain a publicly encrypted block.
  • Use the private key sk and the public encryption block as Peggy’s public key.

Although many ZKP schemes use Fiat-Shamir or Schnorr, Picnic adopts an MPC-in-the-head scheme, through a certain MPC scheme:

  • Peggy obtains an arbitrary circuit LowMC composed of AND and XOR gates, then runs the main flow of the circuit in MPC, and then sends the running results to Victor (Verifier).
  • The selected LowMC circuit should support Peggy to calculate ZKP for Victor to show that Peggy knows his private key sk.
  • A family of block ciphers is defined in the LowMC circuit, which can be used in MPC and fully homomorphic encryption.

2.1 Key pair generation and signing

As shown in the figure above, the basic process is:

  • Generate a random plaintext block p, and a random private key sk.
  • calculate

    C

    =

    L

    o

    w

    M

    C

    (

    s

    k

    ,

    p

    )

    C=LowMC(sk,p)

    C=LowMC(sk,p), and define the public key as pk=(C,p).

  • Signature: The signature treats the message as a nonce value and knows the proof of the corresponding private key sk:
    • Define knowing sk such that

      C

      =

      L

      o

      w

      M

      C

      (

      s

      k

      ,

      p

      )

      C=LowMC(sk,p)

      C=LowMC(sk,p).

    • Define the sk corresponding to the message m in the signature and the public key pk.

2.2 Speed comparison

In the key generation phase, Picnic is the fastest, but its signature and signature verification speeds are slightly weaker, and the Dilithium solution based on Lattice is an all-rounder:

At the same time, Picnic has the smallest key size. The public key of Picnic_L1_FS is 33 bytes and the private key is 49 bytes, but its signature is 34036 bytes.


Both Picnic and SPHINCS+ have small public and private keys. Taking Picnic_L3_FS as an example, its public key is 49 bytes and its private key is 73 bytes, which can easily defeat Dilithium, Falcon and Rainbow. Picnic’s main weakness is its large signature size, which requires 71kB, while Dilithium only requires 2kB to 4kB.

Picnic code example is:

#include stdio.h
#include stdint.h
#include stdlib.h
#include time.h
#include "api.h"
#include "picnic.h"

#defineMLEN 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, " x", 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\
", CRYPTO_ALGNAME);
  printf("CRYPTO_PUBLICKEYBYTES = %d\
", CRYPTO_PUBLICKEYBYTES);
  printf("CRYPTO_SECRETKEYBYTES = %d\
", CRYPTO_SECRETKEYBYTES);
  printf("CRYPTO_BYTES = %d\
", CRYPTO_BYTES);
// printf("Signature Length + Msg = %ld\
", smlen);
  printf("\
Alice Public key: %s\
",showhex(pk,CRYPTO_PUBLICKEYBYTES));
  printf("Alice Secret key: %s\
",showhex(sk,CRYPTO_SECRETKEYBYTES));
  printf("\
Message: %s\
",showhex(m,MLEN));

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

    if(ret) {<!-- -->
      fprintf(stderr, "Verification failed\
");
      return -1;
    }
/*
    if(smlen != MLEN + CRYPTO_BYTES) {
      fprintf(stderr, "Signed message lengths wrong\
");
      return -1;
    } */
    if(mlen != MLEN) {<!-- -->
      fprintf(stderr, "Message lengths wrong\
");
      return -1;
    }
    for(j = 0; j < MLEN; + + j) {<!-- -->
      if(m2[j] != m[j]) {<!-- -->
        fprintf(stderr, "Messages don't match\
");
        return -1;
      }
    }

 
  
  printf("Signature (Showing 1/128th of signature): %s\
",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;
}

The running result is:

NAME: picnicl3full
CRYPTO_PUBLICKEYBYTES = 49
CRYPTO_SECRETKEYBYTES = 73
CRYPTO_BYTES = 71179
Alice Public key: 0befe6cd9b6298fb28b875877bd0197f1f0306846d6acfcf490c17dec49021434b1778b7c957ceb31ebdab2bbd02b5c40e
Alice Secret key: 0b0c17dec49021434b1778b7c957ceb31ebdab2bbd02b5c40eefe6cd9b6298fb28b875877bd0197f1f0306846d6acfcf490c17dec49021434b1778b7c957ceb31eb dab2bbd02b5c40e
Message: 0c17dec49021434b1778b7c957ceb31ebdab2bbd02b5c40eff304211c2c13f45e17723c80e0b50bfec679df8226606ceaddba24d7ad4d5973420c6
Signature (Showing 1/128th of signature): 3b0d01000c17dec49021434b1778b7c957ceb31ebdab2bbd02b5c40eff304211c2c13f45e17723c80e0b50bfec679df8226606ceaddba24d7ad4d5 973420c699185102220a6a94a04222064298054622469652911926a189665595aa5a068a0818291a0a4416614860502659552996666282151692a666a86 a0a92486954282522809a11a4606418664665a4281856969140c99a5ce4f10595cc914919cbb542f391d5a3b603942cb1cbc0c2413e5c9e7f92a3f03b2e973 3773beecdaadf9d89195c4548dc011be0a67ed282a1c10e09fc5285ebf68936196c058fdc0805b5695eb54daeb50ef5f8c550dda600173f344c7fd29f2b17821d7aa662 c10b8cfbdedff941d2ed143c512e4732e1932a28cab803bcf4455e83401e1cef9684fcebb29cef2b05f39491b7d8499099e4e824504273cd59a47f0eed02fada506e2fc93 f465fa799e022f593fdbaa16f9b7504c8ddc0c90a873588ae3b61bd2c81fd86c4c9f9200fb4876a37de821bc80191304f0d5509ec8828def45e2a14c49bab2f3a364 9a2d6dcf36a67a06188730d4c5e667fb2bd691073e9e13e62fee98a8501f789d23b3ed8858d333ff89085c9152992c384984cf39f38be3b05b10b4fb20a79b541 83be611e7668df5b02b28cfc1829a60ed02d3b8c65d2db619c1e12a53198a924c34978efdfd284b5b5b35a7867d8b3b415dfb349f4a80a7b5e0aad036b9d132a a2488653297d69f6835b2d478969c180a4d1ceec282ee087

Reference materials

[1] Prof Bill Buchanan OBE September 2023 Blog MPC-in-the-Head In Contention To Replace RSA, ECDSA and EdDSA For Signatures–Small keys and a relatively large signature