Digital Signatures for the Future: Dilithium, FALCON and SPHINCS+

And so, our world of digital signatures revolves around RSA, ECDSA and EdDSA. We have long since dropped DSA, and only just approved EdDSA…
Photo by Signature Pro on Unsplash

Digital Signatures for the Future: Dilithium, FALCON and SPHINCS+

And so, our world of digital signatures revolves around RSA, ECDSA and EdDSA. We have long since dropped DSA, and only just approved EdDSA to be part of FIPS 186. But, all of these methods are under threat from quantum computers, and so we must bring in new methods which are quantum robust. The three methods that NIST has defined for standardization are:

  • CRYSTALS-Dilithium. Lattice-based. We have Dilithium2 (Level 1), Dilithium3 (Level 3), and Dilithium5 (Level 5). Level 1 is equivalent to 128-bit AES, Level 3 to 192-bit AES, and Level 5 to 256-bit AES.
  • Falcon. Lattice-based. We have Falcon-512 (Level 1) and Falcon-1024 (Level 5).
  • SPHINCS+. Hash-based. SPHINCS+-128 (Level 1), SPHINCS+-192 (Level 3), and SPHINCS+-256 (Level 5).

The following shows a sample run for timings with key generation, signing and verifying [here]:

We can see out of the three methods that Dilithium has the best performance in all areas compared with FALCON and SPHINCS+, with SPINHCS+-Haraka performing the best for SPHINCS+. FALCON has a weaker performance for key generation than Dilithium but does fairly well for signing and verification. As the key generation part is less likely to happen than signing and verification, it is not a major problem.

Where SPHINCS+ does well is the size of the private and the public key, and where we have a 32-byte private key and a 64-byte public key. This is similar to ECC, which has a 256-bit (32-byte) and 512-bit (64-byte) public key. Unfortunately, the digital signature is over 17kB in size [here]. While Dilithium has good performance levels, FALCON beats it on the size of the signature created, and where FALCON-512 has a 690-byte signature, as opposed to Dilithium-2 with a 2,420-byte signature.

Dilithium has a 1,312-byte private key and a 2,528-byte public key, and with a 2,420-byte signature. Falcon has similar key sizes. In summary the key sizes are:

Method                       Public key size    Private key size   Signature size  Security level
------------------------------------------------------------------------------------------------------
Crystals Dilithium 2         1,312              2,528              2,420         1 (128-bit) Lattice
Crystals Dilithium 3         1,952              4,000              3,293         3 (192-bit) Lattice
Crystals Dilithium 5         2,592              4,864              4,595         5 (256-bit) Lattice
Falcon 512 (Lattice)           897              1,281                690         1 (128-bit) Lattice
Falcon 1024                  1,793              2,305              1,330         5 (256-bit) Lattice
Sphincs SHA256-128f Simple      32                 64             17,088         1 (128-bit) Hash-based
Sphincs SHA256-192f Simple      48                 96             35,664         3 (192-bit) Hash-based
Sphincs SHA256-256f Simple      64                128             49,856         5 (256-bit) Hash-based
RSA-2048                       256                256                256
ECC 256-bit                     64                 32                256

SPHINCS+

In the last 20 years, Daniel J Bernstein (djb) has contributed so much to cryptography, and in building a more trusted world. He created research around ChaCha20, Salsa20, Curve 25519, twisted elliptic curves, AES timing attacks, and so much more. But one of his core contributions is with SPHINCS+ [here]:

So while most hash-based methods suffer from having to remember the private keys which have signed previous messages, SPHINCS is a stateless hash-based signature scheme.

Overall SPHINCS+ 256 128-bit has a public key size of 32 bytes, a private key size of 64 bytes, and a signature of 17KB kB. It has been shown to operate at speeds of hundreds of hashes per second on a 4-core 3.5GHz processor. Other hashing methods are Haraka and SHAKE-256, for 128-bit, 192-bit and 256-bit versions.

It uses WOTS and HORST for hash-based trees and uses a number of parameters:

  • n — length of hash in WOTS / HORST (in bits)
  • m — length of message hash (in bits)
  • h — height of the hyper-tree
  • d — layers of the hyper-tree
  • w — Winternitz parameter used for WOTS signature
  • tau — layers in the HORST tree (2^tau is no. of secret-key elements)
  • k — number of revealed secret-key elements per HORST signature

