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 2 is equivalent to a 128-bit signature, and is perhaps the starting point for an implementation. To support both Ed25519 and Dilithium, we can implement a hybrid signature scheme, and where the signature contains both the Ed25519 and Dilithium2 keys and signatures.
Ed25519-Dilithium2 (hybrid signature scheme) 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 Dilithium2-Ed25519 1,344 2,560 2,484 1 (128-bit) Lattice Crystals Dilithium3-Ed25519 2,009 4,057 3,407 3 (192-bit) Lattice 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/eddilithium2" ) func main() { m := "Hello" argCount := len(os.Args[1:]) if argCount > 0 { m = os.Args[1] } pk, sk, _ :=eddilithium2.GenerateKey(nil) msg := []byte(m) var signature [eddilithium2.SignatureSize]byte eddilithium2.SignTo(sk, msg,signature[:]) fmt.Printf("PQC Signatures (Ed25519-Dilithium2)\n\n") fmt.Printf("Message: %s \n\n", msg) fmt.Printf("Private key: %x [showing first 64 bytes]\n", sk.Bytes()[:64]) fmt.Printf(" - Private key length: %d\n", len(sk.Bytes())) fmt.Printf("Public key: %x [showing first 64 bytes]\n", pk.Bytes()[:64]) fmt.Printf(" - Public key length: %d\n", len(pk.Bytes())) fmt.Printf("Signature: %x [showing first 64 bytes]\n", signature[:64]) fmt.Printf(" - Signature length: %d \n", len(signature)) if !eddilithium2.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 (Ed25519-Dilithium2) Message: Hello Private key: daa45043f2a791d980ada155688addc4663d6213f37483df02118edaace5ffc5f86fb44e0caea401646ab1b0ca663abc145a02a54121eed835eabb18b8fe7014 [showing first 64 bytes] - Private key length: 2560 Public key: daa45043f2a791d980ada155688addc4663d6213f37483df02118edaace5ffc53d1c1b16bc78f4ffe014c74920296913b4b57da2ccae0699de644e349aeec1af [showing first 64 bytes] - Public key length: 1344 Signature: 1b87ef67f34b472e811da6de8064605e833ca6c68007c1846b36f7bd4c6c231ff55b49c0a7b3a7f63e96c171b6ef4095c1e6e80c2eab53bee4ac9309acc7739f [showing first 64 bytes] - Signature length: 2484 Signature has been verified!
We can then see that we have a 2,560 byte private key, a 1,344 byte public key and a 2,484 byte signature length. With Dilithium2 on its own, these would be 2,528 bytes, 1,312 bytes and 2,420 bytes. Thus we have:
Private key: 2560 = 2528 (Dilithium2) + 32 (Ed25519) Private key: 1344 = 1312 (Dilitihum2) + 32 (Ed25519) Signatures: 2484 = 2420 (Dilithium2) + 64 (Ed25519)