Gröbner Bases, Coding, and Cryptography

Last century saw a number of landmark scientific contributions, solving long-standing problems and opening the path to entirely new subjects. We are interested in three (here listed in chronological order) of these:

1.

Claude Shannon’s (Bell System Tech. J. 27:379–423, 623–656, 1948),

2.

Claude Shannon’s (Bell System Tech. J. 28:656–715, 1949),

3.

Bruno Buchberger’s (Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal, Ph.D. thesis, Innsbruck, 1965)

This is NOT an introductory survey do Gröbner bases and Buchberger algorithms; for that there are a lot of better available papers, even by me. The only aim of this small note is to harmonize the notation and terminology throughout this book.

Möller’s Algorithm is a procedure which, given a set of linear functionals defining a zero-dimensional polynomial ideal, allows to compute, with good complexity,

a set of polynomials which are triangular/bihortogonal to the given functionals;

at least a “minimal” polynomial which vanishes to all the given functionals;

a Gröbner basis of the given ideal.

As such Möller’s Algorithm has applications

when the functionals are point evaluation (where the only relevant informations are the bihortogonal polynomials);

as an interpretation of Berlekamp–Massey Algorithm (such interpretation is due to Fitzpatrick) where the deduced minimal vanishing polynomial is the key equation;

as an efficient solution of the FGLM-Problem (deduced with good complexity the lex Gröbner basis of a zero-dim. ideal given by another easy-to-be-computed Gröbner basis of the same ideal).

Our purpose is to recall some basic aspects about linear and cyclic codes. We first briefly describe the role of error-correcting codes in communication. To do this we introduce, with examples, the concept of linear codes and their parameters, in particular the Hamming distance.

A fundamental subclass of linear codes is given by cyclic codes, that enjoy a very interesting algebraic structure. In fact, cyclic codes can be viewed as ideals in a residue classes ring of univariate polynomials. BCH codes are the most studied family of cyclic codes, for which some efficient decoding algorithms are known, as the method of Sugiyama.

In 1990 Cooper suggested to use Gröbner basis computations in order to deduce error locator polynomials of cyclic codes.

The aim of this tutorial is to show, with illuminating examples, how Cooper’s approach has been refined up to give both an

online decoder

and

general error locator polynomials

.

This chapter is meant primarily as an introduction to AG codes, with material on producing proper one-point descriptions of these codes as well. The terminology chosen is that of the easily understood concepts of multivariate polynomial rings and ideals of relations among the variables, which is more useful computationally than the more standard algebraic geometry terminology.

We survey some encoding methods for AG codes, focusing primarily on one approach utilizing code automorphisms. If a linear code

C

over

$\mathbb{F}_{q}$

has a finite Abelian group

H

as a group of automorphisms, then

C

has the structure of a module over a polynomial ring ℘. This structure can be used to develop systematic encoding algorithms using Gröbner bases for modules. We illustrate these observations with several examples including geometric Goppa codes and codes from order domains.

In this tutorial we introduce order domains and study the related codes. Special attention is given to the one-point geometric Goppa codes. We show how Gröbner basis theory helps us constructing order domains as well as helps us dealing with the related codes.

We present a sketch of the

n

-dimensional (

n

-D) Berlekamp–Massey algorithm (alias Berlekamp–Massey–Sakata or BMS algorithm) w.r.t.

n

-D arrays. That is: (1) How is it related to Gröbner basis? (2) What problem can it solve? (3) How does it work? (4) Its variations. First we discuss another problem closely related to our main problem, and introduce some concepts about

n

-D linear recurrences and modules of

n

-D arrays as their general solutions. These two problems are just the inverse (or rather dual) to each other, which can be solved by the Buchberger algorithm (Buchberger in Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal, Ph.D. thesis, Innsbruck,

1965

; J. Symb. Comput. 41(3–4):475–511,

2006

; Multidimensional systems theory, Reidel, Dordrecht, pp. 184–232,

1985

; Mora in Gröbner technology, this volume, pp. 11–25,

2009b

), and the BMS algorithm, respectively. Furthermore, we discuss some properties of BMS algorithm and its outputs, including its computational complexity, as well as several variations of the BMS algorithm.

