No abstract uploaded!

No abstract uploaded!

Short integer solution (SIS) and learning with errors (LWE) are two hard lattice problems. These two problems are believed having huge potential in application of cryptography. In 2012, Ding et al. [5] introduced the first provably secure key exchange based on LWE problem. On the other hand, we believe that it is very difficult to do key exchange on SIS problem only. In 2014, Wang et al. [6] did an attempt, but it was not successful. Mao et al. [7] broke the protocol by an attack based on CBi-SIS problem in 2016. However, their attack is not efficient. In this paper, we present a extremely straightforward and simple attack to Wang’s key exchange and then we will construct a key exchange based on SIS and LWE problems.

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.

No abstract uploaded!