AuthorsH. Raddum
TitleMRHS Equation Systems
Afilliation, Communication Systems
Project(s)Simula UiB
Publication TypeProceedings, refereed
Year of Publication2007
Conference Name14th International Workshop on Selected Areas in Cryptography, SAC 2007
Date Published08/2007
PublisherLecture Notes in Computer Science, Springer Verlag
ISBN Number978-3-540-77359-7
ISSN Number0302-9743
Keywordsalgebraic attacks, Cryptanalysis, DES, non-linear equation systems

We show how to represent a non-linear equation over GF(2) using linear systems with multiple right hand sides. We argue that this representation is particularly useful for constructing equation systems describing ciphers using an S-box as the only means for non-linearity. Several techniques for solving systems of such equations were proposed in earlier work, and are also explained here. Results from experiments with DES are reported. Finally we use our representation to link a particular problem concerning vector spaces to the security of ciphers with S-boxes as the only non-linear operation.

Citation Key24081

Contact person