Hugendubel.info - Die B2B Online-Buchhandlung 

Merkliste
Die Merkliste ist leer.
Bitte warten - die Druckansicht der Seite wird vorbereitet.
Der Druckdialog öffnet sich, sobald die Seite vollständig geladen wurde.
Sollte die Druckvorschau unvollständig sein, bitte schliessen und "Erneut drucken" wählen.

Gröbner Bases, Coding, and Cryptography

E-BookPDF1 - PDF WatermarkE-Book
430 Seiten
Englisch
Springer Berlin Heidelbergerschienen am28.05.20092009
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.mehr
Verfügbare Formate
BuchGebunden
EUR106,99
E-BookPDF1 - PDF WatermarkE-Book
EUR96,29

Produkt

KlappentextCoding 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.
Details
Weitere ISBN/GTIN9783540938064
ProduktartE-Book
EinbandartE-Book
FormatPDF
Format Hinweis1 - PDF Watermark
FormatE107
Erscheinungsjahr2009
Erscheinungsdatum28.05.2009
Auflage2009
Seiten430 Seiten
SpracheEnglisch
IllustrationenXVI, 430 p.
Artikel-Nr.1442057
Rubriken
Genre9200

Inhalt/Kritik

Inhaltsverzeichnis
1;Preface;5
2;Contents;6
3;Gröbner Bases, Coding, and Cryptography: a Guide to the State-of-Art;16
3.1;In the Beginning;16
3.2;Until Now;17
3.2.1;Classical Coding Theory;18
3.2.2;AG Codes;19
3.2.3;Coding Miscellanea;19
3.2.4;Cryptography;20
3.3;Final Comments;21
3.4;References;21
4;Invited Papers;24
4.1;Gröbner Technology;25
4.1.1;Notation and Definitions;25
4.1.2;Term-Orderings: Classification and Representation;30
4.1.3;Buchberger's Theorem and Algorithm;33
4.1.3.1;Acknowledgements;38
4.1.4;References;38
4.2;The FGLM Problem and Möller's Algorithm on Zero-dimensional Ideals;40
4.2.1;Duality;40
4.2.2;Möller's Algorithm;41
4.2.3;The FGLM Problem;46
4.2.4;The FGLM Matrix;46
4.2.5;Pointers;48
4.2.6;Point Evaluation;51
4.2.6.1;Möller's Algorithm;51
4.2.6.2;Cerlienco-Mureddu Correspondence;51
4.2.6.3;Farr-Gao Analysis;52
4.2.6.4;Points with Multiplicities;55
4.2.7;References;56
4.3;An Introduction to Linear and Cyclic Codes;59
4.3.1;An Overview on Error Correcting Codes;59
4.3.2;Linear Codes;60
4.3.2.1;Basic Definitions;60
4.3.2.2;Hamming Distance;61
4.3.2.3;Decoding Linear Codes;64
4.3.3;Some Bounds on Codes;66
4.3.4;Cyclic Codes;67
4.3.4.1;An Algebraic Correspondence;67
4.3.4.2;Encoding and Decoding with Cyclic Codes;68
4.3.4.3;Zeros of Cyclic Codes;69
4.3.5;Some Examples of Cyclic Codes;70
4.3.5.1; Hamming and Simplex Codes;70
4.3.5.2;Quadratic Residue Codes;72
4.3.6;BCH Codes;72
4.3.6.1;On the Optimality of BCH Codes;73
4.3.7;Decoding BCH Codes;74
4.3.7.1;The First Step: the Key Equation;75
4.3.7.2;The Second Step: the Extended Euclidean Algorithm;76
4.3.7.3;The Third Step: Determining the Error Values;78
4.3.8;On the Asymptotic Properties of Cyclic Codes;78
4.3.8.1;Acknowledgements;79
4.3.9;References;79
4.4;Decoding Cyclic Codes: the Cooper Philosophy;81
4.4.1;Introduction;81
4.4.2;Decoding Binary BCH Codes;83
4.4.3;Gröbner Bases for Cyclic Codes;86
4.4.3.1;Decoding Binary Cyclic Codes;86
4.4.3.2;Decoding Cyclic Codes over Fq;87
4.4.3.3;A New System with the Newton Identities;88
4.4.4;The CRHT Syndrome Variety;89
4.4.5;The Gianni-Kalkbrener Shape Theorem;90
4.4.6;The General Error Locator Polynomial;97
4.4.7;A Newton-Based Decoder;100
4.4.7.1;Acknowledgements;102
4.4.8;References;102
4.5;A Tutorial on AG Code Construction from a Gröbner Basis Perspective;104
4.5.1;Introduction;104
4.5.2;Traditional AG Approach;106
4.5.3;Weighted Total-Degree Orders;108
4.5.4;Hermitian Codes and Affine-Variety Codes;108
4.5.5;Curve Definition;110
4.5.5.1;Acknowledgements;117
4.5.6;References;117
4.6;Automorphisms and Encoding of AG and Order Domain Codes;118
4.6.1;Introduction;118
4.6.2;Other Encoding Methods for AG Goppa Codes;119
4.6.3;Automorphisms and Module Structures;120
4.6.4;A Systematic Encoding Algorithm;121
4.6.5;Complexity Comparisons;123
4.6.6;Automorphisms of Curves and AG Goppa Codes;123
4.6.7;Examples;125
4.6.7.1;Acknowledgements;130
4.6.8;References;130
4.7;Algebraic Geometry Codes from Order Domains;132
4.7.1;Introduction;132
4.7.2;Order Domains with Weight Functions;133
4.7.3;Codes from Order Domains;136
4.7.4;One-Point Geometric Goppa Codes;143
4.7.5;Gröbner Basis Theoretical Tools for the Construction of Order Domains;144
4.7.6;Gröbner Basis Theoretical Tools for the Code Construction;148
4.7.7;The Connection to Valuation Theory;151
4.7.7.1;Acknowledgements;151
4.7.8;References;151
4.8;The BMS Algorithm;153
4.8.1;Introduction;153
4.8.2;Generating Arrays;156
4.8.3;BMS Algorithm;158
4.8.4;Variations;164
4.8.4.1;Multiarray BMS Algorithm;167
4.8.4.2;Vectorial BMS Algorithm;168
4.8.4.3;Non-Homogeneous BMS Algorithm;170
4.8.4.4;Submodule BMS Algorithm;170
4.8.4.5;Semigroup BMS Algorithm;171
4.8.5;Conclusion;171
4.8.5.1;Acknowledgements;171
4.8.6;Appendix A: Computation of BMS Algorithm;171
4.8.6.1;Example of Computation;171
4.8.7;References;173
4.9;The BMS Algorithm and Decoding of AG Codes;174
4.9.1;Introduction;175
4.9.2;Syndrome Decoding of Dual Codes;177
4.9.3;Multivariate Polynomial Interpolation and List Decoding of Primal Codes;182
4.9.4;Other Relevant Decoding Methods of Primal/Dual Codes;188
4.9.5;Conclusion;191
4.9.5.1;Acknowledgements;192
4.9.6;References;192
4.10;A Tutorial on AG Code Decoding from a Gröbner Basis Perspective;195
4.10.1; Introduction;195
4.10.2;Functional Decoding of RS Codes and AG Codes Using Syndromes and Error-Locator Ideals;195
4.10.3;Interpolation to Do List Decoding for RS Codes and AG Codes;200
4.10.3.1;Acknowledgements;203
4.10.4;References;203
4.11;FGLM-Like Decoding: from Fitzpatrick's Approach to Recent Developments;205
4.11.1;Introduction;205
4.11.2;Iterative Computation of Gröbner Basis;206
4.11.3;The Key Equation for Alternant Codes;209
4.11.4;Variations;210
4.11.5;Some Applications to AG Codes;211
4.11.6;Errors and Erasures for Alternant Codes;212
4.11.6.1;Errors and Erasures;212
4.11.6.2;Solutions Using Gröbner Bases;213
4.11.7;List Decoding Problem;215
4.11.7.1;Sudan's Approach;216
4.11.7.2;Improvements on the Interpolation Steps for the RS Codes;218
4.11.7.3;Method in Sect. 2 Applied to List Decoding for AG Codes;220
4.11.7.4;Hard-Decision List Decoding and List Decoding with Soft Information;222
4.11.8;Conclusions;224
4.11.8.1;Acknowledgements;224
4.11.9;References;224
4.12;An Introduction to Ring-Linear Coding Theory;227
4.12.1;Introduction and History;227
4.12.2;Rings and Modules;229
4.12.2.1;Some Classes of Rings;229
4.12.3;Weight Functions on Finite Rings and Modules;231
4.12.4;Linear and Cyclic Codes;232
4.12.4.1;Cyclic Linear Codes;233
4.12.5;A Foundational Result: Code Equivalence;233
4.12.6;Weight Enumerators and MacWilliams' Identity;235
4.12.7;Code Optimality: Bounds on the Parameters of Codes;238
4.12.8;Outlook: the Future of Ring-Linear Coding;241
4.12.9;Addendum: the Non-commutative Case;242
4.12.9.1;Rings and modules:;242
4.12.9.2;Weight functions:;243
4.12.9.3;Linear and cyclic codes:;243
4.12.9.4;Foundational results:;244
4.12.9.5;Existence bounds:;244
4.12.10;References;244
4.13;Gröbner Bases over Commutative Rings and Applications to Coding Theory;247
4.13.1;Introduction;247
4.13.2;Gröbner Basis over Commutative Rings: the Lost Lore;248
4.13.2.1;Notation;248
4.13.2.2;Zacharias Rings;252
4.13.2.3;Möller: Gröbner Basis over a Principal Ideal Ring;253
4.13.2.4;Spear's Theorem;255
4.13.2.5;Szekeres Ideals;255
4.13.3;Finite Chain Rings;256
4.13.4;Solving a Key Equation;257
4.13.5;Alternant Codes;260
4.13.5.1;Unique Decoding C for the Hamming Distance;261
4.13.5.2;Unique Decoding of C for the Lee Distance;263
4.13.5.3;List Decoding of C for the Hamming Distance;264
4.13.6;References;266
4.14;Overview of Cryptanalysis Techniques in Multivariate Public Key Cryptography;270
4.14.1;Introduction;270
4.14.2;Inversion Attacks;271
4.14.2.1;Matsumoto-Imai Scheme A and Its Variations;272
4.14.2.2;Direct Inversion Attacks;274
4.14.2.3;MinRank;276
4.14.2.4;Unbalanced Oil and Vinegar;279
4.14.2.5;Defense Mechanisms;280
4.14.2.5.1;Removing Equations;280
4.14.2.5.2;Perturbations;281
4.14.3;Structural Attacks;281
4.14.3.1;Isomorphism of Polynomials;282
4.14.3.2;Two Rounds;284
4.14.4;Discussion;286
4.14.4.1;Acknowledgements;287
4.14.5;References;287
4.15;A Survey on Polly Cracker Systems;291
4.15.1;Introduction;291
4.15.2;The Seminal Paper;293
4.15.2.1;Barkee's Cryptosystem;293
4.15.2.2;The Fantomas Attack;294
4.15.2.3;The Moriarty Attack;294
4.15.2.4;Bulygin's Attack;295
4.15.2.4.1;Rai-Bulygin: Protecting Barkee's Scheme Against Bulygin's Attack;295
4.15.3;CA-Style Cryptosystems;296
4.15.3.1;Generic Design;296
4.15.3.1.1;Effective Proposals and Basic Attacks;296
4.15.3.2;Graph 3-Coloring;297
4.15.3.3;Graph Perfect Code;297
4.15.3.4;Intelligent Linear Algebra Attack;298
4.15.3.5;EnRoot;298
4.15.3.6;0-Evaluation Attack;299
4.15.3.7;3-SAT;300
4.15.4;Further Attacks;301
4.15.4.1;Basic CCA (Steinwandt and Geiselmann 2002);301
4.15.4.2;Differential Attack;302
4.15.4.3;The 2-Nomial Attack;303
4.15.4.4;Further Linear Algebra Attacks;304
4.15.5;Polly-Two;305
4.15.6;Non-commutative Gröbner Cryptosystems? No Thanks!;306
4.15.6.1;Non-commutative Polly Cracker;306
4.15.6.1.1;Factoring Attacks;307
4.15.6.2;Monoid Algebras;307
4.15.6.3;Pritchard's Decryption Algorithm;308
4.15.7;Conclusion;309
4.15.7.1;Acknowledgements;309
4.15.8;References;309
4.16;Block Ciphers: Algebraic Cryptanalysis and Gröbner Bases;312
4.16.1;Introduction;312
4.16.2;Design of Block Ciphers;313
4.16.3;Block Cipher Cryptanalysis;315
4.16.4;Algebraic Cryptanalysis;317
4.16.4.1;Polynomial Descriptions of Block Ciphers;318
4.16.4.2;Field Equations;319
4.16.4.3;Polynomial Systems over F2;320
4.16.4.4;Equations for Non-linear Components;320
4.16.4.5;Equations for Inversion over F2n;321
4.16.4.6;Block Cipher Embeddings;321
4.16.4.7;Direct Construction of Gröbner Bases;322
4.16.5;Small Scale and Experimental Ciphers;323
4.16.5.1;Small Scale Variants of the AES;323
4.16.5.2;Flurry and Curry;324
4.16.5.3;Other Examples;325
4.16.6;Experimental Results;325
4.16.6.1;Small Versions of the AES;325
4.16.6.2;Flurry and Curry;326
4.16.6.3;Other Experiments;327
4.16.7;Attack Strategies;327
4.16.7.1;Meet-in-the-Middle and Incremental Techniques;327
4.16.7.2;Differential-Algebraic Cryptanalysis;328
4.16.8;Alternative Methods for Solving Polynomial Systems;329
4.16.9;Conclusions;330
4.16.9.1;Acknowledgements;330
4.16.10;References;330
4.17;Algebraic Attacks on Stream Ciphers with Gröbner Bases;333
4.17.1;Introduction;333
4.17.2;Keystream Generators;334
4.17.3;Algebraic Attacks;337
4.17.4;Finding Equations;340
4.17.4.1;Simple Combiners;340
4.17.4.2;Combiners with Memory;343
4.17.4.3;Considering Several Equations Simultaneously;345
4.17.4.3.1;Reducing the Degree;346
4.17.4.3.2;Reducing the Number of Variables;346
4.17.5;Computing Solutions;347
4.17.5.1;Minimum Number of Outputs;348
4.17.5.2;Time Effort;349
4.17.6;Conclusions;350
4.17.6.1;Acknowledgements;351
4.17.7;References;351
5;Notes;353
5.1;Canonical Representation of Quasicyclic Codes Using Gröbner Bases Theory;354
5.1.1;Introduction;354
5.1.2;Characterisation Using Gröbner Bases Theory;355
5.1.3;Parity Check Matrix and Dual Code;357
5.1.4;Recent Application to QC LDPC Codes;357
5.1.5;References;358
5.2;About the nth-Root Codes: a Gröbner Basis Approach to the Weight Computation;359
5.2.1;General nth-Root Codes;359
5.2.1.1;Computing Distance and Weight Distribution for an nth-Root Code;360
5.2.2;Conclusions and Further Research;362
5.2.2.1;Acknowledgements;362
5.2.3;References;362
5.3;Decoding Linear Error-Correcting Codes up to Half the Minimum Distance with Gröbner Bases;363
5.3.1;Introduction;363
5.3.2;Matrix in MDS Form;363
5.3.3;Decoding up to Half the Minimum Distance;364
5.3.4;Conclusion and Future Work;366
5.3.4.1;Acknowledgements;366
5.3.5;References;366
5.4;Gröbner Bases for the Distance Distribution of Systematic Codes;368
5.4.1;Preliminaries;368
5.4.2;Theoretical Results;369
5.4.3;Numerical Computations;371
5.4.3.1;Acknowledgements;372
5.4.4;References;372
5.5;A Prize Problem in Coding Theory;374
5.5.1;Introduction;374
5.5.2;Related Facts about a Putative Type II [72,36,16] Code;375
5.5.3;Future Work;376
5.5.4;Monetary Prizes;377
5.5.4.1;Acknowledgements;377
5.5.5;References;377
5.6;An Application of Möller's Algorithm to Coding Theory;379
5.6.1;Introduction;379
5.6.2;An Ideal Associated with a Linear Code;379
5.6.2.1;A Second Way of Getting the Data for I;380
5.6.3;Examples;381
5.6.3.1;Working out with a Gröbner Representation;381
5.6.3.2;Combinatorial Properties of a Binary Code;382
5.6.3.3;Example: the Golay Code;383
5.6.3.4;GAP Computing Section;383
5.6.3.4.1;Acknowledgement;384
5.6.4;References;384
5.7;Mattson Solomon Transform and Algebra Codes;385
5.7.1;Introduction;385
5.7.2;Mattson-Solomon Transform;386
5.7.3;Generator Theory;386
5.7.4;A Note on the Syndrome Variety;388
5.7.4.1;Acknowledgement;388
5.7.5;References;388
5.8;Decoding Folded Reed-Solomon Codes Using Hensel-Lifting;389
5.8.1;Introduction;389
5.8.2;Folded Reed-Solomon Codes;390
5.8.3;Decoding of Folded Reed-Solomon Codes;390
5.8.4;References;393
5.9;A Note on the Generalisation of the Guruswami-Sudan List Decoding Algorithm to Reed-Muller Codes;395
5.9.1;Definitions and Notation;395
5.9.2;The Algorithm;396
5.9.3;The Analysis;396
5.9.3.1;Acknowledgement;397
5.9.4;References;397
5.10;Viewing Multipoint Codes as Subcodes of One-Point Codes;399
5.10.1;Introduction;399
5.10.2;Embedding a Multipoint Code in a One-Point Code;400
5.10.3;Examples;400
5.10.4;Conclusion;402
5.10.4.1;Acknowledgements;402
5.10.5;References;402
5.11;A Short Introduction to Cyclic Convolutional Codes;403
5.11.1;Introduction and Preliminaries;403
5.11.2;How to Define Cyclic Convolutional Codes?;404
5.11.3;Analyzing Cyclic CC's with Gröbner-type Theory;406
5.11.3.1;Acknowledgement;407
5.11.4;References;407
5.12;On the Non-linearity of Boolean Functions;409
5.12.1;Introduction;409
5.12.2;Preliminaries and Notation;409
5.12.3;Computing the Non-linearity;411
5.12.3.1;Acknowledgements;412
5.12.4;References;413
5.13;Quasigroups as Boolean Functions, Their Equation Systems and Gröbner Bases;414
5.13.1;Introduction;414
5.13.2;Quasigroups as Vector Valued Boolean Functions;415
5.13.2.1;Lexicographic Ordering of Finite Quasigroups;415
5.13.2.2;Vector Valued Boolean Functions ;415
5.13.2.3;Classification of Quasigroups;416
5.13.3;Systems of Quasigroup Equations and Gröbner Bases;417
5.13.3.1;Acknowledgement;418
5.13.4;References;419
5.14;A New Measure to Estimate Pseudo-Randomness of Boolean Functions and Relations with Gröbner Bases;420
5.14.1;Introduction;420
5.14.2;Normalized Average Number of Terms-NANT;421
5.14.3;NANT and SHA-Family of Hash Functions;422
5.14.3.1;Acknowledgement;424
5.14.4;References;424
5.15;Radical Computation for Small Characteristics;425
5.15.1;Introduction;425
5.15.2;Another Radical Computation Method for Positive Characteristic;426
5.15.3;Comparison of Computational Time and Discussion;426
5.15.3.1;Acknowledgements;428
5.15.4;References;428mehr

Autor