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

by Dr Thomas Prest (Thalès Communications & Security)

Thursday Oct 11, 2018, 10:30 AM → 11:30 AM Europe/Paris

Salle XR201 (Bâtiment XLIM)

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.