Authors: Peter Horak Igor Semaev Zsolt Tuza
Publish Date: 2016/11/02
Volume: 85, Issue: 1, Pages: 129-144
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 Sboxes 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 algorithmsThe authors are indebted to Noga Alon for discussions on expanders and on probabilistic methods which lead to an improvement of the lower bound in Theorem 1 and to Øyvind Ytrehus for a discussion on the Gilbert–Varshamov bound Research of P Horak was supported in part by a Grant from SIAS University of Washington Tacoma Research of P Horak and I Semaev was supported in part by a Grant SPIRE Program in 2013–2015 from University of Bergen Research of I Semaev was also partly supported by the EEA Grant SK06IV01001 and the State Budget of the Slovak Republic from the EEA Scholarship Programme Slovakia Research of Zs Tuza was supported in part by the Grant TÁ MOP422B15/1/KONV20150004
Keywords: