In this paper, we introduce a new method to avoid zero reductions in Gröbner basis computation. We call this method LASyz, which stands for Lineal Algebra to compute Syzygies. LASyz uses exhaustively the information of both principal syzygies and non-trivial syzygies to avoid zero reductions. All computation is done using linear algebra techniques. LASyz is easy to understand and implement. The method does not require to compute Gröbner bases of subsequences of generators incrementally and it imposes no restrictions on the reductions allowed. We provide a complete theoretical foundation for the LASyz method and we describe an algorithm to compute Gröbner bases for zero dimensional ideals based on this foundation. A qualitative comparison with similar algorithms is provided and the performance of the algorithm is illustrated with experimental data.

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.