SPHINCS+: It’s Not Lattice — and That’s a Good Thing!

And, so we end up with three new Post Quantum Cryptography signature methods: Dilithium, Falcon and SPHINCS+. While Dilithium and Falcon…

SPHINCS+: It’s Not Lattice — and That’s a Good Thing!

And, so we end up with three new Post Quantum Cryptography signature methods: Dilithium, Falcon and SPHINCS+. While Dilithium and Falcon are lattice-based methods, SPHINCS+ is a hash-based approach. While slower in performance than the lattice methods, it produces small public and private keys. Unfortunately the signature size is much larger than the lattice methods.

In the last 20 years, Daniel J Bernstein (djb) has contributed so much to cryptography and in building a more trusted world. He created research around ChaCha20, Salsa20, Curve 25519, twisted elliptic curves, AES timing attacks, and so much more. But one of his core contributions is with SPHINCS+ [here]:

So, while most hash-based methods suffer from having to remember the private keys which have signed previous messages, SPHINCS is a stateless hash-based signature scheme. It was recently accepted for standardization by NIST.

Overall SPHINCS+ 256 128-bit has a public key size of 32 bytes, a private key size of 64 bytes, and a signature of 17KB kB. It has been shown to operate at speeds of hundreds of hashes per second on a 4-core 3.5GHz processor. Other hashing methods are Haraka and SHAKE-256, for 128-bit, 192-bit and 256-bit versions.

Parameters

It uses WOTS and HORST for hash-based trees and 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 in some of the operations is BLAKE, and ChaCha is used to generate a random number.

Winternitz one time signature scheme (W-OTS)

W-OTS uses relatively small key and signatures sizes, and is thought to be quantum robust. It generates 32×256 bit random private keys. We then have these a number of times, and is defined by a parameter (w). If we use w=8, we hash the private keys by (2w). This creates 32×256 bits public keys. The signature is the created by taking eight bits at a time, and then the 8-bit binary int (n) is subtracted from 256 and the private key is the hashed 256-n times. The signature is then 32 hashes which are derived from random private keys. To verify the signature, the recipient parses the hash of the signature (using 8 bits at a time, and extracting the 8 bit int, n). The signature is then derived from the 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:

A sample run that just shows the first few private keys and the first public keys:

Hashing number:	256
==== Private key (keep secret) =====
Priv[0]:  bd344c6110628aa38c9b5ca6458bed7b78425b2e82efa0624a578031562f82ee
Priv[1]:  20670af5b1663fa9fad49fab6a692ae5989cff77439f98d2288f173b17a8d99f
Priv[2]:  625aa290fd1f88c930451ff743d5d9ef90e7064368fb23a18c9fd048474818f2
Priv[3]:  ee0e1363cbd5f61017ba27bfe91ec53969d28d143ed59a99efb020941bc4990f
Priv[4]:  ce94d7282ee3f7b05b99768695ff224b5994900c6182dfb89d596d8b7b405ec6
Priv[5]:  d0c59651e951b0bb8d5a2d7b93f6739c9ce4a0c0c0f63bfce23b331b947eb285
==== Public key (show everyone)=====
Pub[0]:  45fdac6339e80cadd1331cce026cd0364ea84146a36f6f3f2449b66fb55a217a
Pub[1]:  184cf92f22072fef078fa4a93ec2044f07ac8b12e326509474209312cace8a5a
Pub[2]:  a47548d4537bd284e7d7f935f41570866d9c6a72c463bb2a2b10c8c7907621f0
Pub[3]:  60395e575522cacb70d866211c64e8a74e562c79d1fffce224d1013d088bf66f
Pub[4]:  8be7b53d5b56e698b8798f2a707fba7b8e417554fd489d74cc40fe8574d7589e
Pub[5]:  9fac35971dae3a5c77ae7b5c720a72f90ee53852668c96c78e095cbb52af20a1
==== Message to sign ===============
Message:	The quick brown fox jumps over the lazy dog
SHA-256:	d7a8fbb307d7809469ca9abcb0082e4f8d5651e46d3cdb762d02d0bf37c9e592
==== Signature =====================
Sign[0]:	45cb53c5c33af9b20426fd0233fd63d92bf0c2ded367163e6f2f93588a33c6d8
Sign[1]:	e8c35987101f2d11d7056a2fe78069d3ed73aee315ebef8c2d40e04973301c26
Sign[2]:	59220d80b7c958957b28511f4081341cc4a00a0d6d5e1d05351be7dec3ca8aaa
Sign[3]:	72a906d719be18e1592314bf6f6c521a325a9de2b5b9e9e13117bf01b0157f5c
The signature test is  True

A demonstration of the method is given here.

Implementation

SPHINCS+ has short public and private keys, but it has a much longer signature than Dilithium and Falcon [here]:

For the same security level, SPHINCS+ has a 49KB signature compared with just 4K for Dilithium and 1KB for Falcon. The following is an implementation of SPHINCS+ [here]:

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 of SPHINCS+ 128 shows that the public key size is 36 bytes, the secret key is 68 bytes, and the digital signature is 17,088 bytes [here]:

Message: Post Quantum Crypto
Method:  haraka_128f

Public key (length): 36 bytes
Alice Public key : 0003010110775A1AD1ACD9A9451FC9292AE600ABA2532854ED0514BC4C2FD80A93A06054

Private key (length): 68 bytes
Alice Private key: 000301014E6F6DD01D91F71FD9556A635E6808250E20599EECFF60E5A86011F87E9285CC10775A1AD1ACD9A9451FC9292AE600ABA2532854ED0514BC4C2FD80A93A06054

Signature (length): 17088 bytes
Signature (first 50 bytes):  EE25C84116C3276A4FD0E43D11F29FC36465660D9A410882798197E8F9BA3303FD8E7A98C9D3542E06EC3F1DA41448C6E652

Verified: True

Conclusions

And, so, the focus is on Dilithum for a general-purpose method, but where FALCON wins on signature sizes. As Dilithium and FALCON are lattice methods, we need an alternative: SPHINCS+. Overall, SPHINCS+ has a small key pair size, but the signature is fairly large.

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)