Crypto Bake-Off — The FINAL! — And It’s a Lattice Bake in The Lead

Crypto Bake-Off — The FINAL! — And It’s a Lattice Bake in The Lead

As if you didn’t know, quantum computers will put an end to our most popular public-key methods. And so NIST has been working on defining a standard for the best method to replace these, and yesterday they made their announcement on the final of the PQC (Post Quantum Cryptography) standardization process. For Public-Key Encryption and KEMs (Key Exchange) we have:

• Classic McEliece. This has been around for around 40 years, and has been shown to be fairly resistant to attack. It produces a fairly long encryption key, but produces a fairly small amount of ciphertext.
• CRYSTALS-KYBER (Lattice). Uses LWE (Learning with Errors) with lattice methods. A new lattice attack was discovered within the period of the assessment [1], but it is hoped that an updated version of KYBER can be produced for the final assessment. NIST have some worried about its side-channel robustness, and is a strong contender for KEM.
• NTRU (Lattice). This is a traditional structured lattice based approach, and has been around for longer than the other lattice methods — showing that it is perhaps more robust against attack and against intellitecual property claims.
• SABER (Lattice). This is based on modular learning with rounding, and uses lattice methods. SABER has excellent performance, and is possibly near production ready. NIST’s only recommendation is that updates should perhaps consider side-channel attacks.

and for digital signatures:

• CRYSTALS-DILITHIUM (Lattice).
• FALCON (Lattice).
• Rainbow (Oil and Vinegar).

These are defined as the finalists, and a winner will be chosen from these, but because CRYSTALS-KYBER, NTRU, and SABER are lattice methods, NIST only wants one winner from a lattice technique. So it has drawn up a list for an alternative of: BIKE; FrodoKEM; HQC; NTRU Prime; and SIKE. And CRYSTALS-DILITHIUM and FALCON are lattice methods for digital signatures, so the alterative list has: GeMSS; Picnic; and SPHINCS+. NIST thus wants to guard against lattice methods being cracked in the future, and thus would like an alternative method as a back-up. The report is [here]:

For many in PCQ, the seven candidates will allow a move towards their integrates into systems, and which may result in them becoming a standard before the winner is announced.

SIKE is highlighted in the NIST assessment, as it is the only one which uses iosgenies, and which results in a small key size and small cipher text. It thus has a good chance to be named as one of the alteratives to the winner:

The final assessment will start in October 2020 and is expected to last up to 18 months, with a possible announcement the 3rd NIST PQC Standardization Conference in 2021. So here are some of the finalists:

Classic McEliece

Another serious contender dates back to 1978. In a lesson for any modern researcher, in just two pages, Robert McEliece outlined a public key encryption method based on Algebraic Coding — now known as the McEliece Cryptography method [paper]. It is an asymmetric encryption method (with a public key and a private key), and, at the time, looked to be a serious contender for a trapdoor method. Unfortunately, RSA became the King of the Hill, and the McEliece method was pushed to the end of the queue for designers.

It has basically drifted for nearly 40 years. But, as an era of quantum computers is dawning, it is now being reconsidered, as it is seen to be immune to attacks using Shor’s algorithm [here].

The McEliece method uses code-based cryptography. Its foundation is based on the difficulty in decoding a general linear code and is generally faster than RSA for encryption and decryption. Within it, we have a probabilistic key generation method, which is then used to produce the public and the private key. The keys are generated with the parameters of n, k and T.

The keys are generated with the parameters of n, k and t. With this, we created an [n,k] matrix of codes, and which is able to correct t errors. In his paper, McEliece defines defines n=1024, k=524, t=50, and which gives a public key size of 524x(1024–524) = 262,000 bits. In the example above we use k=1608, N=2048 and T=40, which gives a public key size of 1608x(2048–40) — 3,228,864 bits. For quantum robustness it is recommended that N is 6960, k is 5,412 and t is 119 (giving a large key size of 8,373,911 bits.

Here is a demo of the encryption [here] and provides a simple explanation of how the key is created for McEliece crypto. It uses a (7,4) Hamming code with one-bit error correction. The following is an outline [here]:

This is based on the example [here]. We illustrate the process with a (7,4) Hamming code which corrects one error. The generator matrix is then:

    1  0  0  0  1  1  0
G = 0  1  0  0  1  0  1
    0  0  1  0  0  1  1
    0  0  0  1  1  1  1

Bob then selects a scrambler matrix (S):

    1  1  0  1
S = 1  0  0  1
    0  1  1  1
    1  1  0  0

And also a permutation matrix:

              0  1  0  0  0  0  0 
              0  0  0  1  0  0  0
              0  0  0  0  0  0  1
         P =  1  0  0  0  0  0  0
              0  0  1  0  0  0  0
              0  0  0  0  0  1  0
              0  0  0  0  1  0  0

Bob public key then becomes the dot product of these matrices

                  1  1  1  1  0  0  0
     G' = SGP   = 1  1  0  0  1  0  0
                  1  0  0  1  1  0  1
                  0  1  0  1  1  1  0

Bob will use G’ as a public key, but S, G and P are secret. Next, for Alice to send a ciphered message to Bob, she converts the message into binary vectors of length k.

For a message of m Alice will create randomly a binary n-vector of weight t, and randomly places t 1’s in a zero vector of length n).

