Member-only story
Post-quantum: Lattice, Polynomials and Modulo
If you are away from work over Christmas and have some spare time, why not learn a little bit of theory?
One thing that worries me about this modern world, is that there can sometimes be a lack of deep knowledge around some of the core theoretical aspects. As a profession, there must be core fundamental knowledge that moves away from a surface learning approach in order develop a deep understanding of the core principles. One current weak area is in post-quantum cryptography, and especially the move towards lattice cryptography. So let’s take a simple example.
With lattice methods we use the shortest vector problem in a lattice, and which has an underpinning difficulty of factorizing polynomials. The lattice vector points are represented as polynomial values.
For this, we create modulo polynomial and then generate its inverse. In this case, we will create a polynomial (f) and then find its modulo inverse (f_p), and which will result in:
f⋅f_p=1 (mod p)
Thus, if we then take a message (m) and multiply by f and then by f_p, we should be able to recover the message. Let’s take an example, with N=11 (the highest polynomial factor), p=31 and where Bob picks polynomial factors (f) of:
