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.,SIVPy problem,to average-case NTRU problems.Our results also mean that solving a kind of average-case SVPy 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=?(n5.5),average-case NTRU problem over arbitrary cyclotomic field K with[K:Q]=n is at least as hard as worst-case SIVPy problems over K with y=?(n6).

Yang WANG;Mingqiang WANG

School of Mathematics,Shandong University,Jinan 250100,China;Key Laboratory of Cryptologic Technology and Information Security,Shandong University,Jinan 250100,China

计算机科学前沿

[1]Yang WANG;Mingqiang WANG-.On the hardness of NTRU problems)[J].计算机科学前沿,2022(06):129-138

SIVPy,SVPy,n5,cyclotomic

On,hardness,NTRU,problems,affects,heavily,securities,cryptosystems,However,could,only,estimate,specific,parameterized,from,perspective,actual,attacks,whether,there,are,worst,case,average,reductions,like,other,lattice,Ring,LWE,still,open,In,this,paper,show,that,any,algebraic,number,field,suitable,parameters,defined,over,ring,integers,least,corresponding,Hence,combining,known,reduce,basic,ideal,Our,results,also,mean,solving,kind,highly,structured,important,corollary,prove,modulus,arbitrary,n6

0.400623