Research On New Cryptographic Algorithms From Lattice Assumptions And Their Applications

With the rapid development of quantum computers, the widely applied cryptographic algorithms in cyberspace, which are based on traditional hardness of problems, such as discrete logarithm, factor decomposition and so on, will be threatened. Designing secure cryptographic algorithms against quantum computer attacks, especially for platforms running current operating system, namely post-quantum cryptography, is a hot topic. Recently, the research on post-quantum cryptography has attracted cryptographic researchers’ widely attention, many schemes based on lattice assumptions have been proposed. While the existing lattice-based cryptographic algorithms are still not mature, they are far from reaching new secure requirements of the post-quantum cryptographic communication environments. Therefore, it is urgent for us to investigate new efficient algorithms from lattice which can lay the solid foundation for security in their practical applied environments. In this dissertation, we engage in researching new efficient cryptographic algorithms from lattice assumptions. Our proposed algorithms own new cryptographic functionalities that the existing algorithms do not possess. And compared with previous related algorithms, our proposed lattice-based algorithms are further improved in performance, especially, some of our algorithms can dramatically reduce the communication overhead. Furthermore, we also apply our lattice-based cryptographic algorithms in designing secure data auditing for cloud storage with quantum computers resistance. The main research results are specified as follows:1. Research on public key encryption algorithms from lattice assumptions.(1) We propose an efficient fully homomorphic encryption(FHE) from ring learning with errors(RLWE) assumption. And we use the re-linearization and modulus reduction switching technique to improve the performance, manage the noise growth efficiently, guarantee that the ciphertext size is invariant.(2) With the key-homomorphic property from RLWE, we extend our FHE scheme to a threshold fully homomorphic encryption(TFHE), which can be protected against related-key attacks.(3) We construct public key encryption with keyword search from lattice assumption, our proposed algorithms achieve provable ciphertext indistinguishability in the random oracle model and guarantee trapdoor security.2. Research on identity-based digital signature algorithms from lattice assumptions.(1) We propose an efficient forward secure identity-based signature scheme(FSIBS) from lattice assumption. Our FSIBS scheme can guarantee the unforgeability of the prior signatures even if the current signing secret key is revealed.(2) We propose an efficient fuzzy identity based signature(FIBS) from lattice assumption. We also prove that our proposed scheme achieves strong existential unforgeability under an adaptive chosen message and selective fuzzy identity attack in the random oracle model. As in a fuzzy identity based signature, the identity can be described as an attribute set, thus our FIBS scheme can be well applied in the area of post-quantum secure biometric authentication.3. Research on identity-based lattice-based digital signcryption algorithms.(1) We propose an efficient multi-receiver identity-based signcryption(MIBSC) algorithm from lattice assumptions. The algorithm is provably secure in the random oracle model, which has the indistinguishability against chosen ciphertext attacks under the hardness of learning with errors(LWE), and achieves strong existential unforgeability against chosen message attacks under the small integer solution assumption(SIS). Our proposed MIBSC algorithm can be well applied in post-quantum cryptographic distributed communication environments.(2) We also propose a new identity-based proxy-signcryption(IBPSC) scheme from lattice assumptions. Meanwhile, our IBPSC scheme can guarantee strong existential unforgeability and confidentiality in the random oracle model. Compared with existing IBPSC schemes, our scheme is more secure and more efficient, such that it can be well applied in post-quantum cryptographic communication environments which require the service of proxy-signcryption.4. Research on secure data auditing for cloud storage from lattice assumptions.(1) We give security analysis on a public proof of cloud storage from lattice assumption. And we point out that the scheme is vulnerable to tampering attacks from any malicious cloud service provider, and is also vulnerable to data recovery from any curious third party auditor through solving some linearly equations.(2) We propose an efficient identity-based cloud storage public auditing scheme, which is constructed based on lattice. Our public auditing scheme can protect any malicious cloud server from generating the valid response proof which can pass the verification to cheat the third party auditor(TPA) and the cloud users. Moreover, we need random masking technique results from lattice-based signature to prevent the TPA from revealing the primitive data blocks of cloud users.(3) We propose a secure designated verifier auditing scheme for cloud storage from lattice assumptions. Our scheme can also resist tampering attacks from the malicious cloud server and can resist curiosity data recovery attacks from the curious TPA. Our scheme only requires modular additions and modular multiplications over a moderate modulus rather than pairing computation and modular exponentiation operation, which is more efficient and more practical in the post-quantum cryptographic communication.