This is then sent to Bob:

y = mG’ + e

Bob then decrypts with:

yP−1=(mG′+e)P−1=mSG+eP−1=mSG+e′

A sample run is:

Message: [ 1.  1.  0.  1.]
G:
[[1 0 0 0 1 1 0]
 [0 1 0 0 1 0 1]
 [0 0 1 0 0 1 1]
 [0 0 0 1 1 1 1]]
S:
[[1 1 0 1]
 [1 0 0 1]
 [0 1 1 1]
 [1 1 0 0]]
P:
[[0 1 0 0 0 0 0]
 [0 0 0 1 0 0 0]
 [0 0 0 0 0 0 1]
 [1 0 0 0 0 0 0]
 [0 0 1 0 0 0 0]
 [0 0 0 0 0 1 0]
 [0 0 0 0 1 0 0]]
Result:
[[1 1 1 1 0 0 0]
 [1 1 0 0 1 0 0]
 [1 0 0 1 1 0 1]
 [0 1 0 1 1 1 0]]Cipher: [ 0.  1.  1.  0.  1.  1.  0.]P^{-1}:
[[ 0.  0.  0.  1.  0.  0.  0.]
 [ 1.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  1.  0.  0.]
 [ 0.  1.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  1.]
 [ 0.  0.  0.  0.  0.  1.  0.]
 [ 0.  0.  1.  0.  0.  0.  0.]]y': [ 1.  0.  0.  0.  1.  1.  1.]S^{-1}:
[[ 1.  1.  0.  1.]
 [ 1.  1.  0.  0.]
 [-0.  1.  1.  1.]
 [ 1.  0.  0.  1.]]Decipher: [ 1.  1.  0.  1.]

NTRU

The NTRU (Nth degree TRUncated polynomial ring) public key method is a lattice-based method which is quantum robust. It uses the shortest vector problem in a lattice and has an underpinning related to the difficulty of factorizing certain polynomials. This article outlines the method used to generate the public key (h).

With Lattice encryption, Bob and Alice agree to share N, p and q, and then Bob generates two short polynomials (f and g) and generates his key pair from this. Alice receives this, and she generates a random polynomial and encrypts some data for Bob. Bob then decrypts the message with his private key. We generate the public and private key from N, p and q:

==== Bob generates public key =====
Values used:
 N= 11
 p= 3
 q= 32
