We present a generalized learning with errors (LWE) problem, which is essentially a simple and direct extension of the original LWE problem to the case of matrices. Then we use this new version of LWE problem, which we call matrix LWE problem to build new cryptographic schemes, which include a new scalable key distribution scheme, a new key exchanges scheme and a new simple identity-based encryption scheme.

We use the learning with errors (LWE) problem to build a new simple and provably secure key exchange scheme. The basic idea of the construction can be viewed as certain extension of Diffie-Hellman problem with errors. The mathematical structure behind comes from the commutativity of computing a bilinear form in two different ways due to the associativity of the matrix multiplications: (x^t \times A)\times y = x^t \times (A\times y), where x,y are column vectors and A is a square matrix. We show that our new schemes are more efficient in terms of communication and computation complexity compared with key exchange schemes or key transport schemes via encryption schemes based on the LWE problem. Furthermore, we extend our scheme to the ring learning with errors (RLWE) problem, resulting in small key size and better efficiency.

A new fundamental and secure group key management approach with a group controller GC using the theory of polynomial functions over a vector space over finite field is developed, where each member in the group corresponds to a vector in the vector space and the GC computes a central vector, whose inner product with every member's ID vector are identical. The central vector is published and each member can compute a common group key via inner product. The security relies on the fact that any illegitimate user cannot calculate this value without the legitimate vector, therefore cannot derive the group key. This approach is secure and its backward and forward secrecy can be guaranteed. The performance of our approach is analyzed to demonstrate its advantages in comparison with others, which include: 1) it requires both small memory and little computations for each group member; 2) it can handle massive membership change efficiently with only two re-keying messages, i.e., the central vector and a random number; 3) it is very efficient and very scalable for large size groups. Our experiments confirm these advantages and the implementation of our prototype presents very satisfactory performance for large size groups.

In this paper, we prove that the degree of regularity of the family of Square systems, an HFE type of systems, over a prime finite field of odd characteristics q is exactly q, and therefore prove that \begin{itemize} \item inverting Square systems algebraically is exponential, when q=O(n), where n is the number of variables of the system. \end{itemize}

In this paper, we prove a closed formula for the degree of regularity of the family of HFE- (HFE Minus) multivariate public key cryptosystems over a finite field of size q. The degree of regularity of the polynomial system derived from an HFE- system is less than or equal to \begin{eqnarray*} \frac{(q-1)(\lfloor \log_q(D-1)\rfloor +a)}2 +2 & & \text{if is even and is odd,} \\ \frac{(q-1)(\lfloor \log_q(D-1)\rfloor+a+1)}2 +2 & & \text{otherwise.} \end{eqnarray*} Here q is the base field size, D the degree of the HFE polynomial, r=\lfloor \log_q(D-1)\rfloor +1 and a is the number of removed equations (Minus number). This allows us to present an estimate of the complexity of breaking the HFE Challenge 2: \begin{itemize} \item the complexity to break the HFE Challenge 2 directly using algebraic solvers is about 2^{96}. \end{itemize}