|Title||MRHS Equation Systems|
|Afilliation||, Communication Systems|
|Publication Type||Proceedings, refereed|
|Year of Publication||2007|
|Conference Name||14th International Workshop on Selected Areas in Cryptography, SAC 2007|
|Publisher||Lecture Notes in Computer Science, Springer Verlag|
|Keywords||algebraic 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.