Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

02.11.2016 | Ausgabe 1/2017

Designs, Codes and Cryptography 1/2017

A combinatorial problem related to sparse systems of equations

Zeitschrift:
Designs, Codes and Cryptography > Ausgabe 1/2017
Autoren:
Peter Horak, Igor Semaev, Zsolt Tuza
Wichtige Hinweise
Communicated by J. D. Key.

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.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 1/2017

Designs, Codes and Cryptography 1/2017 Zur Ausgabe

Premium Partner

    Bildnachweise