At present, CRYSTALS (Cryptographic Suite for Algebraic Lattices) supports two quantum robust mechanisms: Kyber for key-encapsulation mechanism (KEM) and key exchange; and Dilithium for a digital signature algorithm. CRYSTALS Dilithium uses lattice-based Fiat-Shamir schemes, and produces one of the smallest signatures of all the post-quantum methods, and with relatively small public and private key sizes. The three main implements for the parameters used are: Dilithium 2, Dilithium 3 and Dilithium 5. Overall, Dilithium 3 is equivalent to a 128-bit signature, and is perhaps the starting point for an implementation.
CRYSTALS Dilithium (Lattice) - Digital Signature |
Outline
NIST are now assessing just three methods for digital signatures: CRYSTALS-DILITHIUM (led by Vadim Lyubashevsky), FALCON (led by Thomas Present) and RAINBOW (led by Jintai Ding). The three main implementations for Dilithium are: Dilithium 2 (2,479 byte - 19,832 bit - signature), Dilithium 3 (3,352 byte - 26,816 bit - signature) and Dilithium 5 (4,654 byte - 37,232 bit - signature). Overall, Dilithium 3 is equivalent to a 128-bit signature and is perhaps the starting point for an implementation.
Performance evaluation
The following provides an analysis of the PCQ methods for digital signing:
Method Public key size Private key size Signature size Security level ------------------------------------------------------------------------------------------------------ Crystals Dilithium 2 (Lattice) 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 Rainbow Level Ia (Oil-and-Vineger) 161,600 103,648 66 1 (128-bit) Multivariate (UOV) Rainbow Level IIIa 861,400 611,300 164 3 (192-bit) Multivariate (UOV) Rainbow Level Vc 1,885,400 1,375,700 204 5 (256-bit) Multivariate (UOV) 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 Picnic 3 Full 49 73 71,179 3 (192-bit) Symmetric GeMSS 128 352,188 16 33 1 (128-bit) Multivariate (HFEv-) GeMSS 192 1,237,964 24 53 1 (128-bit) Multivariate (HFEv-) RSA-2048 256 256 256 ECC 256-bit 64 32 256
For performance on M4 (ARM Cortex-M4 dev) [1] and measured in CPU operations per second. Note, no Rainbow assessment has been performed in [1], so LUOV (an Oil-and-Vinegar method) has been used to give an indication of performance levels:
Method Key Generation Sign Verify ------------------------------------------------------------------------------------------------------ Crystals Dilithium 2 1,400,412 6,157,001 1,461,284 1 (128-bit) Lattice Crystals Dilithium 3 2,282,485 9,289,499 2,228,898 3 (192-bit) Lattice Crystals Dilithium 5 3,097,421 8,469,805 3,173,500 5 (256-bit) Lattice Falcon 512 (Lattice) 197,793,925 38,090,446 474,052 1 (128-bit) Lattice Falcon 1024 480,910,965 83,482,883 977,140 3 (256-bit) Lattice Rainbow Level Ia 41,347,565 101,874,410 77,433,705 1 (128-bit) UOV Rainbow Level IIIa 66,072,054 123,878,322 95,330,045 3 (192-bit) UOV Rainbow Level Vc 109,063,616 405,205,796 269,012,028 5 (256-bit) UOV Sphincs SHA256-128f Simple 16,552,135 521,963,206 20,850,719 1 (128-bit) Hash-based Sphincs SHA256-192f Simple 24,355,501 687,693,467 35,097,457 3 (128-bit) Hash-based Sphincs SHA256-256f Simple 64,184,968 1,554,168,401 36,182,488 5 (128-bit) Hash-based
For stack memory size on an ARM Cortex-M4 device [1] and measured in bytes. Note, no Rainbow assessment has been performed in [1], so LUOV (an Oil-and-Vinegar method) has been used to give an indication of performance levels:
Method Key generation Sign Verify ---------------------------------------------------------------- Crystals Dilithium 2 (Lattice) 36,424 61,312 40,664 Crystals Dilithium 3 50,752 81,792 55,000 Crystals Dilithium 5 67,136 104,408 71,472 Falcon 512 (Lattice) 1,680 2,484 512 Falcon 1024 1,680 2,452 512 Rainbow Level Ia (Oil-and-Vineger) 2,969 4,720 2,732 Rainbow Level IIIa 3,216 3,224 1,440 Rainbow Level Vc 3,736 6,896 4,928 Sphincs SHA256-128f Simple 2,192 2,248 2,544 Sphincs SHA256-192f Simple 3,512 3,640 3,872 Sphincs SHA256-256f Simple 5,600 5,560 5,184
For code size on an ARM Cortex-M4 device [1] and measured in bytes. Note, no Rainbow assessment has been performed in [1], so LUOV (an Oil-and-Vinegar method) has been used to give an indication of performance levels:
Method Memory (Bytes) ------------------------------------------------- Crystals Dilithium 2 (Lattice) 13,948 Crystals Dilithium 3 13,756 Crystals Dilithium 5 13,852 Falcon 512 (Lattice) 117,271 Falcon 1024 157,207 Rainbow Level Ia (Oil-and-Vineger) 404,920 Rainbow Level IIIa 405,412 Rainbow Level Vc 405,730 Sphincs SHA256-128f Simple 4,668 Sphincs SHA256-192f Simple 4,676 Sphincs SHA256-256f Simple 5,084
Coding
The following is an implementation of Dilithium 2:
#include stddef.h #include stdint.h #include stdio.h #include "../randombytes.h" #include "../sign.h" #include stdlib.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("CRYPTO_PUBLICKEYBYTES = %d\n", CRYPTO_PUBLICKEYBYTES); printf("CRYPTO_SECRETKEYBYTES = %d\n", CRYPTO_SECRETKEYBYTES); printf("CRYPTO_BYTES = %d\n", CRYPTO_BYTES); printf("Signature Length = %d\n", smlen); printf("\nAlice Public key (only showing 1/8 of key): %s\n",showhex(pk,CRYPTO_PUBLICKEYBYTES/8)); printf("Alice Secret key (only showing 1/8 of key): %s\n",showhex(pk,CRYPTO_SECRETKEYBYTES/8)); printf("\nMessage: %s\n",showhex(m,MLEN)); printf("Signature (1/8 of actual size): %s\n",showhex(sm,smlen/8)); return 0; }
A sample run of Dilithium2 shows that the public key size is 1312 bytes, the secret key is 2,528 bytes, and the digital signature of 2,479 bytes:
CRYPTO_PUBLICKEYBYTES = 1312 CRYPTO_SECRETKEYBYTES = 2528 CRYPTO_BYTES = 2420 Signature Length = 2479 Alice Public key (only showing 1/8 of key): 5a8fdea5e771674249a509629bdcbab24f436c50fa8d7aad1245df7028e80fc8c3142f1bdd8ce659206308f8d1a3168edd18ee0cdc0b92e4269f2d7905ab65ef97f7bae772d67c889f191f1b5091570dd3f965bf656ff852e2b1d6c19309f929e456241b02e58328061960e7690e3f7a3101aa0d73a9c5ad50bd2e8341992a647f5a42731df928d88d9f82108898fbcad4b2dacb95a56b33565337dfdd9055e55ce77017 Alice Secret key (only showing 1/8 of key): 5a8fdea5e771674249a509629bdcbab24f436c50fa8d7aad1245df7028e80fc8c3142f1bdd8ce659206308f8d1a3168edd18ee0cdc0b92e4269f2d7905ab65ef97f7
The code compiles to “test_dilithium2”, and which is a Linux build. To run just run the executable:
References
[1] Kannwischer, M. J., Rijneveld, J., Schwabe, P., & Stoffelen, K. (2019). pqm4: Testing and Benchmarking NIST PQC on ARM Cortex-M4 [here].