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.