Abstract:
NTRU is a very efficient public-key cryptosystem based on polynomial
arithmetic. Its security is related to the hardness of lattice problems
in a very special class of lattices. This article is motivated by
an interesting peculiar property of NTRU lattices. Namely, we show
that NTRU lattices are proportional to the so-called symplectic lattices.
This suggests to try to adapt the classical reduction theory to symplectic
lattices, from both a mathematical and an algorithmic point of view.
As a first step, we show that orthogonalization techniques (Cholesky,
Gram-Schmidt, QR factorization, etc.) which are at the heart of all
reduction algorithms known, are all compatible with symplecticity,
and that they can be significantly sped up for symplectic matrices.
Surprisingly, by doing so, we also discover a new integer Gram-Schmidt
algorithm, which is faster than the usual algorithm for all matrices.
Finally, we study symplectic variants of the celebrated LLL reduction
algorithm, and obtain interesting speed ups.