SPHINCS+ was one of the finalists for the NIST standard for PQC (Post Quantum Cryptography), along with NTRU (Nth degree‐truncated polynomial ring units) and CRYSTALS-DILITHIUM, and is now approved by NIST as a standard for digital signatures. It is a stateless hash-based signature scheme, which is quantum robust. It was proposed by Bernstein et al. in 2015 and updated in [2]. SPHINCS+ 256 128-bit has a public key size of 32 bytes, a private key size of 64 bytes, and a signature of 17KB. It has been shown to operate at speeds of hundreds of hashes per second on a 4-core 3.5GHz processor. In this case we will implement using SHA-256. Other hashing methods are Haraka and SHAKE-256, for 128-bit, 192-bit and 256-bit versions.
SPHINCS+ using Bouncy Castle and C# |
Details
SPHINCS+ uses WOTS and HORST for hash-based trees. The code uses a number of parameters:
- n -- length of hash in WOTS / HORST (in bits)
- m -- length of message hash (in bits)
- h -- height of the hyper-tree
- d -- layers of the hyper-tree
- w -- Winternitz parameter used for WOTS signature
- tau -- layers in the HORST tree (2^tau is no. of secret-key elements)
- k -- number of revealed secret-key elements per HORST signature
In the example we use: n=256, m=512, h=2, d=1, w=4, tau=8, k=64.
The hashing method used of some of the operations is BLAKE, and ChaCha20 is used to generate a random number.
WOTS Signature
The method is:
- Initially we create 32 256-bit random numbers. These 32 values will be our private key.
- We then hash each of these values 256 times. These 32 values will be our public key.
- We now take the message and hash it using SHA-256. This produces 32 8-bit values (N1, N2 ... N32).
- For the signature we take each 8-bit value in the hash of the message, and then hash 256-N times (where N is the value of the 8-bit value).
- To prove the signature, we take the message and hash it with SHA-256, and then take each 8-bit value. We then hash the 8-bit signature value by the number of times defined by the message hash value (N1, N2..). The result for each operation should equal the public key value.
This is illustrated below:
Presentation
Performance evaluation
The following provides an analysis of the PCQ methods for digital signing:
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) UOV Rainbow Level IIIa 861,400 611,300 164 3 (192-bit) UOV Rainbow Level Vc 1,885,400 1,375,700 204 5 (256-bit) 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 GeMSS 192 1,237,964 24 53 1 (128-bit) Multivariate RSA-2048 256 256 256 ECC 256-bit 64 32 256
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:
namespace SphincsPlus { using Org.BouncyCastle.Pqc.Crypto.SphincsPlus; using Org.BouncyCastle.Security; class Program { static void Main(string[] args) { try { var msg="Hello"; var method="haraka_128f"; if (args.Length >0) msg=args[0]; if (args.Length >1) method=args[1]; var random = new SecureRandom(); var keyGenParameters = new SphincsPlusKeyGenerationParameters(random, SphincsPlusParameters.haraka_128f); if (method=="haraka_128f_simple") keyGenParameters = new SphincsPlusKeyGenerationParameters(random, SphincsPlusParameters.haraka_128f_simple); if (method=="haraka_128s") keyGenParameters = new SphincsPlusKeyGenerationParameters(random, SphincsPlusParameters.haraka_128s); if (method=="haraka_128s_simple") keyGenParameters = new SphincsPlusKeyGenerationParameters(random, SphincsPlusParameters.haraka_128s_simple); if (method=="haraka_192f") keyGenParameters = new SphincsPlusKeyGenerationParameters(random, SphincsPlusParameters.haraka_192f); if (method=="haraka_192f_simple") keyGenParameters = new SphincsPlusKeyGenerationParameters(random, SphincsPlusParameters.haraka_192f_simple); if (method=="haraka_192s") keyGenParameters = new SphincsPlusKeyGenerationParameters(random, SphincsPlusParameters.haraka_192s); if (method=="haraka_192s_simple") keyGenParameters = new SphincsPlusKeyGenerationParameters(random, SphincsPlusParameters.haraka_192s_simple); if (method=="haraka_256f") keyGenParameters = new SphincsPlusKeyGenerationParameters(random, SphincsPlusParameters.haraka_256f); if (method=="haraka_256f_simple") keyGenParameters = new SphincsPlusKeyGenerationParameters(random, SphincsPlusParameters.haraka_256f_simple); if (method=="haraka_256f") keyGenParameters = new SphincsPlusKeyGenerationParameters(random, SphincsPlusParameters.haraka_256f); if (method=="haraka_256f_simple") keyGenParameters = new SphincsPlusKeyGenerationParameters(random, SphincsPlusParameters.haraka_256f_simple); if (method=="haraka_256s") keyGenParameters = new SphincsPlusKeyGenerationParameters(random, SphincsPlusParameters.haraka_256s); if (method=="haraka_256s_simple") keyGenParameters = new SphincsPlusKeyGenerationParameters(random, SphincsPlusParameters.haraka_256s_simple); var keyPairGen = new SphincsPlusKeyPairGenerator(); keyPairGen.Init(keyGenParameters); var keyPair = keyPairGen.GenerateKeyPair(); var pubKey = (SphincsPlusPublicKeyParameters)keyPair.Public; var privKey = (SphincsPlusPrivateKeyParameters)keyPair.Private; // Signing var aliceSign = new SphincsPlusSigner(); aliceSign.Init(true, privKey); var signature = aliceSign.GenerateSignature(System.Text.Encoding.UTF8.GetBytes(msg)); // verify signature var bobVerify = new SphincsPlusSigner(); 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 :\t{0}",Convert.ToHexString(pubKey.GetEncoded())); Console.WriteLine("\nPrivate key (length):\t{0} bytes",privKey.GetEncoded().Length); Console.WriteLine("Alice Private key:\t{0}",Convert.ToHexString(privKey.GetEncoded())); 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 128f gives:
Message: Hello Method: haraka_128f Public key (length): 36 bytes Alice Public key : 000301010522C13EB3E169E5745CE87AC2111381A9A6B76A5CDEFE7E9218423A20D11468 Private key (length): 68 bytes Alice Private key: 0003010152FCA8385F5336DAEFE59A16DF0F3F1B355EEE4C52C92EE86A20A2457D58993D0522C13EB3E169E5745CE87AC2111381A9A6B76A5CDEFE7E9218423A2 0D11468 Signature (length): 17088 bytes Signature (first 50 bytes): 96EFAC16799E43613AB047315D039717ABBB365A8E8BE18BC476470286F1FBA389DAFD6026751D95FBC52CE7240EDB8F13C4
References
[1] Kannwischer, M. J., Rijneveld, J., Schwabe, P., & Stoffelen, K. (2019). pqm4: Testing and Benchmarking NIST PQC on ARM Cortex-M4 [here].
[2] Bernstein, D. J., Hülsing, A., Kölbl, S., Niederhagen, R., Rijneveld, J., & Schwabe, P. (2019, November). The SPHINCS+ signature framework. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security (pp. 2129-2146)