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 implementations 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 This page implements Dilithium 2, Dilithium 3 and Dilithium 5 using the Cloudflare CIRCL library.
Dilithium Digital Signatures using CIRCL |
Performance evaluation
For ECDSA, RSA, Ed25519 and Ed448 we have:
Method Public key size (B) Private key size (B) Signature size (B) Security level ------------------------------------------------------------------------------------------------------ Ed25519 32 32 64 1 (128-bit) EdDSA Ed448 57 57 112 3 (192-bit) EdDSA ECDSA 64 32 48 1 (128-bit) ECDSA RSA-2048 256 256 256 1 (128-bit) RSA
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-)
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 (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 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 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 outline of the code:
package main import ( "fmt" "os" "github.com/cloudflare/circl/sign/dilithium" ) func main() { modename := "Dilithium2" // Dilithium2-AES Dilithium3 Dilithium3-AES Dilithium5 Dilithium5-AES m := "Hello" argCount := len(os.Args[1:]) if argCount > 0 { modename = os.Args[1] } if argCount > 1 { m = os.Args[2] } mode := dilithium.ModeByName(modename) pk, sk, _ := mode.GenerateKey(nil) msg := []byte(m) signature := mode.Sign(sk, msg) fmt.Printf("PQC Signatures (Dilithium)\n\n") fmt.Printf("Signature method: %s \n", modename) fmt.Printf("Message: %s \n\n", msg) fmt.Printf("Private key: %x [showing first 32 bytes]\n", sk.Bytes()[:32]) fmt.Printf(" - Private key length: %d\n", len(sk.Bytes())) fmt.Printf("Public key: %x [showing first 32 bytes]\n", pk.Bytes()[:32]) fmt.Printf(" - Public key length: %d\n", len(pk.Bytes())) fmt.Printf("Signature: %x [showing first 32 bytes]\n", signature[:32]) fmt.Printf(" - Signature length: %d \n", len(signature)) if !mode.Verify(pk, msg, signature) { panic("Signature has NOT been verified!") } else { fmt.Printf("Signature has been verified!") } }
A sample run for Dilithium2 is:
PQC Signatures (Dilithium) Signature method: Dilithium2 Message: Hello Private key: a722a234ea9264d9b8586873c5e7669a6142adc81c54577c58563b8fde2513d667bb7984b2eb2e2c3bbb18e616aa2530d97759e37a6811f458ed87b764bd96f3 [showing first 64 bytes] - Private key length: 2528 Public key: a722a234ea9264d9b8586873c5e7669a6142adc81c54577c58563b8fde2513d61716dc9a2b93ed9600aeca8b33ccc06157599095305aa7ad4c9984d155a20763 [showing first 64 bytes] - Public key length: 1312 Signature: 281385e8d1ae415c0ada54435f38b1a6280cd8467d061e93b1cfd63d5d54dfa4862c05d7f9afca2950e2aefa2a845f2fcc91ecbcaca3775570d749cd763c9c07 [showing first 64 bytes] - Signature length: 2420 Signature has been verified!
A sample run for Dilithium3 is:
PQC Signatures (Dilithium) Signature method: Dilithium3 Message: Hello Private key: e07b84ae2ac3156c5029c2ce9dd434bfdf7c7c7b45582750267626520b9fc995109feebc12734f2b2e85dea6c197758db312a329a59954969fb5a09c66922f54 [showing first 64 bytes] - Private key length: 4000 Public key: e07b84ae2ac3156c5029c2ce9dd434bfdf7c7c7b45582750267626520b9fc995b4602c5cc3c6b4f834e9b9d4652af6cfd97dab6e9f8860564ed956767f1329f7 [showing first 64 bytes] - Public key length: 1952 Signature: 2cc62f30f8381171ec913b7aafd1684f4aba3a698e7f32f0ff8a55939c06ca31babb3dda98b4ad0ce1faefe595846526c10ea171f33e942d880bacfb8d920a83 [showing first 64 bytes] - Signature length: 3293 Signature has been verified!
A sample run for Dilithium5:
PQC Signatures (Dilithium) Signature method: Dilithium5 Message: Hello Private key: 1b496280e2e45502bb361f696b32c68eb11c58359245a945eee6b44c2786fbeac1459818212f5ad31c128553ce063f32467204b88625b131686695a47428278b [showing first 64 bytes] - Private key length: 4864 Public key: 1b496280e2e45502bb361f696b32c68eb11c58359245a945eee6b44c2786fbea4dac7554729b4030cbf8f5f63aae25fc29320ca533d7cf0b7d6f88e78dc213ff [showing first 64 bytes] - Public key length: 2592 Signature: 5435ab9d2d35ec77133dc0cf660d8a710f14065829b26c15db5f7295055e4e40e1d2276b972c9ae18d85cd08582d26c97c135f912b85fda3f8d5f15ec8787c78 [showing first 64 bytes] - Signature length: 4595 Signature has been verified!