In this paper, we review various decoding methods of algebraic geometry (or algebraic-geometric) codes (Goppa in Soviet Math. Dokl. 24(1):170–172,

1981

; Høholdt et al. in Handbook of coding theory, vols. I, II, North-Holland, Amsterdam, pp. 871–961,

1998

; Geil in Algebraic geometry codes from order domains, this volume, pp. 121–141,

2009

) mainly based on the Gröbner basis theory (Buchberger in Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal, Ph.D. thesis, Innsbruck,

1965

; Aequationes Math. 4:374–383,

1970

; Multidimensional systems theory, Reidel, Dordrecht, pp. 184–232,

1985

; London Math. Soc. LNS 251:535–545,

1998

; J. Symb. Comput. 41(3–4):475–511,

2006

; Mora in Gröbner technology, this volume, pp. 11–25,

2009b

) as well as the BMS algorithm (Sakata in J. Symbolic Comput. 5(3):321–337,

1988

; Inform. and Comput. 84(2):207–239,

1990

) and its variations (Sakata in

n

-dimensional Berlekamp–Massey algorithm for multiple arrays and construction of multivariate polynomials with preassigned zeros, LNCS, vol. 357, pp. 356–376,

1989

; Finding a minimal polynomial vector set of a vector of

n

D arrays, LNCS, vol. 539, pp. 414–425,

1991

), where the BMS algorithm itself is reviewed in another paper (Sakata in The BMS algorithm, this volume, pp. 143–163,

2009

) in this issue. The main subjects are:

(1) Syndrome decoding of dual codes up to the designed distance (Saints and Heegard in IEEE Trans. Inform. Theory 41(6):1733–1751,

1995

; Sakata et al. in Finite Fields Appl. 1(1):83–101,

1995b

; IEEE Trans. on Inf. Th. 41(6):1672–1677,

1995c

; IEEE Trans. on Inf. Th. 41(6):1762–1768,

1995a

) by using the BMS algorithm. (There have been published several methods of decoding algebraic geometry codes, e.g. Kötter in On decoding of algebraic-geometric and cyclic codes, Ph.D. thesis, Linköping University,

1996

; O’Sullivan in IEEE Trans. on Inf. Th. 41(6):1709–1719,

1995

; Guerrini and Rimoldi in FGLM-like decoding: from Fitzpatrick’s approach to recent developments, this volume, pp. 197–218,

2009

, which are described in some terminology rather from the perspective of algebraic geometry, but are in principle equivalent to the BMS decoding method. We omit their descriptions here.)

(2) List decoding of primal codes (Numakami et al. in IEICE Trans. Fundamentals J83:1309–1317,

2000

; Sakata in LNCS, vol. 2227, pp. 172–181,

2001

; Proc. of ISIT2003, pp. 363–363,

2003

). (The original list decoding algorithms are given for RS codes by Sudan in J. of Complexity 13:180–193,

1997

, and for algebraic geometry codes by Shokrollahi and Wassermann in IEEE Trans. on Inf. Th. 45(2):432–437,

1999

, and their improved versions by Guruswami and Sudan in IEEE Trans. on Inf. Th. 45:(6):1757–1767,

1999

.)

(3) Other relevant decoding algorithms of primal and dual codes (Augot in Proc. of ISIT2002, pp. 86–86,

2002

; Justesen and Høholdt in A course in error-correcting codes, EMS Textbooks in Mathematics, EMS,

2004

; Fujisawa and Sakata in Proc. of SITA2005, pp. 543–546,

2005

; Sakata and Fujisawa in Proc. of SITA2006, pp. 93–96,

2006

; Fujisawa et al. in Proc. of SITA2006, pp. 101–104,

2006

).

In discussing list decoding and usual bounded-distance decoding of primal/dual codes we show that multi-variate interpolation problem is a key and that it can be solved by using the BMS algorithm efficiently. The computational complexities of our methods are less than the other decoding methods including the Feng–Rao (IEEE Trans. on Inf. Th. 39(1):37–45,

1993

) algorithm simply based on Gaussian elimination. These reductions in computational complexity are based on the special structures or properties of the given input data (syndrome arrays, etc.) which originate in the definition of codes themselves and are used cleverly by the BMS algorithm. In Leonard (A tutorial on AG code decoding from a Gröbner basis perspective, this volume, pp. 187–196,

2009b

), Guerrini and Rimoldi (FGLM-like decoding: from Fitzpatrick’s approach to recent developments, this volume, pp. 197–218,

2009

) in this issue, several other efficient decoding methods of algebraic geometry codes from Gröbner basis perspectives are reviewed. Additionally, we mention a recent development of decoding algorithm based on higher-dimensional interpolation (Parvaresh and Vardy in Proc. of IEEE FOCS2005, IEEE Computer Society, pp. 285–294,

2005

), which has error correction performance superior to the improved list decoding by Guruswami and Sudan. As a general method of multivariate interpolation the BMS algorithm is an alternative of the Buchberger–Möller (The construction of multivariate polynomials with preassigned zeros, LNCS, vol. 144, pp. 24–31,

1982

), Mora (The FGLM problem and Möller’s algorithm on zero-dimensional ideals, this volume, pp. 27–45,

2009a

) algorithm and the Marinani–Möller–Mora (AAECC 4:(2):103–145,

1993

) algorithm, but any exact comparisons of computational complexities of these methods remain to be investigated.

