Mod P Polynomial Operations … Towards Quantum Robust Crypto

Mod P Polynomial Operations … Towards Quantum Robust Crypto

There you go … you can’t accuse me of click-baiting. With a title like this, you’re only going to click on this page, if you really want to read about quantum cryptography.

A demo of this method is defined here.

Mod P polynomials are used in some of the proposed methods in quantum computer robust cryptography, such as with lattice cryptography and especially with Ring Learning With Errors (R-LWE). In this we have polynomial equations with factors for each of the polynomial values. When we normally add we just collect the polynomial powers together and add their values:

a=2x⁴+3x³+10x+3

b=3x⁵+14x³+10x+4

The result will be:

z = a + b = 3x⁵+2x⁴+(3+14)x³+(10+10)x+(3+4) = 3x⁵+2x⁴+20x+7

z = a −b = 3x⁵+2x⁴+(3-14)x³+(10−10)x+(3−4) = 3x⁵+2x⁴–11x³−1

But in Mod P polynomials, we take a value (P), and the take the modulus of the factors. Normally we use a prime number number of P, so that we can perform operations. Let’s say we have:

a=2x⁴+3x³+10x+3

b=3x⁵+14x³+10x+4

Then to add Mod 17, we get:

a+ b = 3x⁵+2x⁴+3x+7 (mod 17)

Then to subtract Mod 17, we get:

a−b = 14x⁵+2x⁴+6x³+16 (mod 17)

Then to multiply Mod 17, we get:

a 𝗑 b = 6x⁹+9x⁸+11x⁷+4x⁶+12x⁵+8x⁴+3x³+15x²+2x+12 (mod 17)

A sample run is:

a(x)=	[3, 10, 0, 3, 2]
b(x)=	[4, 10, 0, 14, 0, 3]
p=	17

== Operations ===
A + B (mod p):	[7, 3, 0, 0, 2, 3]
A * B (mod p):	[12, 2, 15, 3, 8, 12, 4, 11, 9, 6]
A - B (mod p):	[16, 0, 0, 6, 2, 14]

Using Polynomial notation
a(x)=	2x^4 + 3x^3 + 10x + 3
b(x)=	3x^5 + 14x^3 + 10x + 4
p=	17

== Operations ===
A + B (mod p):	3x^5 + 2x^4 + 3x + 7
A * B (mod p):	6x^9 + 9x^8 + 11x^7 + 4x^6 + 12x^5 + 8x^4 + 3x^3 + 15x^2 + 2x + 12
A - B (mod p):	14x^5 + 2x^4 + 6x^3 + 16

Here is an outline of the code, and which shows the power of Python when dealing with lists:

A demo of this method is defined here.

The great thing about using mod P operations (and where P is a prime) is that we can multiply, divide, add and subtract values. For example:

a (mod P) + b (mod P) = (a+b) mod P

a (mod P) x b (mod P) = (a x b) mod P

If you want to see how Mod P applies to real-life quantum robust methods, click here.

Conclusions

We have a problem. Our existing ‘hard’ methods in public key encryption are not going to be that difficult any more with the advent for quantum computers, and we must investigate new ways of digitally signing and key exchange. Mod P polynomials give us a method of generating key pairs which is both a hard problem to crack, but where it is also computationally easy to use the keys.

Get Best Software Deals Directly In Your Inbox