Towards a Post Quantum Era: Touching Dilithium Crystals
Towards a Post Quantum Era: Touching Dilithium Crystals
And, so, like it or not, our existing public key methods are not quantum robust and can easily be cracked by quantum computers. This is the case for RSA, ECC and Discrete log methods. Luckily, NIST has defined new methods for key exchange/public key encryption (to replace ECDH and RSA) and digital signatures (RSA, ECDSA and EdDSA). These are: Dilithium, FALCON and SPHINCS+. Both Dilithium and FALCON are lattice-based methods, and SPHINCS+ is a hash-based method.
Overall, Dilithium provides good all round performance for key generation, signing and verification [here]:
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 implements 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.
Performance and key sizes
The following provides an analysis of the PCQ for key sizes. We can see that ECDSA provides a 64 byte public key (512 bits) and a 32 byte private key (256 bits). With Dilithium 2, we increase this to a 1,312 byte public key (10,496 bit), and a 2,528 byte private key (20,224 bit). The signature increases from 256 bytes (2,048 bits) to 2,421 bytes (19,360 bits):
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-)
RSA-2048 256 256 256
ECC 256-bit 64 32 256For performance on M4 (ARM Cortex-M4 dev) and measured in CPU operations per second. Note, no Rainbow assessment has been performed, 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 1,400,412 6,157,001 1,461,284 1 (128-bit) Lattice
Crystals Dilithium 3 2,282,485 9,289,499 2,228,898 3 (192-bit) Lattice
Crystals Dilithium 5 3,097,421 8,469,805 3,173,500 5 (256-bit) Lattice
Falcon 512 (Lattice) 197,793,925 38,090,446 474,052 1 (128-bit) Lattice
Falcon 1024 480,910,965 83,482,883 977,140 3 (256-bit) Lattice
Rainbow Level Ia 41,347,565 101,874,410 77,433,705 1 (128-bit) UOV
Rainbow Level IIIa 66,072,054 123,878,322 95,330,045 3 (192-bit) UOV
Rainbow Level Vc 109,063,616 405,205,796 269,012,028 5 (256-bit) UOV
Sphincs SHA256-128f Simple 16,552,135 521,963,206 20,850,719 1 (128-bit) Hash-based
Sphincs SHA256-192f Simple 24,355,501 687,693,467 35,097,457 3 (128-bit) Hash-based
Sphincs SHA256-256f Simple 64,184,968 1,554,168,401 36,182,488 5 (128-bit) Hash-basedFor 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 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 code 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,084Code
We can create a Dotnet console project for .NET 8.0 with:
dotnet new consoleFirst we install the Bouncy Castle library:
dotnet add package BouncyCastle.CryptographyNext some code [here]:
namespace Dilithium
{
using Org.BouncyCastle.Pqc.Crypto.Crystals.Dilithium;
using Org.BouncyCastle.Security;
class Program
{
static void Main(string[] args)
{
try {
var msg="Hello";
var method="Dilithium2";
if (args.Length >0) msg=args[0];
if (args.Length >1) method=args[1];
var random = new SecureRandom();
var keyGenParameters = new DilithiumKeyGenerationParameters(random, DilithiumParameters.Dilithium2);
if (method=="Dilithium3") keyGenParameters = new DilithiumKeyGenerationParameters(random, DilithiumParameters.Dilithium3);
if (method=="Dilithium5") keyGenParameters = new DilithiumKeyGenerationParameters(random, DilithiumParameters.Dilithium5);
if (method=="Dilithium2Aes") keyGenParameters = new DilithiumKeyGenerationParameters(random, DilithiumParameters.Dilithium2Aes);
if (method=="Dilithium3Aes") keyGenParameters = new DilithiumKeyGenerationParameters(random, DilithiumParameters.Dilithium3Aes);
if (method=="Dilithium5Aes") keyGenParameters = new DilithiumKeyGenerationParameters(random, DilithiumParameters.Dilithium5Aes);
var keyPairGen = new DilithiumKeyPairGenerator();
keyPairGen.Init(keyGenParameters);
var keyPair = keyPairGen.GenerateKeyPair();
var pubKey = (DilithiumPublicKeyParameters)keyPair.Public;
var privKey = (DilithiumPrivateKeyParameters)keyPair.Private;
// Signing
var aliceSign = new DilithiumSigner();
aliceSign.Init(true, privKey);
var signature = aliceSign.GenerateSignature(System.Text.Encoding.UTF8.GetBytes(msg));
// verify signature
var bobVerify = new DilithiumSigner();
bobVerify.Init(false, pubKey);
var rtn = bobVerify.VerifySignature(System.Text.Encoding.UTF8.GetBytes(msg), signature);
Console.WriteLine("Message:\t{0}",msg);
Console.WriteLine("Method:\t\t{0}",method);
Console.WriteLine("\nPublic key (length):\t{0} bytes",pubKey.GetEncoded().Length);
Console.WriteLine("Alice Public key (first 50 bytes)):\t{0}",Convert.ToHexString(pubKey.GetEncoded())[..100]);
Console.WriteLine("\nPrivate key (length):\t{0} bytes",privKey.GetEncoded().Length);
Console.WriteLine("Alice Private key (first 50 bytes)):\t{0}",Convert.ToHexString(privKey.GetEncoded())[..100]);
Console.WriteLine("\nSignature (length):\t{0} bytes",signature.Length);
Console.WriteLine("Signature (first 50 bytes):\t\t{0}",Convert.ToHexString(signature)[..100]);
Console.WriteLine("\nVerified:\t{0}",rtn);
} catch (Exception e) {
Console.WriteLine("Error: {0}",e.Message);
}
}
}
}A sample run with Dilithium5 gives [here]:
Message: Post Quantum Crypto
Method: Dilithium5
Public key (length): 2592 bytes
Alice Public key (first 50 bytes)): D7B5D80F7973C3B99440F9656A4172763DAF79B08E545B04AE34C10435590DD3FF1C6AB2F7D208BFA8E39CA4EF78997F122F
Private key (length): 4864 bytes
Alice Private key (first 50 bytes)): D7B5D80F7973C3B99440F9656A4172763DAF79B08E545B04AE34C10435590DD3D56852FA31D7176C431ED2F9E7B0EED9E51A
Signature (length): 4595 bytes
Signature (first 50 bytes): 8BD6DB2FFFAAB5EB33EC2263EB258C0172AC5CCDEF2D15B38410EF63A7B02D6B57A372E4E3380B72BC4643E278348545D03B
Verified: TrueConclusions
Like it or not, Dilithium, FALCON and SPHINCS+ look like they are the future of digital signatures, so start thinking about migration from ECDSA, EdDSA and RSA soon. You can run a demo here for Dilithium: