LJKDeterministic Models and Algorithms: CASYS Seminar

On Wednesday December 12 2018 at 13h30 in Room 106  IMAG Building

Seminary of Thomas PREST (PQShield Ltd.)

Solving Generalized Bézout Equations using the Field Norm and Applications to NTRU

Summary

I will present a cute algorithm for solving Bézoutstyle equations in the ring Z[x]/(phi), where phi is a cyclotomic polynomial. This algorithm uses the field norm to map such equations into smaller rings, before lifting the solutions back in the original ring. While the techniques used are wellknown in algorithmic number theory, we are not aware of them being previously applied in this setting. This has applications in latticebased cryptography, making some algorithms faster and more memoryefficient by a factor 100.
