Our main contribution is to propose a new ``twisted'' version of the PHS (by Pellet-Mary, Hanrot and Stehlé 2019) algorithm, that we call Twisted-PHS. As a minor contribution, we also propose several improvements of the PHS algorithm. On the theoretical side, we prove that our Twisted-PHS algorithm performs at least as well as the original PHS algorithm. On the practical side though, we provide a full implementation of our algorithm which suggests that much better approximation factors are achieved, and that the given lattice bases are a lot more orthogonal than the ones used in PHS. This is the first time to our knowledge that this type of algorithm is completely implemented and tested for fields of degrees up to~$60$.
Category / Keywords: public-key cryptography / Ideal Lattices, Approx-SVP, PHS Algorithm Original Publication (with major differences): IACR-ASIACRYPT-2020 Date: received 8 Sep 2020 Contact author: olivier bernard at irisa fr Available format(s): PDF | BibTeX Citation Version: 20200909:064750 (All versions of this report) Short URL: ia.cr/2020/1081