A Signature Fit for a Post Quantum Era: Dilithium-Ed25519
A Signature Fit for a Post Quantum Era: Dilithium-Ed25519
And, so, RSA has existed for nearly five decades, and ECC (Elliptic Curve Cryptography) for over two decades. As the Diffie-Hellman key exchange is open to an Eve-in-the-Middle, we thus need a digital signature from RSA or ECC (ECDSA or EdDSA) to verify the Web site we are connecting to. Without this signature, we could not trust the connection to any site.
But, their time will be coming to an end. Why? Because Peter Shorr created a quantum computer algorithm to break them. And, so, NIST has defined Dilithium, FALCON and SPHINCS+ for the replace of RSA, ECDSA and EdDSA for signatures. But, we can’t just switch off the Internet and reboot it with Post Quantum Cryptography. For one, we will need new digital certificates, which will contain both the existing public key encryption method and the PQC method. For this, we are likely to create hybrid methods, and where we will create a digital signature for our existing public key encryption and also the PQC method. This will increase key sizes and signatures.
Luckily, NIST has been working on new standards to replace our existing public key methods, and this is typically based on lattice methods. The most likely method to be standardized in the next year or so is CRYSTALS-Dilithium. This will allow us to create a key pair in the same way we do now, and then we can sign messages with the private key, and then prove with the associated public key:
So, should your company support a traditional signature or a post-quantum one? Well, one approach is to go hybrid, and where you contain both the traditional signature and keys and the post-quantum one. While this will obviously increase the data in the signature, it will allow applications to migrate from RSA or ECDSA towards Dilithium.
The Ed25519 signature method is highly popular for new applications and uses Curve 25519 as a base. But, it is based on elliptic curve methods and thus needs to be replaced by a quantum robust method.
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.
Luckily, we have the CIRCL library and which supports hybrid methods. For ECDSA, RSA, Ed25519 and Ed448 we have key and signature sizes of:
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) RSAIt can be seen that Ed25519 has one of the smallest public and private ke sizes (each with 32 bytes), and a fairly small signature size (64 bytes). 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-)We can see that the signature size of X25519 is normally 64 bytes, but this increases to 2,484 bytes for both Dilithium2 and X25519 (and thus Dilithium2 has a signature size of 2,420 bytes. The private key rises from 32 bytes to 2,560 bytes, and the public key from 32 bytes to 1,344 bytes.
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 Ed25519-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!And here is Dilithium3-X25519 (and which gives us 192-bit equivalent security):
https://asecuritysite.com/circl/circl_dil3
Conclusions
And, so, the days of the short ECDSA signature will be gone with the advent of PQC. Bitcoin and Ethereum have benefited from their small key sizes and signatures, but we need to migrate, so consider the future … and having your crypto cake and eating it.