Analysis And Design Of Lattice-based Cryptosystems

Along with the development of the informatization of society,information se-curity is very important for building a harmonious and stable social environment.Cryptography is the foundation of information security,and the public-key cryp-tosystem is an important cornerstone to design and build secure information sys-tems.In 1994,Shor presented polynomial-time quantum algorithms for factoring large integers and solving discrete logarithm problems,which makes the research on cryptosystems resisting the attack of quantum computing highly concerned.Among them,lattice-based cryptosystems have become a hot research field in the post-quantum cryptography era because of its advantages in efficiency and security.The analysis and design of several lattice-based schemes are studied in this paper.The main contents and contributions are as follows:?Key Reuse Attack on NewHope ProtocolKey Exchange(KE)is a fundamental cryptographic primitive,allowing two parties to securely generate a common secret key over an insecure network.In 2016,Alkim et al.proposed an RLWE-based key exchange called NewHope.NcwHopc's implementation is very rapid and is one of the famous RLWE-based KE.In the applications of the KE,key reuse is widely adopted for efficiency rea-sons before.To assess the adaptability of the NewHope protocol,the security of NewHope in the key resue model must be analyzed.In a key reuse attack,the receiver reuses his secret key,and the malicious adversary plays the role of the sender with the ability to initiate any number of key exchange sessions with a receiver.To analyze the security of the RLWE-based key exchange under the key reuse model,we need to analyze the property of the error-reconciliation mecha-nism in the scheme.NewHope's error-reconciliation mechanism is more complex than other schemes,which makes the existing attack methods not suitable for Newhope.We analyze the Newhope scheme in the key reuse model.Due to the error-reconciliation mechanism of NewHope is constructed using a special lattice D4,so we focus on the analysis of the relationship between the signal and the lattice D4.By analyzing the algorithms of the scheme,we find several special properties of Newhope:(1)for every signal data,there is one special vector corresponding to it in D4;(2)when the adversary sets the query inputs some special data,each component of the corresponding vectors in the lattice D4 has a "periodic property";(3)this "periodic property" is directly related to the secret key of the receiver.According to these special properties,this paper constructs a key reuse attack on Newhope.In the key reuse attack,the adversary will set some special input data,and then after receiving the signal data from the receiver,finds the corresponding vectors in D4.Finally,the secret key of the receiver can be recovered by using the algorithm given in this paper.This paper presents the first key reuse attack against Newhope,which makes up for the blank of the security analysis of Newhope under the key reuse security model.?Identity-Concealed Authenticated Encryption from Ring Learn-ing With ErrorsIn the public-key setting,Authenticated Encryption(AE)is a form of encryp-tion that guarantees the confidentiality and authenticity of data at the same time.Because AE can sign and encrypt messages in a single step,the computational cost of it is lower than that of traditional signature-then-encryption methods.AE is very suitable for a resources constrained environment and has become one of the important technologies of modern communication security.By identity concealment we mean that the protocol transcript shouldn't leak participants'identity information.ID concealment is relevant for several reasons.For instance,if the identity is not protected in a wireless device,an attacker can eavesdrop on the communications to track the user's location,which leads to attacks direct-ed towards selected users.Identity concealment is mandated or recommended by many standardized and deployed cryptographic protocols like TLS1.3 and Google's QUIC.In this paper,we present a provably secure RLWE-based identity-concealed au-thenticated encryption in the public-key setting,referred to as RLWE-ICAE.Our scheme can be seen as a parallel extension of higncryption scheme proposed by Zhao(CCS 2016)but in the lattice-based setting.RLWE-ICAE can be viewed as a monolithic integration of public-key encryption,key exchange over ideal lattices,identity coucealment,and digital signature.We apply the error-reconciliation mechanism technique proposed by Peikert to construct the part of key exchange and use the rejection sampling technique to ensure the security and feasibility of the scheme.We prove the security of RLWE-ICAE in Zhao's ICAE security model.In the random oracle model,if the RLWE security and AEAD securi-ty can be guaranteed,our scheme satisfies the security requirements of ICAE.Our scheme not only enjoys many properties of higneryption such as forward ID-privacy,receiver deniability,and x-security but also enjoys some properties of lattice-based cryptography,such as worst-case hardness assumption and resis-tance to quantum computer attacks.Our scheme has some other applications,for example,our scheme can be used to construct protocol with 0-RTT function in the post-quantum world.We also give a direct application of one-pass ID-concealed authenticated key exchange protocol transformed from RLWE-ICAE.?Optimizing Bootstrapping in the LWE-based GSW-FHEFully homomorphic encryption(FHE)allows us to perform computations di-rectly over encrypted data and can be widely used in some highly regulated industries.With the development of cloud computing,multiparty computing,and machine learning,FHE is becoming more and more important.Gentry's bootstrapping procedure is used to refresh noisy ciphertexts and is the only way to achieve the goal of FHE up to now.One of the fastest and simplest LWE-based FHE arose from the GSW scheme by Gentry,Sahai and Water in 2013(CRYP-TO 2013),and the scheme improvements based on GSW are called GSW-type schemes.In this paper,a new bootstrapping procedure is proposed for the GSW-type FHE.The bootstrapping scheme of Hiromasa et al.(PKC 2015)is the best LWE-based GSW-type FHE scheme up to now.We first optimize Hiromasa et al's bootstrapping procedure.We find that the homomorphic matrix multiplication operation used to calculate the linear part of the bootstrapping in their scheme is not optimal.In this paper,a new homomorphic matrix-vector multiplication is proposed to replace the homomorphic matrix-matrix multiplication,which makes the scheme in this paper more efficient.Besides,we propose a new technique to homomorphically compute the nonlinear part in bootstrapping procedure.Note that when the permutation matrix and vector arc multiplied,the vector has the property of "circular rotation",and we use this property to construct the nonlin-ear operation part of the bootstrapping procedure.This optimization makes our scheme can evaluate boolean gates and some complex functions.In torms of effieiency,our scheme is faster than work of Hiromasa et al.by a O(?)factor.In terms of security,our scheme decreases the lattice approximation factor from O(N2.5)by Hiromasa et al.to O(N2).In terms of functionality,this paper solves the problcm that the LWE-bascd FHE scheme can not calculate com-plex functions in one bootstrapping operation.In the previous work,researchers can only use the special structure of the ring to quickly calculate complex func-tions,that is,to use RLWE(TLWE)based schemes such as FHEW or TFHE to evaluate complex functions,and our scheme is the first LWE-based FHE that can compute complex functions homomorphically within once bootstrapping.