Cutting dimensions in the LLL attack for the ETRU post-quantum cryptosystem

NTRU is one of the most important post-quantum cryptosystems nowadays, based on polynomial rings with coefficients in Z. Among its variants, the ETRU cryptosystem utilizes Eisenstein integers Z[ω], where ω is a primitive cube root of unity. We explore this cryptosystem and introduce a new lattice based on May’s technique, which proposes reducing the original lattice dimension to enable attacks with increased complexity. This new lattice allowed us to recover the private key of the ETRU system for a dimension that was not yet possible using current lattice reduction techniques over the original lattice.