Analysis And Design Of LWE-Based Cryptographic Schemes Over Lattices

The development of quantum computers poses significant new challenges for the research of cryptography.In response to the mortal threat of quantum computing technology to public key cryptographic systems,it is imperative to research cryptographic schemes that are resistant to quantum computing attacks.Lattice-based public key cryptography is a typical representative of post-quantum cryptography,with advantages such as simple and parallel operations,low asymptotic complexity.The learning with errors(LWE)problem on lattices can not only be used to design basic cryptographic primitives such as public key encryption and digital signature,but also can be used to construct advanced cryptographic algorithms such as attribute-based encryption(ABE)and fully homomorphic encryption.Although cryptographic schemes based on the LWE problem can achieve various security requirements,the security and implementation efficiency of existing ABE schemes still need to be further analyzed.In addition,to meet the new requirements of application scenarios,the thesis also aims at designing post-quantum secure oblivious transfer(OT)protocols and key encapsulation mechanisms(KEM).The main research works are as follows:1.Regarding the BGG+14 ABE scheme,the first ABE scheme supporting arithmetic circuit based on the LWE problem,we conduct security analysis from three aspects.Firstly,the BGG+14 ABE scheme has the problem of weak attributes.An associated“decryption key”is accompanied by a weak attribute,and whenever a ciphertext is labeled with this weak attribute,the corresponding “decryption key”can recover one bit of the plaintext.Secondly,to reduce the key size of the BGG+14 ABE scheme,three different “naturally simplified”pre-sampling matrices are proposed to obtain three simplified variants,and the security of these three simplified variants under a collusion attack is analyzed.Finally,the main reason why the modulus in the scheme cannot be composite is analyzed.If the modulus has a small factor,an adversary without decryption permission can successfully obtain the plaintext.2.To address the issue that OT protocols based on classical number-theoretic assumptions are not resistant to quantum computing attacks,an OT protocol based on LWE and indistinguishability obfuscation is proposed under the Universal Composability(UC)security model using a classical dual-mode encryption system.The two modes in the dual-mode encryption system are separately obfuscated while maintaining the same functionality and achieving indistinguishability.We prove that the scheme obtained by obfuscating the two modes still has the properties of a dual-mode encryption system,and the OT protocol derived from it is UC secure.Compared with the OT protocol proposed by Yuan et al.,our protocol has a higher post-quantum security,since our design builds upon the LWE problem.3.The double-mode encryption system based on the LWE problem proposed by Quach can only handle plaintexts of one bit,resulting in the problem that the derived OT protocol needs to be repeated multiple times to achieve multi-bit output.To solve this problem,the Jiang-style key coordination mechanism based on the LWE problem is used as the key technology to extend the single-bit symmetric encryption key to multiple bits,and a multi-bit output double-mode encryption system based on the LWE problem is constructed and an OT protocol with multi-bit output is obtained.Through comprehensive performance comparison analysis,the multi-bit output OT protocol based on the LWE problem can achieve UC security and relatively high efficiency.4.Aiming at the design requirement of post-quantum secure KEMs in multi-user scenarios,a KEM scheme based on the LWE problem is constructed.Firstly,a public key encryption scheme with indistinguishability under chosen plaintext attack is constructed based on the first key exchange protocol on lattices.Secondly,using a variant of the Fujisaki-Okamoto(FO)universal transform with explicit rejection,a KEM based on the LWE problem is designed in the multi-user scenario.Finally,it is proved that the proposed KEM scheme achieves indistinguishability under chosen ciphertext attack.