Research And Application Of Provable Security Public-key Cryptosystem Based On LWE

For the quality of simple and efficient linear operation, quantum-resistant and flexible structure, the public-key cryptosystem based on lattice is considered as the most promising post-quantum cryptosystem. At present, LWE and SIS are the most two practical lattice structure in constructing cryptographic system. With the proposal and development of the theory of provable security, it resolve defects where the cryptographic algorithms and protocols are designed by conjecture and fix bugs repeatedly. An method is put forward by the theory which can reduce the hard problems of cryptographic algorithms and protocols to primitives, so that a reliable guarantee of those schemes are provided. Through nearly research and analyses on the cryptosystem based on lattice, the theory of LWE and provable security, our research is as follows:Firstly, the theories of lattice, LWE and provable security are stated in this article. The inner triadic relation and the necessity of constructions of schemes are proposed. This article mainly describes the secure guarantee of LWE, the basic definition of provable security models, and methodology, and also three attack method of LWE, which can help us avoid defects while designing schemes.Secondly, two public-key encryption based on LWE which satisfy provable security are proposed. The first one is BGN class encryption based on LWE. For the consideration of BGN scheme with good homomorphism and GHV scheme aimed at encrypting binary matrix, the hard problem of LWE is embedded into encrypt algorithm, and the encryption scheme is named as BGN class which aimed at encryption multivariant matrix, and its CPA security is proved. The second one is an multi-bit IBE encryption based on LWE is designed. With analyses of ABB scheme offering single-bit encryption, the initial algorithm is modified to an multi-bit one, and also it is INDr-s ID-CPA secure under standard model.Thirdly, an novel NTRU-class digital signature scheme is proposed primarily while two provable public-key scheme based on R-LWE are constructed. In the first part, without decreasing the security of new scheme, the digital signature efficiency is raised up at the meaning of computation complexity. In the next part, on the basis of novel NTRU-class digital signature scheme in the first part, an NTRU-class scheme based on R-LWE is proposed. Our main contribution is embedding the hard problem of R-LWE to signing algorithm, and its EUF-ACMA secure is proved. In the last part, on the basis of LPR’10 scheme, an tamper-proofing encryption scheme based on R-LWE is designed. Our main contribution is to combine the Chinese Remainder Theory with the initial one, and construct a multi-bit encryption while its IND-CCA secure is proved.At last, two application protocal, which one is a PIR protocal based on LWE and the other is TPC protocal based on R-LWE are given out. In the first scenario, with the good “Somewhat” homomorphism of BGN-class public-key scheme based on LWE, we develop an practical privacy information retrieval(PIR) protocol. In the next scenario, an public-key encryption scheme based on R-LWE is used to two-part confidential comparison, and we prove that it is secure and confidential under semi-honesty model while using simulation examples. And also, the protocol can be popularized to an multi-part one.