========Bob picks two polynomials (g and f):
f(x)=  [-1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1]
g(x)=  [-1, 0, 1, 1, 0, 1, 0, 0, -1, 0, -1]====Now we determine F_p and F_q ===
F_p: [1, 2, 0, 2, 2, 1, 0, 2, 1, 2, 0]
F_q: [5, 9, 6, 16, 4, 15, 16, 22, 20, 18, 30]====And finally h====
f_q x g:  [-5, -9, -1, -2, 11, 12, 13, 3, 22, 15, 16, 29, 60, 19, -2, -7, -36, -40, -50, -18, -30]
H (Bob's Public Key):  [24, 19, 18, 28, 4, 8, 5, 17, 4, 17, 16]====Let's encrypt====
Alice's Message:	[1, 0, 1, 0, 1, 1, 1]
Random:			[-1, -1, 1, 1]
Encrypted message:	[8, 2, 10, 23, 16, 7, 26, 2, 8, 3, 28]====Let's decrypt====
Decrypted message:	[1, 0, 1, 0, 1, 1, 1]

NTRU is asymmetric encryption and has been benchmarked as twice as fast as RSA to encrypt, and three times faster to decrypt. NTRU was the public key method which is not based on factorization (RSA) or discrete logs (Elliptic Curve).

The following is taken from Wikipedia and shows the test case [here]:

I have created a demonstrator here. An outline of the code [here]:

Rainbow — Oil and Vinegar (UOV)

The Rainbow method uses the Unbalanced Oil and Vinegar (UOV) scheme for a quantum robust cryptography method with asymmetric encryption. To explain its method, let’s take a simple example:

“Okay”, your teacher says, solve “x² + 2 x = 8”, and you quickly say, “I think that x is equal to 2”.

Now the teacher says, “Solve: 2x + y = 1 and 3x + y = 7”,

And you quickly do a calculation and put up your hand … “I think x is 2 and y is 1”. “Well done”, says the teacher, “And now solve…

5 x+ 4y + 10 w + 9 z = 99
6 x + 3 y + 2 w + 3 z =38
8 x + 2 y + 7 w + z = 51
 x + 9 y + 4 w + 6 z =57"

[The answer is below]

Things now get a bit difficult for you, as this is an NP-hard mathematical problem, where we would require significant computing power to solve large equations with many variables.

If we just have one variable, we can use the least mean squares method to compute the values. For example, if we have:

x² + 2 x — 8 = 0

Then we can write a small Python program to solve this (8 = x² + 2x):

import numpy as npcoeff = [1,2,-8]
z = np.roots(coeff)
print z

The answer is [-4,2]. So trying -4 and 2 into this equation will solve it.

The multivariate polynomial problem is now being applied in quantum robust cryptography, where we create a trap door to allow us to quickly solve the n variables with m equations (which are multivariate polynomials).

One scheme that can be used is the Unbalanced Oil and Vinegar scheme and was created by J. Patarin. A signature is created with a number of equations:

y1 = f(x1, x2 … xn)
y2 = f(x1,x2 … xn)
…
ym= f(x1,x2 … xn)

where y1, y2, … ym is the message that is to be signed, and where x1, x2 … xn is the signature for the message.

So a simple example:

5 x+ 4y + 10 w + 9 z = 99
6 x + 3 y + 2 w + 3 z =38
8 x + 2 y + 7 w + z = 51
 x + 9 y + 4 w + 6 z =57

The message is 99, 38, 51 and 57, and the signature is then 5, 4, 10 … 6.

A demonstrator of Oil and Vinegar is given here. The following provides an outline of the code, where we sign “Hello” with the private key and verify with the public key:

package rain;import java.math.BigInteger;
import java.security.SecureRandom;import org.bouncycastle.crypto.AsymmetricCipherKeyPair;
import org.bouncycastle.crypto.digests.SHA224Digest;
import org.bouncycastle.crypto.params.ParametersWithRandom;
import org.bouncycastle.pqc.crypto.DigestingMessageSigner;
import org.bouncycastle.pqc.crypto.rainbow.RainbowKeyGenerationParameters;
import org.bouncycastle.pqc.crypto.rainbow.RainbowKeyPairGenerator;
import org.bouncycastle.pqc.crypto.rainbow.RainbowParameters;
import org.bouncycastle.pqc.crypto.rainbow.RainbowSigner;public class rain {
	
	public static void main(String args[]){SecureRandom    keyRandom = new SecureRandom();
		
	RainbowParameters params = new RainbowParameters();RainbowKeyPairGenerator rainbowKeyGen = new RainbowKeyPairGenerator();
	RainbowKeyGenerationParameters genParam = new RainbowKeyGenerationParameters(keyRandom, params);rainbowKeyGen.init(genParam);AsymmetricCipherKeyPair pair = rainbowKeyGen.generateKeyPair();
	        
	org.bouncycastle.pqc.crypto.rainbow.RainbowPrivateKeyParameters priv = (org.bouncycastle.pqc.crypto.rainbow.RainbowPrivateKeyParameters) pair.getPrivate();
	org.bouncycastle.pqc.crypto.rainbow.RainbowPublicKeyParameters pub = (org.bouncycastle.pqc.crypto.rainbow.RainbowPublicKeyParameters) pair.getPublic();
		      
	System.out.println("Random:"+new BigInteger(130, keyRandom).toString(32));
	System.out.println("\n----Private Key----");System.out.println("Doc length:"+priv.getDocLength());
	System.out.println("B1:");
	showints(priv.getB1());
	
	System.out.println("B2:");
	showints(priv.getB2());
	
	System.out.println("InvA1:");
	showints(priv.getInvA1());
	
	System.out.println("InvA1:");
	showints(priv.getInvA2());
	
	System.out.println("Vi:");	 
	showints(priv.getVi());
	
	System.out.println("\n----Public Key----");
	System.out.println("Doc length:"+pub.getDocLength());
	System.out.println("Coeff Quadratic:");
	showints(pub.getCoeffQuadratic());
	System.out.println("Coeff Scalar:");
	showints(pub.getCoeffScalar());
	System.out.println("Coeff Singlar:");
	showints(pub.getCoeffSingular());     
	ParametersWithRandom param = new ParametersWithRandom(pair.getPrivate(), keyRandom);DigestingMessageSigner rainbowSigner = new DigestingMessageSigner(new RainbowSigner() , new SHA224Digest());
	rainbowSigner.init(true, param);System.out.println("\n----Message and signing----");
	String ex="hello";
	if (args.length>1) ex = args[0];
	
	byte[] message = ex.getBytes();
	System.out.println("Message:"+ex);rainbowSigner.update(message, 0, message.length);
	byte[] sig = rainbowSigner.generateSignature();System.out.println("Signature:"+getHexString(sig));
	
	rainbowSigner.init(false, pair.getPublic());
	rainbowSigner.update(message, 0, message.length);
	        
	if (!rainbowSigner.verifySignature(sig))
	{
		System.out.println("Failure in signature");
	}
	else 
		System.out.println("Success in signature");		
	 }
	
	public static String getHexString(byte[] b) {
		  String result = "";
		  for (int i=0; i < b.length; i++) {
		    result +=
		          Integer.toString( ( b[i] & 0xff ) + 0x100, 16).substring( 1 );
		  }
		  return result;
		}
	public static void showints(short [][] grid)
	{
        System.out.println("Dimension: [" + grid.length+"]["+grid[0].length+"] (Only displaying first few)");
	    int count=0;
        for(int r=0; r<grid.length; r++) {for(int c=0; c<grid[r].length; c++)
	        {
	            System.out.print(grid[r][c] + " ");
		    	count++; if (count>15) return;
	        }
	        System.out.println();
	     }
	}
	public static void showints(short [] grid)
	{
	    for(int r=0; r<grid.length; r++) {
	            System.out.print(grid[r] + " ");}
        System.out.println();
	}
	public static void showints(int [] grid)
	{
	    for(int r=0; r<grid.length; r++) {
	            System.out.print(grid[r] + " ");}
        System.out.println();
	}
}

The variables used include:

• Doc — Number of polynomials in Rainbow.
• Vi — Number of Vinegar-variables per layer ({6, 12, 17, 22, 33})
• B1 — Translation part of the private quadratic map L1.
• InvA1 — Inverse matrix of A1.
• B2 — Translation part of the private quadratic map L2.
• InvA2 — Inverse matrix of A2.

Oil and Vinegar is a method which is difficult to solve if we do not have the required secret information. Unfortunately, the methods used in discrete logarithms and prime number factorization are a major target for quantum computers, so we perhaps need to look to problems which will still be hard when quantum computers go live.

Ans: x=2, y= 1, w= 4, z= 5

SPHINCS

For digital signatures, SPHINCS is a stateless hash-based signature scheme, and is quantum robust. It was proposed by Bernstein et al. in 2015 [paper]. SPHINCS+ 256 has a public key size of 1kB, a private key size of 1kB, and a signature of 41 kB. It has been shown to operate at speeds of hundreds of hashes per second on a 4-core 3.5GHz processor.

It 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 Cha-cha is used to generate a random number.

A demonstration of this method is given here.

Conclusions

And so, it looks like lattice methods will be replacing elliptic curve and RSA public key methods. We need to start looking at this soon, as we need a good migration strategy. If you are interested, here is an outline of LWE (Learning With Errors) and Lattice methods:

References

[1] Ravi, P., Roy, D. B., Bhasin, S., Chattopadhyay, A., & Mukhopadhyay, D. (2019, April). Number “not used” once-practical fault attack on pqm4 implementations of NIST candidates. In International Workshop on Constructive Side-Channel Analysis and Secure Design (pp. 232–250). Springer, Cham.