Gröbner Bases, Coding, and Cryptography

Coding theory and cryptography allow secure and reliable data transmission, which is at the heart of modern communication. Nowadays, it is hard to find an electronic device without some code inside. Gröbner bases have emerged as the main tool in computational algebra, permitting numerous applications, both in theoretical contexts and in practical situations.

This book is the first book ever giving a comprehensive overview on the application of commutative algebra to coding theory and cryptography. For example, all important properties of algebraic/geometric coding systems (including encoding, construction, decoding, list decoding) are individually analysed, reporting all significant approaches appeared in the literature. Also, stream ciphers, PK cryptography, symmetric cryptography and Polly Cracker systems deserve each a separate chapter, where all the relevant literature is reported and compared. While many short notes hint at new exciting directions, the reader will find that all chapters fit nicely within a unified notation.

Part I: Invited Talks 1 Teo Mora: Groebner technology, 2 Teo Mora: The FGLM problem and Moeller's algorithm on zero-dimensional ideals, 3 Daniel Augot, Emanuele Betti, Emmanuela Orsini: An introduction to linear and cyclic codes, 4 Teo Mora, Emmanuela Orsini: Decoding cyclic codes: the Cooper philosophy, 5 Douglas A. Leonard: A tutorial on AG code construction from a Groebner basis perspective, 6 John Little: Automorphisms and encoding of AG and order domain codes, 7 Olav Geil: Algebraic geometry codes from order domains, 8 Shojiro Sakata: The BMS algorithm, 9 Shojiro Sakata: The BMS Algorithm and decoding of algebraic geometry codes, 10 Douglas A. Leonard: A tutorial on AG code decoding from a Groebner basis perspective, 11 Eleonora Guerrini,Anna Rimoldi: FGLM-like decoding: from Fitzpatrick's approach to recent developments, 12 Marcus Greferath: An introduction to ring-linear coding theory, 13 Eimear Byrne, Teo Mora: Groebner bases over commutative Artin chain rings and applications to coding theory, 14 Olivier Billet and Jintai Ding: Overview of cryptanalysis techniques in multivariate public key cryptography 15 Francoise Levy-dit-Vehel, Maria Grazia Marinari, Ludovic Perret, Carlo Traverso: A survey on Polly-Cracker systems, 16 Carlos Cid, Ralf Weinmann: Block ciphers: algebraic cryptanalysis and Groebner bases, 17 Frederik Armknecht, Gwenole Ars: Algebraic attacks on stream ciphers with Groebner bases, Part II: Notes 1 Kristine Lally: Canonical representation of quasicyclic codes using Gröbner basis theory, 2 Marta Giorgetti: About the nth-root codes, 3 Stanislav Bulygin, Ruud Pellikaan: Decoding linear error-correcting codes up to half the minimum distance withGroebner bases, 4 Eleonora Guerrini, Emmanuela Orsini, Ilaria Simonetti: Gröbner bases for the distance distribution of systematic codes, 5 Jon-Lark Kim: A Prize Problem in Coding Theory, 6 Mijail Borges-Quintana, Miguel A. Borges-Trenard, Edgar Martinez-Moro: An application of Moeller's Algorithm to Coding Theory, 7 Edgar Martinez-Moro, Diego Ruano: Mattson Solomon transform and algebra codes, 8 Peter Beelen, Kristian Brander: Decoding folded Reed-Solomon codes using Hensel lifting, 9 Daniel Augot, Michael Stepanov: A note on the generalisation of the Guruswami-Sudan list decoding 10 Gretchen L. Matthews: Viewing multipoint codes as subcodes of one-point codes 11 Heide Gluesing-Luerssen, Barbara Langfeld, Wiland Schmale: A short introduction to cyclic convolutional codes, 12 Ilaria Simonetti: On the non-linearity of Boolean functions 13 Danilo Gligoroski, Vesna Dimitrova, Smile Markovski: Quasigroups as Boolean functions, their equation systems and Groebner bases 14 Danilo Gligoroski, Smile Markovski, Svein J. Knapskog: A new measure to estimate pseudo-randomness of Boolean functions and relations with Gröbner bases 15 Ryutaroh Matsumoto: Radical computation for small characteristics