Details:
Title  Polynomial system solving for decoding linear codes and algebraic cryptanalysis  Author(s)  Stanislav Bulygin  Type  PhD Theses  Abstract  This thesis is devoted to applying symbolic methods to the problems of decoding linear codes and of algebraic cryptanalysis. The paradigm we employ here is as follows. We reformulate the initial problem in terms of systems of polynomial equations over a finite field. The solution(s) of such systems should yield a way to solve the initial problem. Our main tools for handling polynomials and polynomial systems in such a paradigm is the technique of Gröbner bases and normal form reductions.
The first part of the thesis is devoted to formulating and solving specific
polynomial systems that reduce the problem of decoding linear codes to the problem of polynomial system solving. We analyze the existing methods (mainly for the cyclic codes) and propose an original method for arbitrary linear codes that in some sense generalizes the Newton identities method widely known for cyclic codes. We investigate the structure of the underlying ideals and show how one can solve the decoding problem  both the socalled bounded decoding and more general nearest codeword decoding  by finding reduced Gröbner bases of these ideals. The main feature of the method is that unlike usual methods based on Gröbner bases for "finite field" situations, we do not add the socalled field equations. This tremendously simplifies the underlying ideals, thus making feasible working with quite large parameters of codes. Further we address complexity issues, by giving some insight to the Macaulay matrix of the underlying systems. By making a series of assumptions we are able to provide an upper bound for the complexity coefficient of our method. We address also finding the minimum distance and the weight distribution. We provide solid experimental material and comparisons with some of the existing methods in this area.
In the second part we deal with the algebraic cryptanalysis of block iterative ciphers. Namely, we analyze the smallscale variants of the Advanced Encryption Standard (AES), which is a widely used modern block cipher. Here a cryptanalyst composes the polynomial systems which solutions should yield a secret key used by communicating parties in a symmetric cryptosystem. We analyze the systems formulated by researchers for the algebraic cryptanalysis, and identify the problem that conventional systems have many auxiliary variables that are not actually needed for the key recovery. Moreover, having many such auxiliary variables, specific to a given plaintext/ciphertext pair, complicates the use of several pairs which is common in cryptanalysis. We thus provide a new system where the auxiliary variables are eliminated via normal form reductions. The resulting system in keyvariables only is then solved. We present experimental evidence that such an approach is quite good for small scaled ciphers. We investigate further our approach and employ the socalled meetinthemiddle principle to see how far one can go in analyzing just
23 rounds of scaled ciphers. Additional "tuning techniques" are discussed together with experimental material. Overall, we believe that the
material of this part of the thesis makes a step further in algebraic cryptanalysis of block ciphers.  Keywords  Kanalcodierung , GröbnerBasis , Kryptoanalyse , Singular <Programm> , Advanced Encryption Standard  Length  154 
URL 
http://kluedo.ub.unikl.de/volltexte/2009/2350/ 
Language  English  Year  2009  Month  June  Translation 
No  Refereed 
No  Institution 
Department of Mathematics, Technische Universitat Kaiserslautern 
