Reductions Between Hard Lattice Problems,Designs And Analyses Of Cryptosystems Over Lattices

With the rapid development of quantum computing theory and quantum computer technology,the traditional public key cryptography has been greatly chal-lenged.Difficult problems that can resist the attacks of quantum computers,together with designs and analyses of related anti-quantum cryptographic primitives,have become one of the research focuses in cryptography and mathematics.At the beginning of 2019,NIST published the round two submissions of post-quantum cryptography,and 12 out of 26 candidates are lattice-based.The development of lattice-based cryptography follows two main lines:One is to study the computational complexity and searching algorithms for solving hard problems in high dimensional lattices based on the researches of classical lattice problems.The other is to analyze the security of non-lattice-based public key cryptosystems using the algorithms solving hard lattice problems,and further to design the lattice-based cryptosystems.Till now,the most widely used lattice-based problems for designing anti-quantum cryptographic primitives are LWE(Learning With Errors),SIS(Short Integer Solution)and NTRU(Number Theory Research Unit).In this paper,we mainly consider the following three kinds of problems:1.The computational complexities and reductions of Ring-LWE problems and Module-LWE problems;2.Provably secure encryption systems based on NTRU over arbitrary cyclotomic field;3.Constructions of trapdoor functions based on NTRU over general cyclotomic fields,and their applications.Ring-LWE v.s.Module-LWE:In order to balance the security and efficiency,the Ring-LWE problems and Module-LWE problems were studied systematically.Compared with plain LWE problems,the worst-case reduction losses of Ring(Module)-LWE problems are much smaller.Meanwhile,cryptographic primitives based on Ring(Module)-LWE problems have more advantages on efficiency and storage,due to the special algebraic structures of number fields.However,the hardness assumptions of Ring(Module)-LWE problems are stronger than plain LWE problems.Compared with ideal lattices,the algebraic structure of module lattices is more disordered.So it is generally believed that the Module-LWE problems should be more difficult than the Ring-LWE problems with similar parameters.Till now,the only known results about reductions from Module-LWE problems to Ring-LWE problems are given by Albrecht et al.in ASIACRYPT 2017.The technique of modulus-dimension switching is used directly to convert the instance of Normal Form Module-LWE problems to the instance of Ring-LWE problems,then Albrecht et al.analyzed their results in powers-of-2 cyclotomic rings by using coefficient embedding.However,in the content of Module-LWE,the statistical distance of the input and output of modulus-dimension switching method is hard to control.Therefore,the loss of reduction from decisional Module-LWE problems to Ring-LWE problems is exponential,thus the results could not show that decisional Ring-LWE problems with large modulus is harder than decisional Module-LWE problems with small modulus.Also,Albrecht et al.only analyzed the cases of reductions from Normal Form search variant of Module-LWE problems to search variant of Ring-LWE problems in powers-of-2 cyclotomic rings by using coefficient embedding.Reductions from Module-LWE problems to Normal Form Module-LWE problems were not discussed.Moreover,it needs further discussion that if reductions between search variants LWE problems could be applied to more general number fields(or more general cyclotomic fields).In applications,the LWE problems that most cryptosystems relied on are decisional variants(such as NIST candidates KC1,CRYSTALS KYBER,CRYSTALS-DILITHIUM,AKCN).This makes it of great theoretical significance and practical value to study in detail the difference between the Module-LWE problems and the Ring-LWE problems.In this paper,we introduce some proper "bridge" problems,combine the module-dimension switching technique and thoughts used in dual attacks to give a reduction from decision Module-LWE problems with module rank d and computation modulus q to decision Ring-LWE problems with modulus qd over any cyclotomic field K.More precisely,our reduction road-map is:decision Module-LWE problems H Normal Form decision Module-LWE problems→Normal Form search Module-LWE problems → search Ring-LWE problems decision Ring-LWE prob-lems.With the help of good bases of cyclotomic fields(the powerful basis and the decoding basis),our reduction increases the LWE error rate by a small polynomial factor of n:=[K:Q].As an important conclusion,we obtain an efficient reduction from decision Module-LWE problems with modulus q≈O(n5.75)and error rate α≈O(n-4.25)to decision Ring-LWE problems with error rate Γ≈O(n-1/2).Combining the known results,we get a reduction from worst-case module approximate shortest independent vectors problem(SIVPγ)with approximation parameterγ≈O(n5)to corresponding decision Ring-LWE problems.Meanwhile,our result shows that the search variant reductions of Albrecht et al.could work in arbitrary cyclotomic field as well.We also give an efficient self-reduction of RLWE problems,which could be used to prove the hardness of a wide class of Ring-LWE problems with non-prime modulus.In the end,we give a converse reduction from decision Module-LWE problems to a kind of module SIVPγ problems over any cyclotomic field,thus we establish a relationship between worst-case hard module-lattice problems and a class of average-case module SIVPγ problems.Our methods can also be applied to more general algebraic fields K,as long as we can find a good enough basis of the dual Rˇ of the ring of integers of K.Provably secure NTRUEncrypt:The NTRU encryption scheme was devised by Hoffstein,Pipher and Silverman in 1996.It is one of the fastest known lattice-based cryptosystems as testified by its inclusion in the IEEE P1363 standard and regarded as an alternative to RSA and ECC due to its moderate key sizes,high efficiency and potential of resisting attacks by quantum computers.Based on the underlying problem of NTRU,various cryptographic primitives were designed.Cryptosystems based on NTRU have many advantages,such as simple designs,small parameters and high efficiency.Some encryption and key exchange algorithms based on NTRU,for example NTRU,NTRU PRIME,were also selected to the round 2 candidates of NIST.However,the securities of the classic NTRUEncrypt and its variant encryption systems are heuristic.This is quite different from the encryption systems based on LWE.In EUROCRYPT 2011,Stehle and Steinfeld gave the first provably secure NTRUEncrypt by linking the security of NTRUEncrypt to the worst-case ideal lattice problems.More precisely,they used coefficient embedding to prove that the IND-CPA security of their NTRUEncrypt relied on the corresponding(polynomial)Ring-LWE problems in powers-of-2 cyclotomic rings.Then,combining the known results,they could prove that for appropriate parameters,the IND-CPA security of their NTRUEncrypt can be guaranteed by the worst-case ideal lattices problems in these special kind of cyclotomic rings.An open problem proposed by Stehle and Steinfeld is whether their construction can be improved to more general rings.Soon after,Yu et al.extended provably secure NTRUEncrypt to prime and prime-powers cyclotomic rings respectively.Considering the attack efficiency of the existing attack algorithms,the dimensions of lattices used in the designs of lattice-based cryptosystems are generally no less than 512.To achieve this requirement,both prime and prime-powers cyclotomic fields may contain too many subfields.Due to the subfield attack,the computational complexity of basic hard lattice problems in these special fields may be lower than that in more general fields.Accordingly,the security of the cryptosystems designed in these special fields may have potential risks.In this paper,we prove that the statistical distance of h=g·f-1 and U(Rq×)is negligible for suitable parameters over any cyclotomic field,as long as the secret key f,g of NTRUEncrypt obeys to some suitable discrete Gaussians.With the help of good bases of cyclotomic fields(the powerful basis and the decoding basis),we introduce the concept of basis-coefficient embedding and propose a new provably IND-CPA secure NTRUEncrypt schemes in the standard model by using the canonical embedding over any cyclotomic field.The IND-CPA security of our scheme is based on the decisional variants of Ring-LWE problems.So,combining the known results,we could prove that the IND-CPA security of our NRTUEn-crypt could be guaranteed by the worst-case basic ideal lattices problems(such as SIVPγ).Meanwhile,compared with the known provably secure NTRUEncrypts,the bounds of the reduction parameter γ and the modulus q in our scheme are less dependent on the choices of plain-text spaces.This leads to that our scheme provides more flexibilities for the choices of parameters with higher efficiency under weaker security assumption.Furthermore,the probability that the decryption algorithm of our scheme fails to get the correct plain-texts is much smaller than those of the previous works.We also give a reduction from dual Ring-LWE problems to primal Ring-LWE problems in cyclotomic fields with quite small reduction losses.Trapdoors based on NTRU:One of the widely used trapdoor functions based on lattices was proposed by Gentry et al..Gentry et al.used the improved nearest plane algorithm to give an efficient method of sampling discrete Gaussians of a random lattice by using one of its relative short bases.Combining the known methods of generating random lattices and their short bases,Gentry et al.showed how to construct a family of collision resistent,preimage sampleable,trapdoor one-way functions in Euclidean lattices.They also give a series of applications(for example,they designed provably secure signatures and identity-based encryption schemes based on worst-case basic lattice problems).These primitives designed in Euclidean lattices can be trivially modified to ideal lattices by using coefficient embedding.However,these trivial modifications do not utilize the special algebraic structures of polynomial rings,and suffices many disadvantages,such as large parameters and low efficiency.Essentially,methods proposed by Gentry et al.were how to use a short basis of a random lattice,then Gentry et al.constructed a new cryptographic primitive and gave many applications.The secret keys of many signatures based on NTRU(for example,NTRUSign)were short bases of NTRU lattices.So,by combining methods of Gentry et al.and the designs of NTRUSign,one may improve constructions of Gentry et al.to ideal lattices more efficiently.Stehle and Steinfeld first noticed this and gave the first provably secure collision resistent preimage sampleable functions over powers-of-2 cyclotomic rings by using coefficient embedding.They then designed the first provably secure NTRUSign by using Hash-and-Sign analogue,the security of their NTRUSign relied on worst-case basic ideal lattice problems in corresponding cyclotomic fields.However,just like the cases of provably secure NTRUEncrypt,if we restrict the cryptosystems to this special kind of cyclotomic polynomial rings,the parameter selections will be more limited.Meanwhile,cryptosystems designed over these rings may have potential security risks.Whether we could design provably secure NTRU signatures over more general polynomial rings is also an open problem raised by Stehle and Steinfeld in their paper.In this paper,we propose a detailed construction of collision resistance preimage sampleable functions over general cyclotomic fields based on NTRU by using canonical embedding.In a wide class of cyclotomic fields,for appropriate parameters,we give an upper bound of value of the Dedekind Zeta function at 2,and prove that the modified key generation algorithm of classic NTRUSign(which is also the key generation algorithm of our collision resistent preimage sampleable functions)is PPT.We also improve some results showed in our earlier work and prove the hardness of a kind of Ring-ISIS problem.We then use the known methods and the good bases of cyclotomic fields(the powerful basis and the decoding basis)to construct provably secure(claw-free)collision resistent preimage sampleable functions over a wide class of cyclotomic fields.We also discuss the cases of constructing these functions in any cyclotomic field.Finally,combining the Hash-and-Sign analogue and the rejection sampling techniques,we give some applications of our(claw-free)collision resistent preimage sampleable functions,such as signatures,identity-based encryption schemes and identity-based signature schemes.