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.
Author(s): Massimiliano Sala (auth.), Massimiliano Sala, Shojiro Sakata, Teo Mora, Carlo Traverso, Ludovic Perret (eds.)
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2009
Language: English
Pages: 430
City: Berlin :, [S.l.]
Tags: Algebra; Combinatorics; Data Encryption; Mathematics of Computing; Theory of Computation
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