In the example we use: n=256, m=512, h=2, d=1, w=4, tau=8, k=64.

The hashing method used in some of the operations is BLAKE, and ChaCha is used to generate a random number.

Winternitz one time signature scheme (W-OTS)

W-OTS uses relatively small key and signatures sizes, and is thought to be quantum robust. It generates 32×256 bit random private keys. We then have these a number of times, and is defined by a parameter (w). If we use w=8, we hash the private keys by (2w). This creates 32×256 bits public keys. The signature is the created by taking eight bits at a time, and then the 8-bit binary int (n) is subtracted from 256 and the private key is the hashed 256-n times. The signature is then 32 hashes which are derived from random private keys. To verify the signature, the recipient parses the hash of the signature (using 8 bits at a time, and extracting the 8 bit int, n). The signature is then derived from the signature.

The method is:

  • Initially, we create 32 256-bit random numbers. These 32 values will be our private key.
  • We then hash each of these values 256 times. These 32 values will be our public key.
  • We now take the message and hash it using SHA-256. This produces 32 8-bit values (N1, N2 … N32).
  • For the signature, we take each 8-bit value in the hash of the message, and then hash 256-N times (where N is the value of the 8-bit value).
  • To prove the signature, we take the message and hash it with SHA-256, and then take each 8-bit value. We then hash the 8-bit signature value by the number of times defined by the message hash value (N1, N2..). The result for each operation should equal the public key value.

This is illustrated below:

A sample run that just shows the first few private keys and the first public keys:

Hashing number:	256
==== Private key (keep secret) =====
Priv[0]:  bd344c6110628aa38c9b5ca6458bed7b78425b2e82efa0624a578031562f82ee
Priv[1]:  20670af5b1663fa9fad49fab6a692ae5989cff77439f98d2288f173b17a8d99f
Priv[2]:  625aa290fd1f88c930451ff743d5d9ef90e7064368fb23a18c9fd048474818f2
Priv[3]:  ee0e1363cbd5f61017ba27bfe91ec53969d28d143ed59a99efb020941bc4990f
Priv[4]:  ce94d7282ee3f7b05b99768695ff224b5994900c6182dfb89d596d8b7b405ec6
Priv[5]:  d0c59651e951b0bb8d5a2d7b93f6739c9ce4a0c0c0f63bfce23b331b947eb285
==== Public key (show everyone)=====
Pub[0]:  45fdac6339e80cadd1331cce026cd0364ea84146a36f6f3f2449b66fb55a217a
Pub[1]:  184cf92f22072fef078fa4a93ec2044f07ac8b12e326509474209312cace8a5a
Pub[2]:  a47548d4537bd284e7d7f935f41570866d9c6a72c463bb2a2b10c8c7907621f0
Pub[3]:  60395e575522cacb70d866211c64e8a74e562c79d1fffce224d1013d088bf66f
Pub[4]:  8be7b53d5b56e698b8798f2a707fba7b8e417554fd489d74cc40fe8574d7589e
Pub[5]:  9fac35971dae3a5c77ae7b5c720a72f90ee53852668c96c78e095cbb52af20a1
==== Message to sign ===============
Message:	The quick brown fox jumps over the lazy dog
SHA-256:	d7a8fbb307d7809469ca9abcb0082e4f8d5651e46d3cdb762d02d0bf37c9e592
==== Signature =====================
Sign[0]:	45cb53c5c33af9b20426fd0233fd63d92bf0c2ded367163e6f2f93588a33c6d8
Sign[1]:	e8c35987101f2d11d7056a2fe78069d3ed73aee315ebef8c2d40e04973301c26
Sign[2]:	59220d80b7c958957b28511f4081341cc4a00a0d6d5e1d05351be7dec3ca8aaa
Sign[3]:	72a906d719be18e1592314bf6f6c521a325a9de2b5b9e9e13117bf01b0157f5c
The signature test is  True

A demonstration of the method is given here.

Implementation

