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. Front Matter....Pages 1-16 Gröbner Bases, Coding, and Cryptography: a Guide to the State-of-Art....Pages 1-8 Front Matter....Pages 9-9 Gröbner Technology....Pages 11-25 The FGLM Problem and Möller’s Algorithm on Zero-dimensional Ideals....Pages 27-45 An Introduction to Linear and Cyclic Codes....Pages 47-68 Decoding Cyclic Codes: the Cooper Philosophy....Pages 69-91 A Tutorial on AG Code Construction from a Gröbner Basis Perspective....Pages 93-106 Automorphisms and Encoding of AG and Order Domain Codes....Pages 107-120 Algebraic Geometry Codes from Order Domains....Pages 121-141 The BMS Algorithm....Pages 143-163 The BMS Algorithm and Decoding of AG Codes....Pages 165-185 A Tutorial on AG Code Decoding from a Gröbner Basis Perspective....Pages 187-196 FGLM-Like Decoding: from Fitzpatrick’s Approach to Recent Developments....Pages 197-218 An Introduction to Ring-Linear Coding Theory....Pages 219-238 Gröbner Bases over Commutative Rings and Applications to Coding Theory....Pages 239-261 Overview of Cryptanalysis Techniques in Multivariate Public Key Cryptography....Pages 263-283 A Survey on Polly Cracker Systems....Pages 285-305 Block Ciphers: Algebraic Cryptanalysis and Gröbner Bases....Pages 307-327 Algebraic Attacks on Stream Ciphers with Gröbner Bases....Pages 329-348 Front Matter....Pages 349-349 Canonical Representation of Quasicyclic Codes Using Gröbner Bases Theory....Pages 351-355 About the n th-Root Codes: a Gröbner Basis Approach to the Weight Computation....Pages 357-360 Front Matter....Pages 349-349 Decoding Linear Error-Correcting Codes up to Half the Minimum Distance with Gröbner Bases....Pages 361-365 Gröbner Bases for the Distance Distribution of Systematic Codes....Pages 367-372 A Prize Problem in Coding Theory....Pages 373-377 An Application of Möller’s Algorithm to Coding Theory....Pages 379-384 Mattson Solomon Transform and Algebra Codes....Pages 385-388 Decoding Folded Reed–Solomon Codes Using Hensel-Lifting....Pages 389-394 A Note on the Generalisation of the Guruswami–Sudan List Decoding Algorithm to Reed–Muller Codes....Pages 395-398 Viewing Multipoint Codes as Subcodes of One-Point Codes....Pages 399-402 A Short Introduction to Cyclic Convolutional Codes....Pages 403-408 On the Non-linearity of Boolean Functions....Pages 409-413 Quasigroups as Boolean Functions, Their Equation Systems and Gröbner Bases....Pages 415-420 A New Measure to Estimate Pseudo-Randomness of Boolean Functions and Relations with Gröbner Bases....Pages 421-425 Radical Computation for Small Characteristics....Pages 427-430 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 [source : 4e de couv.] This text presents 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