This chapter presents material about syndrome decoding and list decoding of AG codes. The syndrome decoding of AG codes is viewed in terms of Sakata’s generalization of the Berlekamp–Massey algorithm and Feng and Rao’s majority voting scheme. Their list-decoding is viewed following Sudan’s ideas and some variations.

Many decoding problems in algebraic coding theory can be solved by the computation of a suitable Gröbner basis. The Gröbner basis can often be computed via the FGLM algorithm or a related algorithm (like the Buchberger–Möller algorithm). In this tutorial we describe how this has been done in the literature from a historical point of view, starting from Fitzpatrick’s seminal 1995 paper, and covering recent developments for list decoding.

This contribution gives an introduction to algebraic coding theory over rings. We will start with a historical sketch and then present basics on rings and modules. Particular attention will be paid to weight functions on these, before some foundational results of ring-linear coding will be discussed. Among these we will deal with code equivalence, and with MacWilliams’ identities about the relation between weight enumerators. A further section is devoted to existence bounds and code optimality. An outlook will then be presented on the still unsolved problem of the construction of large families of ring-linear codes of high quality.

We give a survey of results and applications relating to the theory of Gröbner bases of ideals and modules where the coefficient ring is a finite commutative ring. For applications, we specialize to the case of a finite chain ring. We discuss and compare the main algorithms that may be implemented to compute Gröbner and (in the case of a chain ring) Szekeres-like bases. We give an account of a number of decoding algorithms for alternant codes over commutative finite chain rings.

This paper summarizes most of the main developments in the cryptanalysis of multivariate cryptosystems and discuss some problems that remain open. A strong emphasis is put on the symbolic computation tools that have been used to achieve these advances.

In 1993 Boo Barkee and others have written a paper “

Why you cannot even hope to use Gröbner Bases in Public Key Cryptography

:

an open letter to a scientist who failed and a challenge to those who have not yet failed.

” Since 1994, further attempts have been made, that gave rise to several cryptosystems now known as Polly Cracker systems. None of these proposals have been successful, and while Gröbner Bases are now an established tool for cryptanalysis, the challenge of Boo Barkee still stands w.r.t. the design point of view. We outline a description of how all these attempts have failed.

Block ciphers are one of the most important classes of cryptographic algorithms in current use. Commonly used to provide confidentiality for transmission and storage of information, they encrypt and decrypt blocks of data according to a secret key. Several recently proposed block ciphers (in particular the AES (Daemen and Rijmen in The Design of Rijndael, Springer, Berlin,

2002

)) exhibit a highly algebraic structure: their round transformations are based on simple algebraic operations over a finite field of characteristic 2. This has caused an increasing amount of cryptanalytic attention to be directed to the algebraic properties of these ciphers. Of particular interest is the proposal of the so-called

algebraic attacks

against block ciphers. In these attacks, a cryptanalyst describes the encryption operation as a large set of multivariate polynomial equations, which—once solved—can be used to recover the secret key. Thus the difficulty of solving these systems of equations is directly related to the cipher’s security. As a result computational algebra is becoming an important tool for the cryptanalysis of block ciphers. In this paper we give an overview of block ciphers design and recall some of the work that has been developed in the area of algebraic cryptanalysis. We also consider a few computational and algebraic techniques that could be used in the analysis of block ciphers and discuss possible directions for future work.

Stream ciphers efficiently encrypt data streams of arbitrary length and are widely deployed in practice, e.g., in mobile phones. Consequently, the development of new mechanisms to design and analyze stream ciphers is one of the major topics in modern cryptography. Algebraic attacks evaluate the security of certain stream ciphers by exploring the question how an attack could be performed by generating and solving appropriate systems of equations. In this text, we give an introduction to algebraic attacks and provide an overview on how and to what extent Gröbner bases are useful in this context.

The tools and techniques of Gröbner bases theory have proved useful in characterising quasicyclic codes and analysing their algebraic structure. A canonical generating set can be obtained from the reduced Gröbner basis of an associated module structure. The very particular form of this generating set allows straightforward determination of properties such as dimension, in manner directly analogous to the theory developed for cyclic codes.

