In this paper, we present a new algorithm to solve algebraically the following lattice-related problems: 1) the small integer solution (SIS) problem under the condition: if the solution is bounded by an integer β in l_∞ norm, which we call a bounded SIS (BSIS) problem, and if the difference between the row dimension n and the column dimension m of the corresponding basis matrix is relatively small with respect the row dimension m; 2) the learning with errors (LWE) problems under the condition: 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 a learning with bounded errors (LWBE) problem. We will show that we can solve these problems with polynomial complexity.

We propose a new efficient hardware implementation of Rainbow signature scheme. We enhance the implementation in three directions. First, we develop a new parallel hardware design for the Gauss-Jordan elimination, and solve a 12 ×12 system of linear equations with only 12 clock cycles. Second, a novel multiplier is designed to speed up multiplication of three elements over a finite field. Third, we design a novel partial multiplicative inverter to speed up the multiplicative inversion of finite field elements. Through further other minor optimizations of the parallelization process and by integrating the major optimizations above, we build a new hardware implementation, which takes only 198 clock cycles to generate a Rainbow signature, a new record in generating digital signatures and four times faster than the 804-clock-cycle Balasubramanian-Bogdanov-Carter-Ding-Rupp design with similar parameters.

In this paper, we present an experimental analysis of HFE Challenge 2 (144 bit) type systems. We generate scaled versions of the full challenge fixing and guessing some unknowns. We use the MXL_3 algorithm, an efficient algorithm for computing Gröbner basis, to solve these scaled versions. We review the MXL_3 strategy and introduce our experimental results.

Recent developments in multivariate polynomial solving algorithms have made algebraic cryptanalysis a plausible threat to many cryptosystems. However, theoretical complexity estimates have shown this kind of attack unfeasible for most realistic applications. In this paper we present a strategy for computing Gröbner basis that challenges those complexity estimates. It uses a flexible partial enlargement technique together with reduced row echelon forms to generate lower degree elements–mutants. This new strategy surpasses old boundaries and obligates us to think of new paradigms for estimating complexity of Gröbner basis computation. The new proposed algorithm computed a Gröbner basis of a degree 2 random system with 32 variables and 32 equations using 30 GB which was never done before by any known Gröbner bases solver.

Recently, the Little Dragon Two and Poly-Dragon multivariate based public-key cryptosystems were proposed as efficient and secure schemes. In particular, the inventors of the two schemes claim that Little Dragon Two and Poly-Dragon resist algebraic cryptanalysis. In this paper, we show that MXL2, an algebraic attack method based on the XL algorithm and Ding’s concept of Mutants, is able to break Little Dragon Two with keys of length up to 229 bits and Poly-Dragon with keys of length up to 299. This contradicts the security claim for the proposed schemes and demonstrates the strength of MXL2 and the Mutant concept. This strength is further supported by experiments that show that in attacks on both schemes the MXL2 algorithm outperforms the Magma’s implementation of F4.