In a Post Quantum Computing World: For Robust Cooking — You Need a Bit of Oil and Vinegar

In a Post Quantum Computing World: For Robust Cooking — You Need a Bit of Oil and Vinegar

I’m going to try and explain the Unbalanced Oil and Vinegar (UOV) scheme for a quantum robust cryptography method with asymmetric encryption (and where we create a public key and a private key). It is defined as a multivariate polynomial method. So let’s start nice and simple …

“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 np

coeff = [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.

A trap door

The RSA encryption method uses the multiplication of two prime numbers to create a public modulus (N). Unfortunately the factorization of N is fairly easy if we use a quantum computer. Thus NIST are now looking for contenders for the replacement of RSA, and other methods such as El Gamal, for a quantum computer age.

Currently we often use symmetric encryption (such as AES) for the main encryption, and then use asymmetric encryption (such as RSA) to protect the symmetric key and/or to prove identity. Often we use RSA to sign an identity, such as using the private key to sign, and then the associated public key to validate the signature.

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. On the most well-defined methods is Rainbow, and which is on NIST’s short-list for quantum-robust signature methods (for multivariate polynomials):

And Rainbow has rearched the final route:

Code

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.

Conclusions

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.

Answer

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