AuthorsT. E. Schilling and H. Raddum
TitleSolving Compressed Right Hand Side Equation Systems with Linear Absorption
Afilliation, Communication Systems
Project(s)Simula UiB
Publication TypeProceedings, refereed
Year of Publication2012
Conference Name7th International Conference on Sequences and Their Applications, SETA 2012
Date Published06/2012
PublisherLecture Notes in Computer Science, Springer Verlag
ISBN Number978-3-642-30614-3
ISSN Number0302-9743
Keywordsalgebraic cryptanalysis, BDD, multivariate equation system, Trivium

In this paper we describe an approach for solving complex multivariate equation systems related to algebraic cryptanalysis. The work uses the newly introduced Compressed Right Hand Sides (CRHS) representation, where equations are represented using Binary Decision Diagrams (BDD). The paper introduces a new technique for manipulating a BDD, similar to swapping variables in the well-known sifting-method. Using this technique we develop a new solving method for CRHS equation systems. The new algorithm is successfully tested on systems representing reduced variants of Trivium.

Citation Key24094

Contact person