The hardness of NTRU problem affects heavily on the securities of the cryptosystems based on it.However,we could only estimate the hardness of the specific parameterized NTRU problems from the perspective of actual at...The hardness of NTRU problem affects heavily on the securities of the cryptosystems based on it.However,we could only estimate the hardness of the specific parameterized NTRU problems from the perspective of actual attacks,and whether there are worst-case to average-case reductions for NTRU problems like other lattice-based problems(e.g.,the Ring-LWE problem)is still an open problem.In this paper,we show that for any algebraic number field K,the NTRU problem with suitable parameters defined over the ring of integers R is at least as hard as the corresponding Ring-LWE problem.Hence,combining known reductions of the Ring-LWE problem,we could reduce worst-case basic ideal lattice problems,e.g.,SIVPγproblem,to average-case NTRU problems.Our results also mean that solving a kind of average-case SVPγproblem over highly structured NTRU lattice is at least as hard as worst-case basic ideal lattice problems in K.As an important corollary,we could prove that for modulus q=Õ(n^(5.5)),average-case NTRU problem over arbitrary cyclotomic field K with[K:Q]=n is at least as hard as worst-case SIVP_(γ)problems over K with γ=Õ(n^(6)).展开更多
基金supported by the National Key Research and Development Program of China (2018YFA0704702)the National Natural Science Foundation of China (Grant No.61832012).
文摘The hardness of NTRU problem affects heavily on the securities of the cryptosystems based on it.However,we could only estimate the hardness of the specific parameterized NTRU problems from the perspective of actual attacks,and whether there are worst-case to average-case reductions for NTRU problems like other lattice-based problems(e.g.,the Ring-LWE problem)is still an open problem.In this paper,we show that for any algebraic number field K,the NTRU problem with suitable parameters defined over the ring of integers R is at least as hard as the corresponding Ring-LWE problem.Hence,combining known reductions of the Ring-LWE problem,we could reduce worst-case basic ideal lattice problems,e.g.,SIVPγproblem,to average-case NTRU problems.Our results also mean that solving a kind of average-case SVPγproblem over highly structured NTRU lattice is at least as hard as worst-case basic ideal lattice problems in K.As an important corollary,we could prove that for modulus q=Õ(n^(5.5)),average-case NTRU problem over arbitrary cyclotomic field K with[K:Q]=n is at least as hard as worst-case SIVP_(γ)problems over K with γ=Õ(n^(6)).
