Going Hybrid: Making the Quantum Jump In Digital Signatures, Easier
Meet Dilithum2+Ed25519 and Dilithium3+Ed443
Digital signatures are fundamentally important in digital trust. With this, if Bob wants to prove his identity to Alice, he signs a hash of a message with his private key, and she checks this with his public key:
At present, we typically use RSA, ECDSA, or EdDSA (Ed25519) for signatures, but these are not quantum robust, and can be easily broken by quantum computers.
Going hybrid
So, should we just drop public key signatures? Well, we can use hybrid methods while we move towards fully quantum robust techniques. The currently defined NIST standards are Dilithium, Falcon and SPHINCS+. Both Dilithium and Falcon are lattice-based methods, while SPHINCS+ is the hash-based approach.
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.
Dilithium and Ed25519
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.
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) RSAThe 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
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-basedFor 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,184For 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
Sphincs SHA256-128f Simple 4,668
Sphincs SHA256-192f Simple 4,676
Sphincs SHA256-256f Simple 5,084Dilithium2 + Ed25519 Coding
The following is an outline of the code [here]:
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 [here]:
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)
We can thus see that we considerable add to the size of the signature compred with the Ed25519, and will need two data packets to transfer the signature from Alice to Bob:
Dilithium3 + Ed25519
The following is an outline of the code [here]:
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 Dilithium3 is [here]:
PQC Signatures (Ed443-Dilithium3)
Message: Hello
Private key: 2607090338c71a9a37ebff62164b8ebfc9d8914af3dc5c1ccebb607544b3a4b310d2f43cbe629bd52e2dc53df7593d1c892dbe62314eb8b88ba8b798adb51d15 [showing first 64 bytes]
- Private key length: 4057
Public key: 2607090338c71a9a37ebff62164b8ebfc9d8914af3dc5c1ccebb607544b3a4b3887868e1f55836cf9028aa58471b035246caf959674ddcde97f786e067555807 [showing first 64 bytes]
- Public key length: 2009
Signature: eca9281a3084b225391dac1b44a9fd58670b3b12028c82dbcb571a87e2308070cc65e581452703cf47801e270b6e9d2d57f3a29b8318e5e9f2c1776208511364 [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:
Private key: 4,057= 4000 (Dilithium2) + 57 (Ed443)
Private key: 2,009 = 1,952 (Dilitihum2) + 57 (Ed443)
Signatures: 3407= 3,293 (Dilithium2) + 114 (Ed443)
Conclusions
At present, we check the identity of a Web site through the use of RSA or ECC digital signatures. If these signatures were broken, we could not trust any Web site. An alternative is to thus use hybrid signatures, and which would support both ECC and Dilithium methods. This will allow us to migrate towards a fully post quantum robust world.
