2017 | OriginalPaper | Buchkapitel
Revisiting Lattice Attacks on Overstretched NTRU Parameters
verfasst von : Paul Kirchner, Pierre-Alain Fouque
Erschienen in: Advances in Cryptology – EUROCRYPT 2017
Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
NTRUEncrypt
standard. They allow to recover the secret key given the public key of Fully Homomorphic Encryption schemes based on NTRU ideas. Hopefully, these attacks do not endanger the security of the NTRUEncrypt
, but shed new light on the hardness of the NTRU problem. The idea consists in decreasing the dimension of the NTRU lattice using the multiplication matrix by the norm (resp. trace) of the public key in some subfield instead of the public key itself. Since the dimension of the subfield is smaller, so is the dimension of the lattice and better lattice reduction algorithms perform.NTRUEncrypt
. Instead of using the norm and trace, the multiplication by the public key in a subring allows to break smaller parameters and we show that in \(\mathbb {Q}(\zeta _{2^n})\), the time complexity is polynomial for \(q=2^{\mathrm {\Omega }(\sqrt{n\log \log n})}\). Then, we revisit the lattice reduction part of the hybrid attack of Howgrave-Graham and analyze the success probability of this attack using a new technical tool proposed by Pataki and Tural. We show that, under some heuristics, this attack is more efficient than the subfield attack and works in any ring for large q, such as the NTRU Prime ring. We insist that the improvement on the analysis applies even for relatively small modulus; although if the secret is sparse, it may not be the fastest attack. We also derive a tight estimation of security for (Ring-) LWE and NTRU assumptions and perform many practical experiments.