| Tartalom: |
http://real.mtak.hu/44139/ |
| Archívum: |
MTA Könyvtár |
| Gyűjtemény: |
Status = In Press
Type = Article
|
| Cím: |
A combinatorial problem related to sparse systems of equations
|
| Létrehozó: |
Horak, P.
Semaev, I.
Tuza, Zsolt
|
| Kiadó: |
Springer
|
| Dátum: |
2016
|
| Téma: |
QA Mathematics / matematika
|
| Tartalmi leírás: |
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
|
| Nyelv: |
angol
|
| Típus: |
Article
PeerReviewed
info:eu-repo/semantics/article
|
| Formátum: |
text
|
| Azonosító: |
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)
|
| Kapcsolat: |
MTMT:3156844; doi:10.1007/s10623-016-0294-4
|
