Meet New PQC Signature Contenders

Meet New PQC Signature Contenders

And Multivariate (aka Oil and Vinegar Methods) To The Fore

Digital signatures are the foundation of our digital trust. With this, Bob has a key pair: a private key and a public key. In order to provide his identity, he signs a hash of a message with his private key, and then Alice proves this with his public key. Currently, we mainly use RSA, ECDSA and EdDSA for our signature methods, and where DSA signatures (which use discrete logs) have been dropped for their creation. For example, ECDSA is used with Bitcoin and Ethereum, and RSA is often used to identify Web sites. EdDSA is now on the rise, and is part of the FIPS-186–5 standard. Unforunately, we will need to replace these methods — as quantum computers can crack them.

The other area that needs to be replaced is key exchange and public key encryption. These days we typically use ECDH (Elliptic Curve Diffie Hellman) for key exchange, and RSA for public key encryption. These will have to be replaced with quantum-robust methods — Post Quantum Cryptography (PQC).

Goodbye RSA and ECC, and Hello to PQC

And, so, using Shor’s algorithm, quantum computers will be able to crack RSA, discrete logs and ECC (Elliptic Curve Cryptography), and so we need to remove RSA, ECDSA and EdDSA and replace them with methods that are quantum robust.

For this, NIST has been running a competition for the last few years, and where CRYSTALS-Dilithium and SPHINCS+ were selected as the winners for PQC digital signatures. There are no other candidates that are being assessed from the previous round. Overall, Dilithium is a lattice-based method, while SPHINCS+ uses a hash-based signature method. But what if these methods are cracked? Well, it happened to two of the finalists for the NIST competition: Rainbow and SIKE, and where the methods were cracked in the final round of the competition.

For KEM (Key Exchange Mechanisms) to replace ECDH (Elliptic Curve Diffie Hellman) and Public Key Encryption (PKE) to replace RSA, NIST has standardized CRYSTALS-Kyber, and is still assessing BIKE, Classic McEliece, HQC, and SIKE.

Additional Signatures: Round 1

And, so, NIST is on the look-out for alternatives for Dilithium and has set up a new competition [here]:

In the first round, we have:

• Code-based Signatures: CROSS (Codes and Restricted Objects Signature Scheme); Enhanced pqsigRM; FuLeeca; LESS (Linear Equivalence Signature Scheme) and MEDS (Matrix Equivalence Digital Signature Wave).
• Isogenies: SQIsign.
• Lattice based: EagleSign; EHTv3 and EHTv4; HAETAE; HAWK; HuFu (Hash-and-Sign Signatures From Powerful Gadgets); Raccoon; and SQUIRRELS (Square Unstructured Integer Euclidean Lattice Signature).
• MPC in the head: MIRA; MiRitH (MinRank in the Head); MQOM (MQ on my Mind); PERK; RYDE; and SDitH (Syndrome Decoding in the Head).
• Multivariate Signatures (Oil and Vinegar): 3WISE; Biscuit; DME-Sign; HPPC (Hidden Product of Polynomial Composition); MAYO; PROV (PRovable unbalanced Oil and Vinegar); QR-UOV; SNOVA; TUOV (Triangular Unbalanced Oil and Vinegar); UOV (Unbalanced Oil and Vinegar); and VOX.
• Symmetric-based Signatures: AIMer; Ascon-Sign; FAEST; and SPHINCS-alpha.

Doing a quick count, we have:

Multivariate: 11; Lattice: 7; Code-based: 5; MPC-in-the-head: 5; Symmetric-based: 4; and Isogenies: 1.

So, multivariate seems to be leading the way, with lattice methods being popular too. But poor old isogenies only has one contender. This may be due to the crack on an isogeny-based method (Supersingular Isogeny Key Encapsulation SIKE), or that isogenies are better suited to key exchange techniques.

And so, let’s look at the basic methods and some previous examples.

Multivariate — Unbalanced Oil and Vinegar (UOV)

With multivariate cryptography, we have n variables within polynomial equations. For example, if we have four variables (w,x,y,z) and an order of two, we could have [here]:

w²+4wx+3x²+2wy−4wz+2wx+6xz=387

Generally, this is a hard problem to solve, so we want to make it easy if we know a secret. In this case, I know that the solution is w=7,x=4,y=5, and z=6.

Lattice

To understand lattice cryptography, you need to understand polynomials, as our bit values are converted into polynomials. Our operations are then conducted with polynomial multiplies and addition, and taken with a (mod p) operation (and where p will be the maximum value we generate for the polynomial values).

Code-based

This method was created in 1978 with the McEliece cryptosystem but has barely been used in real applications. The McEliece method uses linear codes that are used in error-correcting codes and involves matrix-vector multiplication. An example of a linear code is Hamming code [here].

MPC-in-the-head

These methods use non-interactive zero-knowledge proofs of knowledge and MPC (Multiparty Computation). With MPC we can split a problem into a number of computing elements, and these can be worked on in order to produce the result, and where none of the elements can see the working out at intermediate stages. The great advantage of this method is that we only use symmetric key methods (block ciphers and hashing functions).

Symmetric

These methods uses standard cryptographic methods such as symmetric key encryption and hashes. Typically they use AES and SHA3 — and which are quantum robust.

Isogenies

If we have two elliptic curves (E1 and E2), we can create a function that maps a point (P) on E1 to a point Q on E2. This function is known as an isogeny. If we can map this function, every point on E1 can be mapped to E2. Our secret key is then the isogeny and the public key is the elliptic curve. For key exchange, Bob and Alice mix their isogeny and the other side’s curve to generate a secret curve.

Conclusions

Exciting times are ahead as the methods go up and against each. In the last competition, some of the methods fell because of a problem with their parameters (Rainbow — UOV) or because of a core weakness (isogenies). But, this time, they are all likely to come back strong and (hopefully) compete well against the lattice methods.

If you are interested, I will be presenting on PQC methods and their effect on FinTech on 6 October 2023 here:

and here’s a background to PQC:

https://asecuritysite.com/pqc/