Characterizing overstretched NTRU attacks

3.1 The full field attack

Coppersmith and Shamir [5] considered the following 2n × 2n matrix

where I_n is the n-dimensional identity matrix and 𝓜_h represents multiplication in R by the public key h. The lattice generated by A_full, which we call 𝓛(A_full), contains the vector (f, g) = (f₀, …, f_n–1, g₀, …, g_n–1), because (f₀, …, f_n–1)𝓜_h (mod q) ≡ (g₀, …, g_n–1). The vector (f, g) has relatively small Euclidean norm, and is most likely a vector of the smallest non-zero length in the lattice 𝓛(A_full). Thus, the NTRU problem can be reduced to computing short vectors in 𝓛(A_full).

Coppersmith and Shamir [5] note that one can derive useful information to recover the secret key even when a multiple of (f, g) is found, for multiples of relatively small norm (yet larger than (f, g)). See [5] for more details. In fact, one can focus on finding a small multiple of f, since given αf, a small multiple of g can be found by computing αfh = αg. The different attacks exploit this fact, and aim to recover (a small multiple of) N_K/L(f), for a subfield L ⊆ K, which can be shown to have a relatively small Euclidean norm.

In the following descriptions, we use the term “f part” for the part of the vector corresponding to the identity matrix, and “g part” for the part corresponding to multiplication by h (or by N_K/L(h) in the subfield lattice).

The subfield attacks [1, 4] The norm attack [1] uses the lattice generated by the rows of the 2n′ × 2n′ matrix

where n′ is the degree of the subfield L and MNK/L(h)′ is an n′ × n′ matrix representing multiplication by N_K/L(h) in L. This lattice contains the short vector (N_K/L(f), N_K/L(g)) = (∏_σ∈Gσ(f), ∏_σ∈Gσ(g)).

In the trace attack [4] one replaces 𝓜_NK/L(h) with 𝓜_TrK/L(h), the matrix representing multiplication by Tr_K/L(h) in L. We focus on the norm attack because it performs slightly better when the polynomials are balanced (that is, the polynomials f and g have approximately the same number of non-zero coefficients).

The subring attack [12] The subring attack can be divided into two steps. First, consider the the following (n′ + n) × (n′ + n) matrix

where Mh′ is an n′ × n matrix representing multiplication by h in L. This lattice contains the short vector (N_K/L(f), N_K/L(f)h) = (f∏_{σ∈G∖{Id}}σ(f), g∏_{σ∈G∖{Id}}σ(f)).

The dimension n′ + n is larger than 2n′, the subfield attack lattice dimension. The second step “projects” the lattice, i.e., deletes columns of Mh′, to reduce the dimension. We denote the projected vector (N_K/L(f), N_K/L(f)h). For rigorous analysis, columns should be chosen independently. This approach offers more flexibility than the subfield attack by allowing one to choose dimensions greater than 2n′.

Previous comparison of the attacks. The size of the modulus q causes a tension between applications and security. Many applications, such as fully homomorphic encryption, need a relatively large modulus, but NTRU with a very large modulus can be broken in polynomial time, even with the Coppersmith-Shamir attack. Hence, it is important to analyze the relation between q and n when studying the security of cryptosystems that are based on overstretched NTRU.

In [1], the experimental results focus on finding the minimal modulus q for which the NTRU problem can be solved with the subfield attack on a fixed n using the LLL algorithm. The subsequent work [8, 12] followed this approach and directly compared to these experiments, both claiming to achieve “better results”. Moreover, [12, Theorem 9] shows that under some conditions, working over a subfield of smaller index (including the full field) will not give worse results despite the increase in dimension (however, see our experimental results for the full field compared to the other attacks in Table 2).

We claim that the lattice dimension, which strongly influences the attacks’ running time, should be central to the attack comparisons. This point has been overlooked in prior work, and thus it is not clear whether the different experiments remain comparable. Table 1 gives a series of experimental “improvements” that decrease q by modifying the dimension. We give results from previous papers and from our own experiments. We ran the subfield and the subring attack using our implementations of these attacks and used the projection technique to reduce the dimension of the lattice. Except for the case log(n) = 12, these comparisons are inconclusive when dimension is taken into account. For a detailed comparison, see the full version of this paper [6].

4.1 The projection technique

The key to the projection technique is that the system of equations corresponding to f ⋅ h = g is assumed to be overdetermined, so one can discard some of the equations. We formalize this assumption, relate it to standard assumptions on NTRU and derive concrete results. Some of these details are missing in [12, Section 3.2].

In the following, let 𝓛(A) be the lattice generated by any of the above attack matrices A, 𝓛′ be the projected lattice of dimension n′ + d, and 𝓜 the upper right quadrant of A. The discrepancy 𝓓(Γ) [7, 13] measures how equidistributed a sequence of points Γ = {γ₁, …, γ_n} in the interval [0, 1] is. Formally defined, D(Γ)=supJ⊆[0,1]T(J,n)n−|J|, where the supremum is taken over all subintervals J of [0, 1], |J| is the length of J, and T(J, n) is the number of points γ_i in J for 1 ≤ i ≤ n. Let 𝓣 be a sequence of elements in ℤⁿ with the dot product. 𝓣 is Δ-homogenously distributed moduloq if for any a ∈ ℤⁿ with at least one coordinate coprime to q, the discrepancy of {[a ⋅ t]_q/q}_t∈𝓣 is at most Δ. We would like to consider the columns of 𝓜 as a set of elements in 𝓣. However, this sequence is not Δ-homogenously distributed modulo q for small Δ: for example when 𝓜 = 𝓜_h, h ⋅ f = g does not distribute homogenously. We define the following weaker notion.

