MathSciDoc: An Archive for Mathematician ∫

MutantXL is an algorithm for solving systems of polynomial equations that was proposed at SCC 2008 and improved in PQC 2008. This article gives an overview over the MutantXL algorithm. It also presents experimental results comparing the behavior of the MutantXL algorithm to the $F_4$ algorithm on HFE and randomly generated multivariate systems. In both cases MutantXL is faster and uses less memory than the Magma's implementation of $F_4$.

In this paper, we present a new algorithm, such that, for the small integer solution (SIS) problem, if the solution is bounded ( by an integer \beta in l_\infty norm, which we call a bounded SIS (BSIS) problem, {\it and if the difference between the row dimension n and the column dimension m of the corresponding matrix is relatively small with respect the row dimension m}, we can solve it easily with a complexity of polynomial in m.

In this paper, we present a new algorithm, such that, for the learning with errors (LWE) problems, if the errors are bounded -- the errors do not span the whole prime finite field F_q but a fixed known subset of size D (D<q), which we call the learning with bounded errors (LWBE) problems, we can solve it with complexity O(n^D).

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}

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}

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.

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.

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.

In this paper we present a new algorithm to attack lattice based cryptosystems by solving a problem over real numbers. In the case of the NTRU cryptosystem, if we assume the additional information on the modular operations, we can break the NTRU cryptosystems completely by getting the secret key. We believe that this fact was not known before.

We present a new method for building pairs of HFE polynomials of high degree, such that the map constructed with such a pair is easy to invert. The inversion is accomplished using a low degree polynomial of Hamming weight three, which is derived from a special reduction via Hamming weight three polynomials produced by these two HFE polynomials. This allows us to build new candidates for multivariate trapdoor functions in which we use the pair of HFE polynomials to fabricate the core map. We performed the security analysis for the case where the base field is GF(2) and showed that these new trapdoor functions have high degrees of regularity, and therefore they are secure against the direct algebraic attack. We also give theoretical arguments to show that these new trapdoor functions over GF(2) are secure against the MinRank attack as well.