Cryptology ePrint Archive: Report 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.

Category / Keywords: Algebraic cryptanalysis, multivariate polynomial equation, linearization, XL, sparse linear system, structured Gaussian elimination

Publication Info: Unpublished manuscript

Date: received 2 Apr 2012

Contact author: abhij at cse iitkgp ernet in

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20120411:160040 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]