Theorem 1 considers 𝓜_h, and thus also Mh′, as these are the cases of interest in [12, 17] respectively. However, it can be generalized to the other matrices 𝓜 described above. In general, it is not known that the columns of 𝓜_h are (B, f)-weakly homogenously distributed for sufficiently small B. Understanding the distribution of h is extremely important as it underlies the security of NTRU. In general, h is not uniformly distributed in R_q, as can be seen from a simple information-theoretic argument. Hence, understanding the distribution of f^–1 is important in order to understand the distribution of h. Banks and Shparlinski [2] studied how “well spread” the coefficients of f^–1 are, that is, whether they “look and behave like random polynomials”. We remark that the desired property on h may follow from the behaviour of f^–1, but this property is not well formed.

Moreover, it is standard to assume that h = g/f is indistinguishable from random in R_q, see [14]. We remark that this assumption has a strong relation with the weakly homogenous distribution of 𝓜_h. Indeed, if the latter is not true, then one can pick a set of small polynomials a and analyze the distribution of {[a ⋅ t]_q/q}_t∈𝓜h to distinguish it from from a random h. Thus, under the indistinguishability assumption, this set of polynomials has to be negligibly small.

We ran experiments with ternary f, g and verified that the coefficients of [f^–1]_q equidistribute in ℤ_q and that 𝓜_h is (B, f)-weakly homogenously distributed for sufficiently small B. For the rest of the paper, we rely on the following assumption.

Setting d as required in Corollary 1, observe that the dimension of 𝓛′ is n + d ≥ (n log(q) + 1)/(log(q/(2B + 1))). This is similar to the subring lattice in [12, Theorem 6]. Thus, Corollary 1 completes the missing details on the validity of the subring attack and, along with [12, Theorem 6], gives a complete analysis of the subring attack under Assumption 1. We formalize this result in the following theorem. Now, β denotes the block size in the BKZ [21] algorithm.

4.2 Comparing ||N_K/L(g)|| and ||N_K/L(f)h||

In Section 3, we showed that a small vector in the subfield lattice is the vector (N_K/L(f), N_K/L(g)), while in the subring lattice the vector (N_K/L(f), N_K/L(f)h) is small. The f part of these vectors is the same. Our interest is therefore in the g part. Moreover, we know that N_K/L(g) n′-dimension vector and N_K/L(f)h is n-dimensional vector. We show that these two elements have the same Euclidean norm. It then follows that on average the coefficients of N_K/L(g) are larger than the coefficients of N_K/L(f)h. When we truncate the latter to n′ coordinates, its norm becomes smaller than the norm of N_K/L(g). Using an assumption on the distribution of the coefficients of N_K/L(g), we quantify the difference in size. More precisely, Theorem 3 shows, with no further assumptions, that when [K : L] = 2, the average size of the coefficients of N_K/L(g) is expected to be 2 times the average size of the coefficients of N_K/L(f)h. In Theorem 4, we generalize this result for any subfield such that [K : L] = r, and prove that the expected ratio of the average magnitude of the coefficients is r under Assumption 2 below. Our main results are given in Corollaries 2 and 3.

In light of this result, our aim is to show that the ratio between ||N_K/L(g)|| and ||N_K/L(f)h|| tends to 1 as n increases. Then, we can conclude that the subring lattice of dimension 2n′ is expected to contain shorter vectors than the subfield lattice of the same dimension. We use random walks to model the coefficients of a product of two polynomials. A first case is for polynomials whose coefficients are drawn independently and uniformly from the set {–1, 0, 1}. A one-dimensional random walk over ℤ starts at 0 and at each step moves either +1 or –1 with equal probability. Let a_i, for i = 1, …, n, denote independent random variables with value either +1 or –1 with uniform probability, and let w₀ = 0 and wn=∑i=1nai. The series {w_n} defines a random walk over ℤ. The expected distance after n steps is on the order of n. As n increases, the distribution of the series w_n approaches the normal distribution. A second case is for polynomials whose coefficients are drawn from a Gaussian distribution: in a Gaussian random walk, we let a_i follow the Gaussian distribution with standard deviation σ and mean zero. The expected distance after n steps is then on the order of σn. For further background, see [15]. We now consider the specific case of subfield L ⊆ K of index 2.

We would like to generalize this result to r > 2. While the coefficients of gσ₂(g) and gσ₂(f) can be expressed as random walks, and thus follow a Gaussian distribution, they may not be independent.

This assumption seems natural and allows us to prove Theorem 4, a generalisation of Theorem 3 to any r > 0. We experimentally verified that as n grows, the ratio of the norms tends to 1, as in Theorem 4, see Figure 1. From this, we directly get that the ratio of the average coefficient tends to r, see Claim 1.

Figure 1

Experimentally verifying that the ratio of the norms converges to 1.

The following corollary compares small vectors in the subfield and subring lattices of same dimensions, without using projection in the subfield lattice.

It follows that if we take the same lattice dimension in both attacks, the subring lattice contains vectors of smaller size. Therefore one can solve the NTRU problem using the subring attack with a smaller q. As mentioned in [1, Section 6], it is not known that B_subfield is the norm of the shortest vector (see [12, Theorem 5]). Moreover, our experiments in Table 2 show that the ratio between q_subfield and q_subring grows with r. One possible explanation is that (N_K/L(f), N_K/L(f)h) is unbalanced, as we show its f part is much larger than the g part. Therefore, if there exists an integral multiple of this vector that decreases the size of the f part and increases the size of the g part so that the vector becomes balanced, the ratio between the feasible qs would increase.

If the systems of equations derived from the lattices given in Corollary 2 are overdetermined, we can project and get smaller lattices. Since the g part in the subring lattice is smaller than in the subfield one, the subring attack system is more determined than the subfield one.

The following corollary shows that one can use projection to discard more equations in the subring attack and achieve a lower dimension.