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 Ed448 and Dilithium, we can implement a hybrid signature scheme, and where the signature contains both the Ed448 and Dilithium3 keys and signatures.
Ed448-Dilithium3 (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/eddilithium3" ) func main() { m := "Hello" argCount := len(os.Args[1:]) if argCount > 0 { m = os.Args[1] } pk, sk, _ :=eddilithium3.GenerateKey(nil) msg := []byte(m) var signature [eddilithium3.SignatureSize]byte eddilithium3.SignTo(sk, msg,signature[:]) fmt.Printf("PQC Signatures (Ed25519-Dilithium3)\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 !eddilithium3.Verify(pk, msg, signature[:]) { panic("Signature has NOT been verified!") } else { fmt.Printf("Signature has been verified!") } }
A sample run for Ed448-Dilithium3 is:
PQC Signatures (Ed448-Dilithium3) Message: Hello Private key: 4ce7c648c52a159b63af582de6cfc5bcb2187a496afde418019f43dca8c5566904175290b18f01f97c600e5f6b64ed75f6019eed2ef29a26836f96685c7484a8 [showing first 64 bytes] - Private key length: 4057 Public key: 4ce7c648c52a159b63af582de6cfc5bcb2187a496afde418019f43dca8c5566962966a132aa477090345cc9b9ec77d706be491fe143a1edbef12ea2b81bd425d [showing first 64 bytes] - Public key length: 2009 Signature: 828a7d998acb79896b8cc3567aa1a7c2e8abc92b5467814eb2d534ca408907f1386c04d9cd89fc2a00098b0bf5343b59b27cbb84fda9a4bdb729e797b3fcf475 [showing first 64 bytes] - Signature length: 3407 Signature has been verified!
We can then see that we have a 4,057 byte private key, a 2,009 byte public key and a 3407 byte signature length. With Dilithium3 on its own, these would be 4,000 bytes, 1,952 bytes, and 3,293 bytes. In this case we use Curve 448 (the Goldilocks curve), and which is a more secure curve than Curve 25519. The sizes are then:We can then see that we have a 4,057 byte private key, a 2,009 byte public key and a 3,407 byte signature length. With Dilithium3 on its own, these would be 4,000 bytes, 1,952 bytes, and 3,293 bytes. In this case we use Curve 448 (the Goldilocks curve), and which is a more secure curve than Curve 25519. The sizes are then:
Private key: 4,057= 4,000 (Dilithium2) + 57 (Ed448) Private key: 2,009 = 1,952 (Dilitihum2) + 57 (Ed448) Signatures: 3,407= 3,293 (Dilithium2) + 114 (Ed448)