Parallel Gaussian elimination for XL family over GF(2)

• Published in: Security and communication networks 2014-03, Vol.7 (3), p.503-510
• Main Authors: Huang, Heliang, Bao, Wansu, Liu, Shukai
• Format: Article
• Language: English
• Subjects: algebraic attack; Algorithms; Complexity; Gaussian elimination; Linear algebra; Mathematical analysis; parallel fast Gaussian elimination; Polynomials; Reduction; Security; structured Gaussian elimination; Workload; XL family; XL_SP
• ISSN: 1939-0114; 1939-0122
• DOI: 10.1002/sec.744

ABSTRACT The security of many cryptographic systems is based on the difficulty of solving systems of quadratic multivariate polynomial equations. XL family (which stands for eXtended Linearization) is a traditional type of algorithm for solving systems of multivariate polynomial equations over finite fields. The main idea of these algorithms is to extend the initial system by monomials multiplications and use linear algebra techniques to solve the system. The overall complexity of XL family is essentially determined by the workload of Gaussian elimination step. In this paper, we use the structured Gaussian elimination and parallel fast Gaussian elimination to reduce the complexity of XL family over GF(2). Because of the sparsity of the extended system, structured Gaussian elimination is applied to reduce the dimensions of the extended system. Thus, a great reduction of the storage can be obtained. By slightly modifying the logic of ordinarily Gaussian elimination, we parallelly compute the reduced system. Theory analysis indicates that the complexity of our improved XL, XL_SP, is (λT)2, which is far lower than (7/64)T2.8, the complexity of XL, where T is the number of monomials and λ is the ratio of the dimensions of the reduced system to the extended system. Further experiments to Hidden Field Equation cryptosystems show that about 90% reduction of the extended system is achieved by using structured Gaussian elimination, which means λ is about 1/10 in our experiments. Copyright © 2013 John Wiley & Sons, Ltd. In this paper, our goal is to improve the two major weaknesses of XL family algorithms: the storage problem and the huge workload of Gaussian elimination step. We present the XL_SP, a combination of XL and an improved parallel Gaussian elimination (IPGE), to reduce the time and space cost of XL family over GF(2). The XL_SP will make the algebraic attacks be more practical.