The method outlined here 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 curve. And so NIST has created a Post Quantum Cryptography (PQC) 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 [paper].
Oil and Vinegar Example |
Method
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^2 + 4wx + 3x^2 + 2 wy - 4wz + 2wx + 6xz = 387 \)
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:
\begin{multline} M =\begin{pmatrix} w & x & y & z \end{pmatrix} \begin{pmatrix} 1 & 2 & 1 & 1\\ 2 & 3 & 3 & -2\\ 1 & 3 & 0 & 0\\ 1 & -2 & 0 & 0\\ \end{pmatrix} \begin{pmatrix} w\\ x\\ y\\ z\\ \end{pmatrix} \end{multline}
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 constrain the values we get, we normally perform \(\pmod p\) operation and where \(p\) is a prime number. This is known as finite field, and are numbers are always constrained between \(0\) and \(p-1\). For example if we select \(p=97\) we have:
\(w^2 + 4wx + 3x^2 + 2 wy - 4wz + 2wx + 6xz = 5 \pmod {97}\)
Now there are multiple solutions to this now for \(w, x, y, z\), so we define \(n\) multivariate polynomials. For example:
\(w^2 + 4wx + 3x^2 + 2wy -4xz + 2wx + 6xy = 96 \pmod{97}\)
\(5w^2 + 3wx + 3x^2 + 4wy -xz + 8wx + 4xy = 36 \pmod{97}\)
\(4w^2 + 5wx + 3x^2 + 2wy -5xz + 3wx + 6xy = 95 \pmod{97}\)
\(6w^2 + 7wx + 4x^2 + 2wy -8xz + 2wx + 9xy = 17 \pmod{97}\)
Now we have 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 \pmod{97}\)
\(245 + 84 + 48 + 28y -4z + 56z + 16y = 36 \pmod{97}\)
and gives:
\(209 + 38y -2z = 96 \pmod{97}\)
\(377 + 44y + 52z = 36 \pmod{97}\)
and gives:
\(38 y + 95 z = -113 \pmod{97}\)
\(44 y + 52 z = -341 \pmod{97}\)
and gives:
\(38 y + 95 z = 81 \pmod{97}\)
\(44 y + 52 z = 47 \pmod{97}\)
In a matrix form this becomes:
\begin{multline} \begin{pmatrix} 38 & 95\\ 44 & 52\\ \end{pmatrix} \begin{pmatrix} y\\ z \end{pmatrix} =\begin{pmatrix} 81\\ 47 \end{pmatrix} \pmod {97} \end{multline}
and we can solve for \(y\) and \(z\) with:
\begin{multline} \begin{pmatrix} y\\ z \end{pmatrix} = {\begin{pmatrix} 38 & 95\\ 44 & 52\\ \end{pmatrix}}^{-1} \begin{pmatrix} 81\\ 47 \end{pmatrix} \pmod {97} \end{multline}
We can now easily solve this to get \(y=5\) and \(z=6\). Here is the code:
# Demo: https://asecuritysite.com/encryption/multiv2 import numpy as np from inv import modMatInv import sys p=97 w=7 x=4 # Unknown y and z 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,res,p): 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="+str(res) +" (mod "+str(p)+")" return rtn def revealM(M,w,x,res,p): 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="+str(res) +" (mod "+str(p)+")" 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,res0,p)) print (printM(M1,res1,p)) print () print (revealM(M0,w,x,res0,p)) print (revealM(M1,w,x,res1,p)) 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 ("Inverse matrix:\n",invA) res = np.dot(invA,B) % p print ("y=",res[0]) print ("z=",res[1])
And a sample run:
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=96 (mod 97) 5w^2 + 3wx + 3x^2 + 4wy + -1xz + 8wz + 4xy=36 (mod 97) 49 + 112 + 48 + 14y + -16z + 14z + 24y=96 (mod 97) 245 + 84 + 48 + 28y + -4z + 56z + 16y=36 (mod 97) 38y+95z=81 44y+52z=47 Inverse matrix: [[63. 36.] [81. 5.]] y= 5.0 z= 6.0
The code is here: