♫ Somewhere Over The Rainbow ♫ … There’s A Hard Problem

♫ Somewhere Over The Rainbow ♫ … There’s A Hard Problem

An introduction to multivariate cryptography

My routine for solving a research problem is to read up on it in the evening, and find key research papers and presentations, and get up between 5 and 6 am, and — often — I have the solution. Here’s my 6 am doodles from this morning on multivariate cryptography:

As a tip for PhD students, I find that research presentations from researchers who really know there topic is the best place to find a distilled version of methods.

So, there’s a point in every academic researcher’s career, when they realise that - for the more challenge areas of research — Wikipedia articles are basically not written by an expert, and are often just cribbed almost word for word from the research papers. I have found this many times, but rediscovered it when researching multivariate cryptography for a simple example [here]:

For something so important for our security, it is very poorly defined, and I would not recommend anyone getting into research to use Wikipedia for anything beyond the simple methods. My advice is — always — to go and read the papers in the area and key research talks, in your really want to understand key topics.

And, so, there’s only one real way to understand a complex topic in research … read the papers of the people who really know their discipline. So I searched for a nice tutorial for this and really found little, so here we go … (please leave now, if maths scares you) …

Okay … still here? … strap yourself in, it’s going to be a bumpy ride …

Our existing methods of public-key encryption — such as discrete logs, RSA and elliptic curve — are known not to be a hard problem in a world of quantum computers. Multivariate cryptography is a known hard problem and is robust against quantum computers. Examples of methods which use multivariate cryptography are Oil-and-Vinger, Unbalanced Oil and Vinger, and Rainbow. While the original Oil-and-Vinger method has been cracked, we have advanced to Rainbow, and which is one of the finalists for the final round of the NIST competition for PQC (Post-Quantum Cryptography) signatures:

Multivariate cryptography

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

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:

In order to constrain the values we get, we normally perform a (mod p) operation and where p is a prime number. This is known as a finite field, and our 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 and z, so we define n multivariate polynomials. For example:

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

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

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

6w2+7wx+4x2+2wy−8wz+2wx+9wx=17 (mod 97)

The solution to this is: w=7, x=4, y=5, z=6, but it is extremely difficult to solve, and know, and here is the code to prove this [here]:

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])+"wz + "+str(M[0][3]+M[3][0])+"wx + "+str(M[1][2]+M[2][1])+"xz"
  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 ("m=",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 ("Res0=",res1)
print ("Res1=",res2)
print ("Res2=",res3)
print ("Res2=",res4)

print ()
print ()
print ("M0=",printM(M0))
print ("M1=",printM(M1))
print ("M2=",printM(M2))
print ("M3=",printM(M3))

and here is a sample run [here]:

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 + -4wz + 2wx + 6xz
M1= 5w^2 + 3wx + 3x^2 + 4wy + -1wz + 8wx + 4xz
M2= 4w^2 + 5wx + 3x^2 + 2wy + -5wz + 3wx + 6xz
M3= 6w^2 + 7wx + 4x^2 + 2wy + -8wz + 2wx + 9xz

Res0= 96
Res1= 36
Res2= 95
Res2= 17

The code is here:

But, what good is this in solving things? Well, in the Oil and Vinegar method, we have a special trapdoor matrix, and which allows those with secret information to have privileged access to the usage of a public key and a private key. The matrices we defined early have the trapdoors built into them:

Well, there’s more, but I thought I leave it here, as I only want to cover the basics of multivariate cryptography. If this topic interests you, please get in touch, as we are keen to collaborate on related areas. Anyway, here’s the result of my early morning doodle:

With multivariate cryptography, we have fast operations for signatures, and with small signatures. Unfortunately the public key is fairly large and can be up to 1MB in size. There are, too, still worries about its security, too.