SPHINCS+ has short public and private keys, but it has a much longer signature than Dilithium and Falcon [here]:

For the same security level, SPHINCS+ has a 49KB signature compared with just 4K for Dilithium and 1KB for Falcon. The following is an implementation of SPHINCS+ [here]:

#include "api.h"
#define MLEN 59
char *showhex(uint8_t a[], int size) ;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 i, j;
  int ret;
  size_t mlen, smlen;
  uint8_t b;
  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];
    randombytes(m, MLEN);    crypto_sign_keypair(pk, sk);
    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;
      }
    }
    randombytes((uint8_t *)&j, sizeof(j));
    do {
      randombytes(&b, 1);
    } while(!b);
    sm[j % (MLEN + CRYPTO_BYTES)] += b;
    ret = crypto_sign_open(m2, &mlen, sm, smlen, pk);
    if(!ret) {
      fprintf(stderr, "Trivial forgeries possible\n");
      return -1;
    }
  
  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(pk,CRYPTO_SECRETKEYBYTES));  printf("\nMessage: %s\n",showhex(m,MLEN));
  printf("Signature (Showing 1/32th of signature): %s\n",showhex(sm,smlen/32));
  return 0;
}

A sample run of SPHINCS+ 128 shows that the public key size is 32 bytes, the secret key is 64 bytes, and the digital signature is 17,088 bytes:

NAME: SPHINCS+
CRYPTO_PUBLICKEYBYTES = 32
CRYPTO_SECRETKEYBYTES = 64
CRYPTO_BYTES = 17088
Signature Length + Msg = 17147Alice Public key: 2fbdcbb6ec87851c3674e0a38f551ca1bb44677ae13969ed16c1350fe95238ce
Alice Secret key: 2fbdcbb6ec87851c3674e0a38f551ca1bb44677ae13969ed16c1350fe95238ce79fb06c5872fbccf30afefc46d1a74791273744e66c59a1b517278a58c33b706Message: 79fb06c5872fbccf30afefc46d1a74791273744e66c59a1b517278a58c33b7062fbdcbb6ec87851c3674e0a38f551ca1c890f02e568a49a7fcc14c
Signature (Showing 1/32th of signature): d681767c6c41ecd17ffd2eda21143b305e133be88bb770a451403a199d9de6e292b16fb4d614817e28e14f07809488f506d18c58db6a3d9106b357a333d75e3d10c9ba78a7eb1a070a08084ee6878b95c9d7c9d24fa377f4131d07dbb07c123eb88a9e8196699f2ed35a62a3fd2c25eb4398a43bc89dd9f3f9fbd479d34395bfba932d9971e68e560b93ceac905afe3a0c87311b345e72fec4b67f0094a693e14fafd890498b3fd0c4c7dfa4f594d35413f3489a40c06bd2c82b8cd4d101a3afba346cf6cd723d23f8aeeee8c8bbcc4f5d70a5975815cad42bc3a59ff5f4af7dc07c9cc26002d25c9a4f2c55e45136f37d4c7a5055c0a76736578da27994472fe81409d1b4578d05d4256444a152e437368040addd4b25c452578199f855ea090a3afe6b49df75505385d8a76460ad0ff8e290ca5db7a0c4a2aab38ad1c544f273776ccb5d12bfaca08271319b3b4aa7b179d5b31034366664cd5290be8f411170015c8f07286445ef6164a5fff825dda62ea61a56418c4a62955537904d87ac2f89b1b5e8c6208fa9192f21019d6730b39dfe8bb4e681551f75902e92a1ff92adf6eaa773c6d0937fcb6abc583872cc61f8ab136e8dbffa43c4711f7677553efaadea1c12002acf0ec222a8217d22ea896d2de8df88704296ff1be222fa8b1a09af78ef2a0483c0b525e04563eaf2db5001d884d74c6a609da361a7808be4264bc00fb56c9fc382f80bd0a150211f817991a25bfaf804

Conclusions

And, so, the focus is on Dilithum for a general-purpose method, but where FALCON wins on signature sizes. As Dilithium and FALCON are lattice methods, we need an alternative: SPHINCS+. Overall, SPHINCS+ has a small key pair size, but the signature is fairly large.