Algebraic cryptanalysis is a well-titled book. The theme is the reduction of attacks on ciphers (cryptosystems) to systems of polynomial equations over finite fields and subsequent heuristics for efficiently solving these systems. The book is written from the standpoint of real-world computational algebra, and contains numerous gems concerning details on how various algorithms and the heuristics using them really work. The book has an overall tripartite structure. Part 1 is a discussion about cryptanalysis, and introduces the equational approach. There is a brief section on permutation statistics. The reader might benefit from consulting another book [1] for more on generating functions. Part 2 goes into great detail on linear equation systems over GF(2). Part 3 treats general polynomial equation systems, with special emphasis on the quadratic case.

Parts 2 and 3 comprise many very short subsections, which is a little distracting to the reader. However, this seems unavoidable given the level of detail provided, including experimental findings. It should be said that the table of contents is well designed and highly descriptive of each subsection’s content. Given the fragmentary nature of its style, a conventional thematic review of the book is out of place. In the spirit of the book’s structure, I will present some of the highlights from Parts 2 and 3.

Part 2 contains a careful examination of problems in using Strassen’s matrix inversion method over finite fields. This includes a full treatment of interreducibility between inversion and matrix multiplication and the associated complexity analysis. This material could be quite valuable in a second course on complexity of arithmetic. Another highlight in this part is the proof of the Baur-Strassen theorem. This theorem, given a rational function f over a field (any field), establishes a linear overhead in terms of basic field operations of the computation of all partial derivatives of f. Also of note is the algorithmic analysis of the four Russians method and its use in connection with Strassen matrix inversion. This is also valuable in a second course on the complexity of arithmetic. Finally, the detailed matrix calculation implementation of the quadratic sieve for factoring RSA moduli is well done.

Part 3 describes the universal mapping theorem. Every mapping between finite sets can be expressed as a polynomial mapping over GF(p) for any p. This result is first obtained for finite field mappings. Another highlight is the interesting discussion from a complexity theory standpoint of size measures for systems of polynomial equations. This is especially useful in connection with MQ, the solution of quadratic polynomial equation systems over finite fields. Also of interest in this part is the application of linearization of polynomial equation systems via Gröbner bases. It is well known that these systems over any field can be reduced to the polynomial ideal membership problem and that the Gröbner basis approach generally works well in practice, provided the number of variables is not too large relative to computational power. In Section 12.2.1, the author points out an important fact on this point. The last group of sections deals with the reduction of polynomial equation systems MQ over GF(2) (mainly) to SAT. The running time analysis of experiments is carried out by attempting to fit results to a log-normal distribution, in order to see whether the logarithm of running times obeys the normal distribution.

The treatments in Parts 2 and 3 are extensive and detailed, but not exhaustive. There is another approach to polynomial equation systems, especially over GF(p) for small p (p = 2) that warrants comparisons with the approaches of this book, namely Tarski algebra. This might make a fruitful doctoral topic.