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.
Metadata
- Available format(s)
-
PDF
PS
- Publication info
- Published elsewhere. Unpublished manuscript
- Keywords
- Algebraic cryptanalysismultivariate polynomial equationlinearizationXLsparse linear systemstructured Gaussian elimination
- Contact author(s)
- abhij @ cse iitkgp ernet in
- History
- 2012-04-11: received
- Short URL
- https://ia.cr/2012/176
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2012/176,
author = {Satrajit Ghosh and Abhijit Das},
title = {Improvements of Algebraic Attacks Based on Structured Gaussian Elimination},
howpublished = {Cryptology ePrint Archive, Paper 2012/176},
year = {2012},
note = {\url{https://eprint.iacr.org/2012/176}},
url = {https://eprint.iacr.org/2012/176}
}
