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 = 5\). In the following, we will define values on \(w, x, y, z\) and determine the result for four defined polynomials. Multivariate cryptography is a known hard problem, and is robust against quantum computers. Examples of methods which use Multivariate cryptography are Oil-and-Vinegar, Unbalanced Oil and Vinegar, and Rainbow. Overall Rainbow is one of the finalists for the final round of the NIST competion for PQC (Post-Quantum Cryptography) signatures. In this example, we will use four polynomials of: \(w^2 + 4wx + 3x^2 + 2wy -4wz + 2wx + 6wx = 96 \pmod{97}\); \(5w^2 + 3wx + 3x^2 + 4wy -wz + 8wx + 4wx = 36 \pmod{97}\); \(4w^2 + 5wx + 3x^2 + 2wy -5wz + 3wx + 6wx = 95 \pmod{97}\); and \(6w^2 + 7wx + 4x^2 + 2wy -8wz + 2wx + 9wx = 17 \pmod{97}\), and use values for \(w, x, y, z\). We define this as a quadratic polynomial as a polynomial of degree 2 (the largest power is 2) - also known as Multivariate Quadratic (MQ), and with \(n\) quadratic polynomials with \(n\) variables.
Multivariate cryptography - Multivariate Quadratic (MQ) |
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, 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}
In order to contrain 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}\)
The solution to this is: \(w=7, x=4, y=5, z=6\), but it is extremely difficult to solve. Here is the code to prove the values:
import numpy as np p=97 w=7 x=4 y=5 z=6 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 m=[w,x,y,z] m_dash = np.transpose(m) 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 ("\nm=",m) print ("m^T=",m_dash) print ("\nM0:",M0) print ("M1:",M1) print ("M2:",M2) print ("M3:",M3) # res = m . M0 . m^{-1} res1= np.dot(np.dot(m,M0),m_dash) % p res2= np.dot(np.dot(m,M1),m_dash) % p res3= np.dot(np.dot(m,M2),m_dash) % p res4= np.dot(np.dot(m,M3),m_dash) % p print () print ("M0=",printM(M0)) print ("M1=",printM(M1)) print ("M2=",printM(M2)) print ("M3=",printM(M3)) print ("\nRes0=",res1) print ("Res1=",res2) print ("Res2=",res3) print ("Res2=",res4)
and here is a sample run:
p= 97 m= [7, 4, 5, 6] m^T= [7 4 5 6] 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]] M0= 1w^2 + 4wx + 3x^2 + 2wy + -4xz + 2wz + 6xy M1= 5w^2 + 3wx + 3x^2 + 4wy + -1xz + 8wz + 4xy M2= 4w^2 + 5wx + 3x^2 + 2wy + -5xz + 3wz + 6xy M3= 6w^2 + 7wx + 4x^2 + 2wy + -8xz + 2wz + 9xy Res0= 96 Res1= 36 Res2= 95 Res2= 17
The code is here: