Paper 2012/176

Improvements of Algebraic Attacks Based on Structured Gaussian Elimination

Satrajit Ghosh and Abhijit Das

Abstract

Algebraic attacks are studied as a potential cryptanalytic procedure for various types of ciphers. The XL_SGE algorithm has been recently proposed to improve the complexity of the XL attack. XL_SGE uses structured Gaussian elimination (SGE) during the expansion phase of XL. In this paper, we establish that XL_SGE suffers from some serious drawbacks that impair the effectiveness of SGE-based reduction at all multiplication stages except the first. In order to avoid this problem, we propose several improvements of XL_SGE. Our modifications are based upon partial monomial multiplication and handling of columns of weight two. Our modified algorithms have been experimentally verified to be substantially superior to XL_SGE.