Learning with Errors Public Key Cryptosystem with Its Security

The main purpose of this paper is to introduce the LWE public key cryptosystem with its security. In the first section, we introduce the LWE public key cryptosystem by Regev with its applications and some previous research results. Then we prove the security of LWE public key cryptosystem by Regev in detail. For not only independent identical Gaussian disturbances but also any general independent identical disturbances, we give a more accurate estimation probability of decryption error of general LWE cryptosystem. This guarantees high security and widespread applications of the LWE public key cryptosystem.

On the LWE Cryptosystem with More General Disturbance

The main purpose of this paper is to give an extension on learning with errors problem (LWE) based cryptosystem about the probability of decryption error with more general disturbance. In the first section, we introduce the LWE cryptosystem with its application and some previous research results. Then we give a more precise estimation probability of decryption error based on independent identical Gaussian disturbances and any general independent identical disturbances. This upper bound probability could be closed to 0 if we choose applicable parameters. It means that the probability of decryption error for the cryptosystem could be sufficiently small. So we verify our core result that the LWE-based cryptosystem could have high security.

Security estimation of LWE via BKW algorithms

The Learning With Errors(LWE)problem is widely used in lattice-based cryptography,which is the most promising post-quantum cryptography direction.There are a variety of LWE-solving methods,which can be classified into four groups:lattice methods,algebraic methods,combinatorial methods,and exhaustive searching.The Blum–Kalai–Wasserman(BKW)algorithm is an important variety of combinatorial algorithms,which was first presented for solving the Learning Parity With Noise(LPN)problem and then extended to solve LWE.In this paper,we give an overview of BKW algorithms for solving LWE.We introduce the framework and key techniques of BKW algorithms and make comparisons between different BKW algorithms and also with lattice methods by estimating concrete security of specific LWE instances.We also briefly discuss the current problems and potential future directions of BKW algorithms.

A lattice-based signcryption scheme without random oracles

In order to achieve secure signcryption schemes in the quantum era, Li Fagen et al. [Concurrency and Computation： Practice and Experience, 2012, 25（4）： 2112-2122] and Wang Fenghe et al. [Applied Mathematics ＆ Information Sciences, 2012, 6（1）： 23-28] have independently extended the concept of signcryption to lattice-based cryptography. However, their schemes are only secure under the random or- acle model. In this paper, we present a lattice-based signcryp- tion scheme which is secure under the standard model. We prove that our scheme achieves indistinguishability against adaptive chosen-ciphertext attacks （IND-CCA2） under the learning with errors （LWE） assumption and existential unforgeability against adaptive chosen-message attacks （EUF- CMA） under the small integer solution （SIS） assumption.

Efficient hierarchical identity based encryption scheme in the standard model over lattices

Using lattice basis delegation in a fixed dimension, we propose an efficient lattice-based hierarchical identity based encryption（HIBE） scheme in the standard model whose public key size is only（dm^2＋ mn） log q bits and whose message-ciphertext expansion factor is only log q, where d is the maximum hierarchical depth and（n, m, q）are public parameters. In our construction, a novel public key assignment rule is used to averagely assign one random and public matrix to two identity bits, which implies that d random public matrices are enough to build the proposed HIBE scheme in the standard model, compared with the case in which 2d such public matrices are needed in the scheme proposed at Crypto 2010 whose public key size is（2dm^2＋ mn ＋ m） log q. To reduce the message-ciphertext expansion factor of the proposed scheme to log q, the encryption algorithm of this scheme is built based on Gentry＇s encryption scheme, by which m^2 bits of plaintext are encrypted into m^2 log q bits of ciphertext by a one time encryption operation. Hence, the presented scheme has some advantages with respect to not only the public key size but also the message-ciphertext expansion factor. Based on the hardness of the learning with errors problem, we demonstrate that the scheme is secure under selective identity and chosen plaintext attacks.