Lattice-based Analysis And Construction For Public Key Encryption Schemes

A lattice is defined as a discrete additive subgroup of the Euclidean space.Hard problems in lattices and their solving algorithms,play an important role in public key cryptography.On the one hand,some cryptography schemes,whose security relies on the hardness of the integer factorization problem or the discrete logarithm problem,may be broken by finding short vectors in lattices using the lattice basis reduction algorithms.On the other hand,due to the small integer solution(SIS)problem and the learning with errors(LWE)problem,one can construct cryptography schemes which are based on lattice problems,and provide their security proof under worst-case hardness assumption.In this paper,we study lattice-based analysis and construction for public key en-cryption schemes.Specifically,it includes the security analysis for the famous RSA scheme,and the construction together with the security proof for the revocable hierar-chical identity-based encryption(RHIBE)scheme.1.Lattice-based analysis for the RSA scheme mainly relies on Coppersmith's method.We study the lattice construction used in Coppersmith's method,and thus analyze the im-plicit factorization problem with shared middle bits,the factoring problem for N=prqs with partial known bits,and the problem of solving Bx-Ay=z together with its appli-cations to cryptanalysis for RSA.Our main results are as follows.(1)Provide a better bound for the implicit factorization problem with shared middle bits.The implicit factorization problem assumes that the unknown prime factors of two RSA moduli share a certain number of bits.It also includes the generalized case of more RSA moduli.In PKC 2010,Faugere et al.first analyzed the case where shared bits are middle bits by finding the shortest non-zero vector in a three-dimensional lattice.Later in 2015,their result was improved by Peng et al.who introduced a new technique by running the lattice basis reduction twice.In this paper,we directly apply Coppersmith's method to the implicit factorization problem with shared middle bits.After optimizing the lattice construction used in Coppersmith's method,we obtain a better bound and thus extend the range of the condition for attacking RSA.(2)Improve the result for factoring N=prqs with partial known bits.The RSA variant with the modulus of the form N=prqs,is much faster in the decryption process than the standard RSA.Thus the analysis for its security is also very important.In 2015,Lu et al.obtained the factoring result given partial bits of one prime factor.Later in 2016,Coron et al.showed that when r or s is large enough,only a constant number of bits need to be known and thus can be obtained by exhaustive search.This result was further improved by Coron and Zeitoun in 2018.In this paper,we summarize the above three works into one framework and obtain a generalized result,in which three specific choices of parameters just imply the above three works,respectively.More importantly,we optimize the lattice construction used in Coppersmith's method,and thus improve this generalized result.For the best situation,we only require nearly half as many known bits as Coron and Zeitoun does.(3)Study the problem of finding small solutions of the integer equation Bx-Ay=z and its applications to cryptanalysis for RSA.We use three methods,including Wiener's method,May-Ritzenhofen's method and Coppersmith's method,to solve this equation,and all of them give the same result after omitting some negligible terms.Then based on Coppersmith's method,we present two improvements for solving Bx-Ay=z in some special cases.As the application of these two improvements,we present some new cryptanalysis results for RSA,such as analysis for the generalized implicit factorization problem,attacks with known bits of the prime factor,an attack on RSA when some bits of the private exponent together with the prime factor are exposed,and so on.2.As an extension of identity-based encryption(IBE),RHIBE further supports both key revocation and key delegation simultaneously,which are two important functionalities for cryptographic use in practice.Based on LWE assumption,we study the simplified construction for RHIBE schemes.Our main result is as follows.Present two new RHIBE schemes from lattices,both of which achieve decryption key exposure resistance(DKER).Initially,the constructions of RHIBE schemes with DKER are all based on bilinear or multilinear maps.In 2019,Katsumata et al.provided the first lattice-based RHIBE scheme with DKER.Using the idea of Katsumata et al.,we obtain two new schemes which are more simple and efficient.With new treatment of the identity spaces and the time period space,our first RHIBE scheme needs less memory space than Katsumata et al.'s scheme for the public parameters,the master secret key,the secret key for each identity,and key update information.While these two schemes both satisfy the selective-identity security in the standard model.Our second RHIBE scheme utilizes the technique for lattice basis delegation that keeps the lattice dimension unchanged upon key delegation.Therefore the dimension of matrices and vectors used in this scheme is fixed for different hierarchy,which makes the scheme more efficient.Furthermore,our second RHIBE scheme also achieves the adaptive-identity security in the random oracle model.