Crypto 2016: A subfield lattice attack on overstretched NTRU assumptions

This year's Crypto kicked off this morning in sunny Santa Barbara. The early afternoon session in track A covered asymmetric Ccryptography and cryptanalysis. Shi Bai presented A subfield lattice attack on overstretched NTRU assumptions: Cryptanalysis of some FHE and Graded Encoding Schemes, which is joint work with Martin Albrecht and Leo Ducas. The talk consisted of three main parts, an introduction, a presentation of the subfield attack and a discussion on its implications.

Introduction

The set-up of the problem is the usual one. Let $\Phi_m$ be a cyclotomic power-of-two polynomial and let $R$ be the ring $R = \mathbb{Z}[x]/\Phi_m$. We let $\lambda$ be the security parameter, $n=\phi(m)=poly(\lambda)$, $q=q(\lambda)$ and $\sigma = poly(\lambda)$. The NTRU problem is the following.

NTRU Problem: We are given a ring $R$ of rank $n$, a modulus $q$, a distribution $D$ and a target norm $\tau$. Given an element $h = [gf^{-1}]_q$ (subject to $f$'s invertibility modulo $q$) for $f, g \leftarrow D$, the NTRU$(R,q,D,\tau)$ problem is to find a vector $(x,y)\neq (0,0) \in R^2 \mod q$ of Euclidean norm smaller than  $\tau\sqrt{2n}$ in the lattice

$\Lambda_h^q = \{ (x,y)\in R^2 : hx-y = 0 \mod q \}$.

We call the above the NTRU lattice.

What the authors mean by overstretched NTRU assumption is the use of super-polynomial modulus $q$ which is utilised in the context of NTRUEncrypt, signature schemes, Fully Homomorphic Encryption schemes and some candidate multilinear maps.

The starting point of the attack is that whenever

$ |f| \approx |g| \approx \sqrt{n}\sigma \ll \sqrt{nq}$,

then the NTRU lattice has an unusually short vector. We also note that, for some target norm, recovering a short enough vector is sufficient to carry the attack. In particular, finding a vector of length $o(q)$ would break applications such as encryption. We note however that in practice, parameters can indeed be set so as to avoid this attack.

The attack

Let $K$ be the cylotomic field $\mathbb{Q}(x)/\Phi_m$ and $L = \mathbb{Q}(x)/\Phi_{m'}$ a subfield, where we have that $m'|m$ and we let $\zeta_m$ and $\zeta_m'$ be the $m^{th}$, respectively $m'^{th}$ roots of unity. The authors here work with power-of-two cyclotomics, but we note that such a subfield can always be found; indeed we can take the maximal real subfield.

The strategy is as follows. We use the fact that $L$ is a subfield of $K$ to use the norm map

$N_{K/L}: K \rightarrow L$

to map down NTRU instances to the subfield, assuming we are working on overstretched large modulus $q$. We then apply lattice reduction (e.g. BKZ) to the subfield, solving a potentially easier problem.

For an NTRU instance $(h,f,g)$ in the full field, we norm it down to an instance $(h',g',g')$ of the subfield. Now the vector $(f',g')$ is in the subfield NTRU lattice $\Lambda_{h'}^q$ and depending on the parameters, it may be unusually short. The attack then proceeds by running a lattice reduction algorithm on the subfield, which produces a vector $(x',y')$. Then, if that vector is short enough, it is in fact an $\mathcal{O}_K$-multiple of $(f',g')$ and we have $(x',y')=v(f',g')$. This allows to lift $(x',y')$ to the full NTRU lattice $\Lambda_{h}^q$ and thus potentially recover non-trivial information on $f$ and $g$.

Consequences

This produces a sub-exponential attack on bootstrappable YASHE. The work also implies an attack on the latest GGH construction without an encoding of zero. Depending on the multilinear degree, this can even go down to a polynomial attack. Compared to the prior state of the art, this is the best attack there is.

In terms of limitations, if the normed down vector $(f',g')$ is not unusually short, then this attack fails. Equally, NTRU-743, NTRU-401 and BLISS are essentially immune. The conclusion of this talk was that in an NTRU assumption set-up, the presence of a subfield, a large modulus and a small $\sigma$ should be considered insecure.