Recently some methods have been proposed to find the distance and weight distribution of cyclic codes using Gröbner bases (Sala in Appl. Algebra Engrg. Comm. Comput. 13(2):137–162,

2002

; Mora and Sala in J. Symbolic Comput. 35(2):177–194,

2003

). We identify a class of codes for which these methods can be generalized. We show that this class contains all interesting linear codes (i.e., with

d

≥2) and we provide variants and improvements.

In this short note we show how one can decode linear error-correcting codes up to half the minimum distance via solving a system of polynomial equations over a finite field. We also explicitly present the reduced Gröbner basis for the system considered.

Coding theorists have been studying only linear codes, with a few exceptions (Preparata in Inform. Control 13(13):378–400,

1968

; Baker et al. in IEEE Trans. on Inf. Th. 29(3):342–345,

1983

). This is not surprising, since linear codes have a nice structure, easy to study and leading to efficient implementations. However, it is well-known that some non-linear codes have a higher distance (or a better distance distribution) that any linear code with the same parameters (Preparata in Inform. Control 13(13):378–400,

1968

; Pless et al. (eds.) in Handbook of Coding Theory, vols. I, II, North-Holland, Amsterdam,

1998

). This translates into a superior decoding performance (Litsyn in Handbook of Coding Theory, vols. I, II, North-Holland, Amsterdam, pp. 463–498,

1998

).

Systematic non-linear codes are the most studied non-linear codes. We describe a Gröbner bases technique to compute the distance distribution for these codes.

In this short note, we describe one of the long-standing open problems in algebraic coding theory, i.e., whether there exists a binary self-dual [72,36,16] code.

We show the use of Möller’s Algorithm and related techniques for decoding and studying some combinatorial properties of linear codes. It is a concise summary of our previous results, with emphasis in illustrating the applications and comparing the developed method for computing the Gröbner basis associated with the code with the classical way to solve the same problem.

In this note we review some results of the first author on the structure of codes defined as subalgebras of a commutative semisimple algebra over a finite field (see Martínez-Moro in Algebra Discrete Math. 3:99–112,

2007

). Generator theory and those aspects related to the theory of Gröbner bases are emphasized.

A standard problem in coding theory is to construct good codes together with an efficient decoder. This paper addresses the construction of a class of codes (folded RS codes) for which one can give an efficient and (in a certain sense) optimal decoder, by adapting a list decoding algorithm.

We revisit the generalisation of the Guruswami–Sudan list decoding algorithm to Reed–Muller codes. Although the generalisation is straightforward, the analysis is more difficult than in the Reed–Solomon case. A previous analysis has been done by Pellikaan and Wu (List decoding of

q

-ary Reed–Muller codes, Tech. report, from the authors,

2004a

; IEEE Trans. on Inf. Th. 50(4): 679–682,

2004b

), relying on the theory of Gröbner bases We give a stronger form of the well-known Schwartz–Zippel Lemma (Schwartz in J. Assoc. Comput. Mach. 27(4): 701–717,

1980

; Zippel in Proc. of EUROSAM 1979, LNCS, vol. 72, Springer, Berlin, pp. 216–226,

1979

), taking multiplicities into account. Using this Lemma, we get an improved decoding radius.

We consider ways in which multipoint algebraic geometry codes may be viewed as subcodes of the more traditionally studied one-point codes. Examples are provided to illustrate the impact of choices made on this embedding.

We introduce the notion of cyclic convolutional codes and briefly survey some recent results that were derived with the aid of Gröbner-type theory.

We compute the non-linearity of Boolean functions with Gröbner bases.

In this short note we represent quasigroups of order 2

n

as vector valued Boolean functions

f

:{0,1}

2

n

→{0,1}

n

. The representation of finite quasigroups as vector valued Boolean functions allows us systems of quasigroup equations to be solved by using Gröbner bases.

In this short note we will introduce a generic measure of the algebraic complexity of vector valued Boolean functions: Normalized Average Number of Terms (NANT). NANT can be considered as a tool that extracts those vector valued Boolean functions that are suitable for effective application of Gröbner bases. As an example, we use NANT to show clear differences between two popular cryptographic hash functions: SHA-1 and SHA-2. The obtained results show that SHA-1 is susceptible to attacks based on Gröbner bases, which lead us to believe that SHA-1 is much weaker than SHA-2 from a design point of view.

In applications to coding theory and cryptography, the characteristic of the coefficient field is often small or 2. We will briefly review an algorithm computing the radical of a polynomial ideal specialized for small characteristics.