LJK-Deterministic 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ézout-style 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 well-known in algorithmic number theory, we are not aware of them being previously applied in this setting. This has applications in lattice-based cryptography, making some algorithms faster and more memory-efficient by a factor 100.
-