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                256

For 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-based

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                           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 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,084

Code

We can create a Dotnet console project for .NET 8.0 with:

dotnet new console

First we install the Bouncy Castle library:

dotnet add package BouncyCastle.Cryptography

Next 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: True

Conclusions

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:

https://asecuritysite.com/csharp/bc_dil