On the hardness of the NTRU problem
https://eprint.iacr.org/2021/821.pdf
The 25 year-old NTRU problem is an important computational assumption in public-key cryptography. However, from a reduction perspective, its relative hardness compared to other problems on Euclidean lattices is not well-understood. Its decision version reduces to the search Ring-LWE problem, but this only provides a hardness upper bound.
We provide two answers to the long-standing open problem of providing reduction-based evidence of the hardness of the NTRU problem. First, we reduce the worst-case approximate Shortest Vector Problem over ideal lattices to an average-case search variant of the NTRU problem. Second, we reduce another average-case search variant of the NTRU problem to the decision NTRU problem.
1Introduction
In the NTRU encryption scheme [HPS98], the public key is an element of a polynomial ring that can be chosen as for some degree monic irreducible polynomial and some integer . This public key is far from uniform in , as it can be written as where the secret key polynomials have coefficients with small magnitudes compared to .
In most concrete instantiations, such as the original scheme and the NTRU and NTRU Prime Round-3 candidates to the NIST post-quantum cryptography standardization project [CDH+20,BBC+20], the coefficients of and even belong to and grows as a small degree polynomial in . As a result, the set of such 's is very sparse in .
[CDH+20]: NTRU round-3 candidate to the NIST post-quantum cryptography standardisation project, 2020. Available at https://ntru.org/ [BBC+20]: NTRU Prime round-3 candidate to the NIST postquantum cryptography standardisation project, 2020. Available at https://ntruprime.cr.yp.to/
The tasks of distinguishing from uniform and recovering a sufficiently short pair from are respectively known as the decision and search variants of the NTRU problem.
The search NTRU problem can be solved with lattice reduction algorithms (such as [Sch87] ), but to succeed for the most usual setting of , they require a computational effort growing as .
In [KF15], Kirchner and Fouque described a heuristic algorithm with slightly subexponential cost for the usual setting of and . If the magnitude bound grows as , then the cost of this algorithm is .
[KF15]: An improved BKW algorithm for LWE with applications to cryptography and lattices.
In the completely different regime of very large (but with and growing at a much smaller pace), recent works [ABD16, CJL16, KF17] have shown that the NTRU problem is significantly easier than previously thought. For example, one can recover appropriately distributed with from in quantum polynomial time when . Prior to those works, it was believed that was necessary for polynomial cost. This range of modulus is far from the one used for the NTRU encryption scheme. However, NTRU instances with a large modulus can occur in more advanced cryptographic constructions such as [LTV12] and [GGH13].
[ABD16]: A subfield lattice attack on overstretched NTRU assumptions - cryptanalysis of some FHE and graded encoding schemes. [CJL16]: An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without an encoding of zero. [KF17]: Revisiting lattice attacks on overstretched NTRU parameters [LTV12]: On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption [GGH13]: Candidate multilinear maps from ideal lattices
On the lower-bound front, it was shown in [SS11] for a power-of-2 cyclotomic and extended in [WW18] to all cyclotomics that if are Gaussian over (restricted to elements that are invertible modulo ) with standard deviation that is a little larger than , then the distribution of is within statistical distance from the uniform distribution over invertible elements of . This variant of decision NTRU is therefore vacuously hard. This parameter regime is relevant to the NTRU signature algorithm [HHP+03,SS13]. It also allows to obtain an NTRU-like public-key encryption scheme, but less efficient than with smaller secret key polynomials .
[SS11]: Making NTRU as secure as worst-case problems over ideal lattices [WW18]: Provably secure NTRUEncrypt over any cyclotomic field [HHP+03]: NTRUSIGN: digital signatures using the NTRU lattice [SS13]: Making NTRUEncrypt and NTRUSign as secure as standard worst-case problems over ideal lattices
Despite 25 years of study, little is known about the relationships between the NTRU problem variants and between them and other well-studied problems over Euclidean lattices.
To our knowledge, the only exceptions are the direct reduction from decision NTRU to search NTRU and a reduction from decision NTRU to the search version of the Ring-LWE problem [SSTX09, LPR10], sketched in [Pei16, Se. 4.4.4]. Note that this only provides an upper bound to the hardness of the NTRU problem. Given this state of affairs, Peikert asked the following question in [Pei16, Se. 7.1]
Is there a worst-case hardness reduction, or a search-to-decision reduction, for an NTRU-like problem?
[SSTX09]: Efficient public key encryption based on ideal lattices [LPR10]: On ideal lattices and learning with errors over rings [Pei16]: A decade of lattice cryptography
2Contributions
We provide positive answers to both components of the above question.
First, we give a reduction from the approximate Shortest Vector Problem restricted to ideal lattices (ideal-SVP) to a worst-case variant of the search NTRU problem. Combining the latter with the recent worst-case to average-case reduction for ideal-SVP from [dBDPW20] leads to a reduction from worst-case ideal-SVP to an average-case version of the search NTRU problem. The instance distribution is inherited from the distribution over ideal lattices considered in [dBDPW20]. We also show that this distribution over NTRU instances can be efficiently sampled from, together with a corresponding trapdoor , if one has access to a quantum computer or if the modulus is sufficiently large: this property allows to sample an NTRU encryption public key along with a corresponding secret key.
[dBDPW20]: Random selfreducibility of Ideal-SVP via Arakelov random walks.
Second, we exhibit a reduction from another (average-case) variant of the search NTRU problem (see below) to the decision NTRU problem. The reduction works for a wide set of distributions for the search NTRU instances, and the decision NTRU instance distribution is directly derived from the considered search NTRU distribution. A sufficient condition on the search NTRU distribution is that it produces with overwhelming probability an with trapdoor such that and have balanced coefficients (in canonical embedding) and or is coprime to . This covers in particular the standard ternary distribution for and (i.e., provided we reject when they are not balanced enough or not coprime to (heuristically, this should happen with probability ). On the other hand, the choice of the decision NTRU distribution is much less flexible: even if we start with a ternary distribution for the search NTRU instances, it is very unlikely that the decision NTRU distribution we obtain is ternary. Similarly to the first reduction, we show that if the samples from the search NTRU distribution can be efficiently sampled along with a corresponding trapdoor , then so can the samples from the resulting decision NTRU instance.
3Technical Overview
For the sake of simplicity, in the forthcoming discussion, we restrict ourselves to power-of-2 cyclotomic defining polynomials, i.e., for a power of 2 . In this case, the ring matches the** ring of integers** of the degree- cyclotomic number field. Moreover, the coefficient embedding (which is the one usually considered in the NTRU literature) and the canonical embedding (used in this article) define the same geometry, up to scaling and rotation. (In the core of the paper, the results are presented for arbitrary number fields.)
To state the above contributions formally, we consider several variants of the NTRU problem. We say that is an NTRU instance with gap if there exists such that and . Note that writing rather than the more standard allows one to consider 's that are not invertible modulo and suffices for cryptographic applications. The norm is the Euclidean norm of the vector made of the coefficients of , and the comparison to is justified by the fact that for a uniformly chosen , one expects the smallest such pair to have Euclidean norm around , up to a small polynomial in (in the core of the paper, we consider the Euclidean norm induced by the canonical embedding, which leads to a slightly different definition, differing by another factor). In the literature, the bound on is often absolute rather than relative to : our definition variant stresses the distance to the uniform regime.
For a distribution over NTRU instances with gap , the decision problem -dNTRU consists in distinguishing between and the uniform distribution over .
On the search NTRU side, the situation is more complex. We consider two variants of search NTRU, both of which with a worst-case and an average-case version.
For , the worst-case vector NTRU problem wcNTRU consists, given as input an NTRU instance with gap ,in recovering such that and . Note that if has a trapdoor , then is another NTRU trapdoor of a possibly larger Euclidean norm, for any non-zero . The wcNTRUvec definition allows solutions whose norms are within an approximation factor from the norms of the promise. Even though there may be plenty of solutions of the form for , the pair ratio over is an invariant.
This motivates the definition of the worst-case module NTRU problem wcNTRU, which consists in recovering from This is equivalent to recovering the rank-1 submodule of the rank-2 -module , hence justifying the name.
The average-case counterparts to wcNTRU and wcNTRU are defined analogously.
We now sketch the reduction from ideal-SVP to wcNTRUvec. Let us consider the worst-case variants, and the restriction of ideal-SVP to principal ideals with a known generator: we are given as input a generator of a principal ideal of , and want to use a wcNTRU oracle to find a short non-zero vector in . Any element is of the form for some . Consider a short non-zero . Multiplying it by , we obtain that . This already looks like an NTRU equation with a candidate for .
But note that is in and has no a priori reason to belong to , whereas the element of an NTRU instance must belong to . To handle this difficulty, we can round to (coefficient-wise). This leads to , where both and are small elements of . We obtain the existence of a small pair such that .
We can then provide the element to the wcNTRU oracle. The latter returns a pair such that , and it can be proved that for any such sufficiently short pair, we have that is a short non-zero element of . To handle possibly nonprincipal ideals (and also principal ideals with unknown generator), we rely on the 2-element representation of ideals.
If we forget polynomial factors and rely on a wcNTRUvec oracle with parameters and , the above allows to find approximations to a shortest nonzero vector of an arbitrary ideal of volume for and . Note that the reduction is worst-case to worst-case and handles bounded-volume ideals. To handle both limitations, we rely on the recent worst-case to average-case reduction for ideal-SVP from de Boer et al [dBDPW20]. By using the reduction with ideals from the average-case distribution from [dBDPW20], we obtain a reduction from worst-case ideal-SVP to average-case NTRUvec. Further, the ideals from the average-case distribution from [dBDPW20] have volumes bounded as . This leads to of the order of , which is significantly larger than in many applications. We refine the analysis of [dBDPW20] to show that by allowing the worst-case to average-case ideal-SVP reduction to run in time higher than polynomial in , the average-case ideals from [dBDPW20] can be chosen with smaller volumes. The resulting NTRU modulus is still slightly larger than polynomial, but it can be chosen as small as if one considers sub-exponential time reductions.
We now provide an overview of our second main result, which is a reduction from average-case to dNTRU. This one is applicable for larger than some moderate poly .
At the core of the reduction is an NTRU rerandomization process. Assume we are given some for which there exists a short pair with . Now, for any , we have , which may be rewritten as with and . Further, if and are short, then so is . This hence gives a way to produce arbitrarily many NTRU samples with a common denominator , from a single one. Our aim is to query the dNTRU oracle on many such samples, and gather relevant information to solve .
Concretely, we define the dNTRU distribution and show how to tweak the rerandomization process to be able to use the Oracle Hidden Center Problem (OHCP) framework from [PRS17]. At a high level, in the OHCP framework, one is given access to a decision oracle whose acceptance probabilities on a family of distributions is a function of the distance to a hidden center . Under some conditions on the oracle behaviour, there exists an efficient algorithm that recovers an arbitrarily accurate approximation to , by querying the OHCP oracle on samples from for well-chosen values of . Prior to this work, the OHCP framework has been used to provide a reduction from ideal-SVP to the decision version of Ring-LWE [PRS17], and a search to decision reduction for Ring-LWE [RSW18].
[PRS17]: Pseudorandomness of ring-LWE for any ring and modulus
Let us now look more closely at the rerandomization of . It was shown in [LSS14] that by sampling and from spherical Gaussians over with standard deviation sufficiently above , the distribution of is Gaussian over the ideal with a covariance matrix that is a function of and . This spherical Gaussian rerandomization defines our dNTRU distribution. We extend the proof of [LSS14] to show that if instead we sample and from correlated non-spherical Gaussians over , then the distribution of is Gaussian over with a covariance matrix that can be made to depend solely on for an arbitrary complex root of , and arbitrary. The center of the OHCP instance is (recall that belongs to . Using the dNTRU oracle within the OHCP framework hence allows us to recover an approximation to In the applications from [PRS17,RSW18] of the OHCP framework, one recovers a vector of centers from an approximation by observing that belongs to a lattice: the exact center c can hence be obtained by simply rounding a sufficiently precise approximation . In our case, we cannot proceed similarly, as has rational coordinates. We instead show that the LLL algorithm [LLL82] can be used in a manner similar to [KLL84] to recover from a sufficiently precise approximation to , given an a priori upper bound to .
[LSS14]:GGHLite: More efficient multilinear maps from ideal lattices
4Discussion
The two reductions put forward in this work provide some evidence towards supporting the conjectured hardness of the search vectorial NTRU problem and the decision NTRU problem. They may give the impression that the hardness of the NTRU problems lies somewhere between the hardness of the ideal-SVP and that of Ring-LWE. This is however neglecting the fact that there are several NTRU problem variants, and it is unclear whether they are computationally equivalent. In particular, the reductions are incompatible, in that the first one reduces to and the second one from . reduces to , but it is a reduction from to that we would need to obtain a chain of reductions from ideal-SVP to Ring-LWE via the computationally equivalent NTRU problems. Note that if we assume that ideal-SVP is easy, then these problems are computationally equivalent , but the reduction from ideal-SVP to becomes vacuous. In fact, it seems that and could even be of different natures: when attempting to solve using an oracle, it is unclear how to make the approximation factor appear, as is only parametrized by the promise gap Better understanding the differences between the NTRU variants seems important to better capture the NTRU hardness. In this direction, note that the known attacks specific to NTRU [ABD16, CJL16, KF17] are mostly relevant for : they can also be used to solve , but the quality of the solution obtained for is the same as the one we would obtain by running the attack to solve , and then running an ideal-SVP solver on the dense rank-1 sub-module to obtain a somehow short vector.
Despite the apparent uncomposability of our two reductions, it would be interesting to have NTRU instance distributions that are compatible with both of them. The second reduction is very permissive with respect to the instance distribution, but the latter still has to satisfy some properties. In particular, the canonical embedding of and should be bounded from below and above, and the ideal should be coprime with . We note that in the reduction from ideal-SVP to wcNTRUvec, the element is an element of the ideal-SVP instance ideal, which could be chosen Gaussian. Using standard properties of lattice Gaussians, it is not unlikely that one can prove the desired property on its canonical embedding. There seems to be less flexibility in the choice of . However, one could replace the deterministic rounding by a Gaussian rounding, to then use a similar approach as the one for . Concerning the co-primality with , one could hope to use an inclusion-exclusion argument for Gaussian sums like the one in [SS11].
Concerning the hardness of the NTRU problems relatively to ideal-SVP and Ring-LWE, note that the state of the art suggests that ideal-SVP might be strictly easier than Ring-LWE, as ideal-SVP is known to reduce to Ring-LWE [SSTX09, LPR10, PRS17] but no reduction from Ring-LWE to ideal-SVP is known. In fact, Ring-LWE seems less related to ideal-SVP than to finding two short linearly independent vectors in rank-2 modules over (SIVP): for an appropriate parametrisation, Ring-LWE reduces to the latter problem [LS15] and, although for some other parametrisation, the latter problem reduces to Ring-LWE (by combining [LS15] and [AD17]). From a lattice perspective, NTRU is a generalization of the unique Shortest Vector Problem to rank-2 modules. At this stage, it is unclear whether its complexity matches the one of ideal-SVP (i.e., SVP for rank-1 modules) or the one of SIVP restricted to rank-2 modules. It could also be strictly in between.