A combinatorial problem related to sparse systems of equations

Horak, P. and Semaev, I. and Tuza, Zsolt (2016) A combinatorial problem related to sparse systems of equations. DESIGNS CODES AND CRYPTOGRAPHY. pp. 1-16. ISSN 0925-1022 (In Press)

Preview

Text 1512.00943.pdf Download (197kB) | Preview

Abstract

Nowadays sparse systems of equations occur frequently in science and engineering. In this contribution we deal with sparse systems common in cryptanalysis. Given a cipher system, one converts it into a system of sparse equations, and then the system is solved to retrieve either a key or a plaintext. Raddum and Semaev proposed new methods for solving such sparse systems common in modern ciphers which are combinations of linear layers and small S-boxes. It turns out that the solution of a combinatorial MaxMinMax problem provides an upper bound on the average computational complexity of those methods. In this paper we initiate the study of a linear algebra variation of the MaxMinMax problem. The complexity bound proved in this paper significantly overcomes conjectured complexity bounds for Gröbner basis type algorithms. © 2016 Springer Science+Business Media New York

Actions (login required)

Edit Item