Oil and Vinegar Makes A Hard Problem Easy

Fixing The Hole In The Internet in a Post Quantum World
Photo by Lucas van Oort on Unsplash

Oil and Vinegar Makes A Hard Problem Easy

Fixing The Hole In The Internet in a Post Quantum World

Okay. This isn’t going to be an easy read, but it reveals an amazing method, and that could help fix our security in a world of quantum computers. The method involves taking a hard problem to solve, and then applying a trap door. If we know a little secret, the hard problem becomes easy.

Overall, quantum computers will be able to break our existing public key methods, such as discrete logs, RSA and elliptic curves. And so NIST has created a Post Quantum Cryptography competition, and one of the methods is known as Rainbow. This is known as the Oil and Vinegar method and uses multivariate cryptography with an added trapdoor. Unfortunately, Rainbow was cracked before the NIST announcement of the methods that it wants to be standardized, and how now been dropped from the competition. But the Oil and Vinegar method is still a strong method, so let’s take a simple example, and work through how the trapdoor works.

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. For a matrix form, we could represent this as:

This matrix has a trapdoor, and where we define our vinegar and oil variables. The vinegar variables are secret and which we will only know, and the oil ones will be discovered if we know the vinegar variables. The trap door is that we do not let the oil variables mix, and where they do mix in the matrix we will have zeros (the trap door):

In order to contain the values we get, we normally perform (mod p) operation and where p is a prime number. This is known as a finite field, and are numbers are always constrained between 0 and p−1. For example, if we select p=97 we have:

w²+4wx+3x²+2wy−4wz+2wx+6xz=5 (mod 97)

Now there are multiple solutions to this now for w,x,y,z, so we define n multivariate polynomials. For example:

w²+4wx+3x²+2wy−4xz+2wx+6xy=96 (mod 97)

5w²+3wx+3x²+4wy−xz+8wx+4xy=36 (mod 97)

4w²+5wx+3x²+2wy−5xz+3wx+6xy=95 (mod 97)

6w²+7wx+4x²+2wy−8xz+2wx+9xy=17 (mod 97)

With large values of the variables, this is a known hard problem to solve. So now we define our vinegar variables of w and x and oil variables of y and z. If we know w and x it will now become easy to determine oil variables. For example, if w=7 and x=4, we get:

49+112+48+14y−16z+14z+24y=96 (mod 97)

245+84+48+28y−4z+56z+16y=36 (mod 97)

and gives:

209+38y−2z=96 (mod 97)

377+44y+52z=36 (mod 97)

and gives:

38y+95z=−113 (mod 97)

44y+52z=−341 (mod 97)

and gives:

38y+95z=81 (mod 97)

44y+52z=47 (mod 97)

This is now a simple linear equation (in a modulo form), and which can be easily solved. In a matrix form this becomes:

and we can solve for y and z with:

We can now easily solve this with y=5 and z=6. Here is the code [here]:

import numpy as np
from inv import modMatInv
import sys

p=97

w=7
x=4


if (len(sys.argv)>1):
    w=int(sys.argv[1])
if (len(sys.argv)>2):
    x=int(sys.argv[2])

if (len(sys.argv)>3):
    p=int(sys.argv[3])

def printM(M):
  rtn = ""+str(M[0][0])+"w^2 + "+str(M[0][1]+M[1][0])+"wx + "+str(M[1][1])+"x^2 + "+str(M[0][2]+M[2][0])+"wy + "+str(M[1][3]+M[3][1])+"xz + " +str(M[0][3]+M[3][0])+"wz + "+str(M[1][2]+M[2][1])+"xy" 
  return rtn

def revealM(M,w,x):
  rtn = ""+str(M[0][0]*w*w) +" + "+str((M[0][1]+M[1][0])*w*x)+" + "+str(M[1][1]*x*x)+" + "+str((M[0][2]+M[2][0])*w)+"y + "+str((M[1][3]+M[3][1])*x)+"z + " +str((M[0][3]+M[3][0])*w)+"z + "+str((M[1][2]+M[2][1])*x)+"y" 
  return rtn


M0=[[1,2,1,1],[2,3,3,-2],[1,3,0,0],[1,-2,0,0]]
M1=[[5,2,1,2],[1,3,2,2],[3,2,0,0],[6,-3,0,0]]
M2=[[4,2,2,1],[3,3,3,-2],[0,3,0,0],[2,-3,0,0]]
M3=[[6,2,1,1],[5,4,3,-3],[1,6,0,0],[1,-5,0,0]]

print ("p=",p)

print ("\nM0:",M0)
print ("M1:",M1)
print ("M2:",M2)
print ("M3:",M3)

# res = m . M0 . m^{-1}
res0=96
res1=36
res2=95
res3=17

a=(res0-(M0[0][0]*(w*w)+(M0[0][1]+M0[1][0])*w*x + (M0[1][1])*x*x ) ) %p
b=(res1-(M1[0][0]*(w*w)+(M1[0][1]+M1[1][0])*w*x + (M1[1][1])*x*x ) ) %p

factor1=( ((M0[0][2]+M0[2][0])*w) +  ((M0[1][2]+M0[2][1]) *x) )  %p
factor2=( ((M0[0][3]+M0[3][0])*w) + ((M0[1][3]+M0[3][1]) *x) )  %p
factor3=( (M1[0][2]+M1[2][0])*w) +  ((M1[1][2]+M1[2][1]) *x)  %p
factor4=( ((M1[0][3]+M1[3][0])*w) + ((M1[1][3]+M1[3][1])*x))  %p

print ("w=",w)
print ("x=",x)
print (printM(M0))
print (printM(M1))
print ()
print (revealM(M0,w,x))
print (revealM(M1,w,x))
print ()
print (str(factor1)+"y+"+str(factor2)+"z="+str(a))
print (str(factor3)+"y+"+str(factor4)+"z="+str(b))
print ()


A = np.array([[factor1,factor2], [factor3,factor4]])
B = np.array([a,b])

invA = modMatInv(A,p)

print (invA)

res = np.dot(invA,B) % p


print ("y=",res[0])
print ("z=",res[1])

And a sample run [here]:

p= 97

M0: [[1, 2, 1, 1], [2, 3, 3, -2], [1, 3, 0, 0], [1, -2, 0, 0]]
M1: [[5, 2, 1, 2], [1, 3, 2, 2], [3, 2, 0, 0], [6, -3, 0, 0]]
M2: [[4, 2, 2, 1], [3, 3, 3, -2], [0, 3, 0, 0], [2, -3, 0, 0]]
M3: [[6, 2, 1, 1], [5, 4, 3, -3], [1, 6, 0, 0], [1, -5, 0, 0]]
w= 7
x= 4
1w^2 + 4wx + 3x^2 + 2wy + -4xz + 2wz + 6xy
5w^2 + 3wx + 3x^2 + 4wy + -1xz + 8wz + 4xy

49 + 112 + 48 + 14y + -16z + 14z + 24y
245 + 84 + 48 + 28y + -4z + 56z + 16y

38y+95z=81
44y+52z=47

Inverse matrix:
 [[63. 36.]
 [81.  5.]]
y= 5.0
z= 6.0

Here is the full code:

And so with a little bit of secret information (from the vinegar variables) we can take a hard problem, and make it easy, and then discover the oil variables.

Paper: [here]