Prof dr ir H C A van Tilborg 2004

Abstract:  Recently, a special kind of cryptanalysis coined as the algebraic attack has gained a lot of attention. In this thesis, we clarify this attack and discuss the threat to common ciphers. Among the known attacks, one can roughly distinguish between two classes. The first consists of structural attacks that focus on specific properties of a certain cipher. The second includes inversion attacks, which are general purpose algorithms that solve multivariate systems of equations. In this thesis we focus on the latter. The different methods appear to be reducible to Gr?bner Basis techniques, an area of algebraic geometry that is understood reasonably well. This report focusses on three topics. Firstly, we introduce a variety of common ciphers and discuss advanced techniques based on Gr?bner Bases to cryptanalyze these ciphers. These are implemented in Magma and presented to the reader. Secondly, the much discussed cryptanalytic tool XL is shown to be related to methods based on Gr?bner Bases. And lastly, this report discusses a complexity approximation of XL based on Hilbert series. 3