### Twisted-PHS: Using the Product Formula to Solve Approx-SVP in Ideal Lattices

##### Abstract

Approx-SVP is a well-known hard problem on lattices, which asks to find short vectors on a given lattice, but its variant restricted to ideal lattices (which correspond to ideals of the ring of integers $\mathcal{O}_{K}$ of a number field $K$) is still not fully understood. For a long time, the best known algorithm to solve this problem on ideal lattices was the same as for arbitrary lattice. But recently, a series of works tends to show that solving this problem could be easier in ideal lattices than in arbitrary ones, in particular in the quantum setting. 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 reaches the same asymptotic trade-off between runtime and approximation factor 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.

Available format(s)
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2020
DOI
10.1007/978-3-030-64834-3_12
Keywords
Ideal Lattices Approx-SVP S-unit attacks Twisted-PHS Algorithm
Contact author(s)
olivier bernard @ normalesup org
History
2022-09-19: last of 2 revisions
See all versions
Short URL
https://ia.cr/2020/1081

CC BY

BibTeX

@misc{cryptoeprint:2020/1081,
author = {Olivier Bernard and Adeline Roux-Langlois},
title = {Twisted-PHS: Using the Product Formula to Solve Approx-SVP in Ideal Lattices},
howpublished = {Cryptology ePrint Archive, Paper 2020/1081},
year = {2020},
doi = {10.1007/978-3-030-64834-3_12},
note = {\url{https://eprint.iacr.org/2020/1081}},
url = {https://eprint.iacr.org/2020/1081}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.