Gröbner Bases, Coding, and Cryptography (eBook)

Preface 5
Contents 6
Gröbner Bases, Coding, and Cryptography: a Guide to the State-of-Art 16
In the Beginning 16
Until Now 17
Classical Coding Theory 18
AG Codes 19
Coding Miscellanea 19
Cryptography 20
Final Comments 21
References 21
Invited Papers 24
Gröbner Technology 25
Notation and Definitions 25
Term-Orderings: Classification and Representation 30
Buchberger's Theorem and Algorithm 33
Acknowledgements 38
References 38
The FGLM Problem and Möller's Algorithm on Zero-dimensional Ideals 40
Duality 40
Möller's Algorithm 41
The FGLM Problem 46
The FGLM Matrix 46
Pointers 48
Point Evaluation 51
Möller's Algorithm 51
Cerlienco-Mureddu Correspondence 51
Farr-Gao Analysis 52
Points with Multiplicities 55
References 56
An Introduction to Linear and Cyclic Codes 59
An Overview on Error Correcting Codes 59
Linear Codes 60
Basic Definitions 60
Hamming Distance 61
Decoding Linear Codes 64
Some Bounds on Codes 66
Cyclic Codes 67
An Algebraic Correspondence 67
Encoding and Decoding with Cyclic Codes 68
Zeros of Cyclic Codes 69
Some Examples of Cyclic Codes 70
Hamming and Simplex Codes 70
Quadratic Residue Codes 72
BCH Codes 72
On the Optimality of BCH Codes 73
Decoding BCH Codes 74
The First Step: the Key Equation 75
The Second Step: the Extended Euclidean Algorithm 76
The Third Step: Determining the Error Values 78
On the Asymptotic Properties of Cyclic Codes 78
Acknowledgements 79
References 79
Decoding Cyclic Codes: the Cooper Philosophy 81
Introduction 81
Decoding Binary BCH Codes 83
Gröbner Bases for Cyclic Codes 86
Decoding Binary Cyclic Codes 86
Decoding Cyclic Codes over Fq 87
A New System with the Newton Identities 88
The CRHT Syndrome Variety 89
The Gianni-Kalkbrener Shape Theorem 90
The General Error Locator Polynomial 97
A Newton-Based Decoder 100
Acknowledgements 102
References 102
A Tutorial on AG Code Construction from a Gröbner Basis Perspective 104
Introduction 104
Traditional AG Approach 106
Weighted Total-Degree Orders 108
Hermitian Codes and Affine-Variety Codes 108
Curve Definition 110
Acknowledgements 117
References 117
Automorphisms and Encoding of AG and Order Domain Codes 118
Introduction 118
Other Encoding Methods for AG Goppa Codes 119
Automorphisms and Module Structures 120
A Systematic Encoding Algorithm 121
Complexity Comparisons 123
Automorphisms of Curves and AG Goppa Codes 123
Examples 125
Acknowledgements 130
References 130
Algebraic Geometry Codes from Order Domains 132
Introduction 132
Order Domains with Weight Functions 133
Codes from Order Domains 136
One-Point Geometric Goppa Codes 143
Gröbner Basis Theoretical Tools for the Construction of Order Domains 144
Gröbner Basis Theoretical Tools for the Code Construction 148
The Connection to Valuation Theory 151
Acknowledgements 151
References 151
The BMS Algorithm 153
Introduction 153
Generating Arrays 156
BMS Algorithm 158
Variations 164
Multiarray BMS Algorithm 167
Vectorial BMS Algorithm 168
Non-Homogeneous BMS Algorithm 170
Submodule BMS Algorithm 170
Semigroup BMS Algorithm 171
Conclusion 171
Acknowledgements 171
Appendix A: Computation of BMS Algorithm 171
Example of Computation 171
References 173
The BMS Algorithm and Decoding of AG Codes 174
Introduction 175
Syndrome Decoding of Dual Codes 177
Multivariate Polynomial Interpolation and List Decoding of Primal Codes 182
Other Relevant Decoding Methods of Primal/Dual Codes 188
Conclusion 191
Acknowledgements 192
References 192
A Tutorial on AG Code Decoding from a Gröbner Basis Perspective 195
Introduction 195
Functional Decoding of RS Codes and AG Codes Using Syndromes and Error-Locator Ideals 195
Interpolation to Do List Decoding for RS Codes and AG Codes 200
Acknowledgements 203
References 203
FGLM-Like Decoding: from Fitzpatrick's Approach to Recent Developments 205
Introduction 205
Iterative Computation of Gröbner Basis 206
The Key Equation for Alternant Codes 209
Variations 210
Some Applications to AG Codes 211
Errors and Erasures for Alternant Codes 212
Errors and Erasures 212
Solutions Using Gröbner Bases 213
List Decoding Problem 215
Sudan's Approach 216
Improvements on the Interpolation Steps for the RS Codes 218
Method in Sect. 2 Applied to List Decoding for AG Codes 220
Hard-Decision List Decoding and List Decoding with Soft Information 222
Conclusions 224
Acknowledgements 224
References 224
An Introduction to Ring-Linear Coding Theory 227
Introduction and History 227
Rings and Modules 229
Some Classes of Rings 229
Weight Functions on Finite Rings and Modules 231
Linear and Cyclic Codes 232
Cyclic Linear Codes 233
A Foundational Result: Code Equivalence 233
Weight Enumerators and MacWilliams' Identity 235
Code Optimality: Bounds on the Parameters of Codes 238
Outlook: the Future of Ring-Linear Coding 241
Addendum: the Non-commutative Case 242
Rings and modules: 242
Weight functions: 243
Linear and cyclic codes: 243
Foundational results: 244
Existence bounds: 244
References 244
Gröbner Bases over Commutative Rings and Applications to Coding Theory 247
Introduction 247
Gröbner Basis over Commutative Rings: the Lost Lore 248
Notation 248
Zacharias Rings 252
Möller: Gröbner Basis over a Principal Ideal Ring 253
Spear's Theorem 255
Szekeres Ideals 255
Finite Chain Rings 256
Solving a Key Equation 257
Alternant Codes 260
Unique Decoding C for the Hamming Distance 261
Unique Decoding of C for the Lee Distance 263
List Decoding of C for the Hamming Distance 264
References 266
Overview of Cryptanalysis Techniques in Multivariate Public Key Cryptography 270
Introduction 270
Inversion Attacks 271
Matsumoto-Imai Scheme A and Its Variations 272
Direct Inversion Attacks 274
MinRank 276
Unbalanced Oil and Vinegar 279
Defense Mechanisms 280
Removing Equations 280
Perturbations 281
Structural Attacks 281
Isomorphism of Polynomials 282
Two Rounds 284
Discussion 286
Acknowledgements 287
References 287
A Survey on Polly Cracker Systems 291
Introduction 291
The Seminal Paper 293
Barkee's Cryptosystem 293
The Fantomas Attack 294
The Moriarty Attack 294
Bulygin's Attack 295
Rai-Bulygin: Protecting Barkee's Scheme Against Bulygin's Attack 295
CA-Style Cryptosystems 296
Generic Design 296
Effective Proposals and Basic Attacks 296
Graph 3-Coloring 297
Graph Perfect Code 297
Intelligent Linear Algebra Attack 298
EnRoot 298
0-Evaluation Attack 299
3-SAT 300
Further Attacks 301
Basic CCA (Steinwandt and Geiselmann 2002) 301
Differential Attack 302
The 2-Nomial Attack 303
Further Linear Algebra Attacks 304
Polly-Two 305
Non-commutative Gröbner Cryptosystems? No Thanks! 306
Non-commutative Polly Cracker 306
Factoring Attacks 307
Monoid Algebras 307
Pritchard's Decryption Algorithm 308
Conclusion 309
Acknowledgements 309
References 309
Block Ciphers: Algebraic Cryptanalysis and Gröbner Bases 312
Introduction 312
Design of Block Ciphers 313
Block Cipher Cryptanalysis 315
Algebraic Cryptanalysis 317
Polynomial Descriptions of Block Ciphers 318
Field Equations 319
Polynomial Systems over F2 320
Equations for Non-linear Components 320
Equations for Inversion over F2n 321
Block Cipher Embeddings 321
Direct Construction of Gröbner Bases 322
Small Scale and Experimental Ciphers 323
Small Scale Variants of the AES 323
Flurry and Curry 324
Other Examples 325
Experimental Results 325
Small Versions of the AES 325
Flurry and Curry 326
Other Experiments 327
Attack Strategies 327
Meet-in-the-Middle and Incremental Techniques 327
Differential-Algebraic Cryptanalysis 328
Alternative Methods for Solving Polynomial Systems 329
Conclusions 330
Acknowledgements 330
References 330
Algebraic Attacks on Stream Ciphers with Gröbner Bases 333
Introduction 333
Keystream Generators 334
Algebraic Attacks 337
Finding Equations 340
Simple Combiners 340
Combiners with Memory 343
Considering Several Equations Simultaneously 345
Reducing the Degree 346
Reducing the Number of Variables 346
Computing Solutions 347
Minimum Number of Outputs 348
Time Effort 349
Conclusions 350
Acknowledgements 351
References 351
Notes 353
Canonical Representation of Quasicyclic Codes Using Gröbner Bases Theory 354
Introduction 354
Characterisation Using Gröbner Bases Theory 355
Parity Check Matrix and Dual Code 357
Recent Application to QC LDPC Codes 357
References 358
About the nth-Root Codes: a Gröbner Basis Approach to the Weight Computation 359
General nth-Root Codes 359
Computing Distance and Weight Distribution for an nth-Root Code 360
Conclusions and Further Research 362
Acknowledgements 362
References 362
Decoding Linear Error-Correcting Codes up to Half the Minimum Distance with Gröbner Bases 363
Introduction 363
Matrix in MDS Form 363
Decoding up to Half the Minimum Distance 364
Conclusion and Future Work 366
Acknowledgements 366
References 366
Gröbner Bases for the Distance Distribution of Systematic Codes 368
Preliminaries 368
Theoretical Results 369
Numerical Computations 371
Acknowledgements 372
References 372
A Prize Problem in Coding Theory 374
Introduction 374
Related Facts about a Putative Type II [72,36,16] Code 375
Future Work 376
Monetary Prizes 377
Acknowledgements 377
References 377
An Application of Möller's Algorithm to Coding Theory 379
Introduction 379
An Ideal Associated with a Linear Code 379
A Second Way of Getting the Data for I 380
Examples 381
Working out with a Gröbner Representation 381
Combinatorial Properties of a Binary Code 382
Example: the Golay Code 383
GAP Computing Section 383
Acknowledgement 384
References 384
Mattson Solomon Transform and Algebra Codes 385
Introduction 385
Mattson-Solomon Transform 386
Generator Theory 386
A Note on the Syndrome Variety 388
Acknowledgement 388
References 388
Decoding Folded Reed-Solomon Codes Using Hensel-Lifting 389
Introduction 389
Folded Reed-Solomon Codes 390
Decoding of Folded Reed-Solomon Codes 390
References 393
A Note on the Generalisation of the Guruswami-Sudan List Decoding Algorithm to Reed-Muller Codes 395
Definitions and Notation 395
The Algorithm 396
The Analysis 396
Acknowledgement 397
References 397
Viewing Multipoint Codes as Subcodes of One-Point Codes 399
Introduction 399
Embedding a Multipoint Code in a One-Point Code 400
Examples 400
Conclusion 402
Acknowledgements 402
References 402
A Short Introduction to Cyclic Convolutional Codes 403
Introduction and Preliminaries 403
How to Define Cyclic Convolutional Codes? 404
Analyzing Cyclic CC's with Gröbner-type Theory 406
Acknowledgement 407
References 407
On the Non-linearity of Boolean Functions 409
Introduction 409
Preliminaries and Notation 409
Computing the Non-linearity 411
Acknowledgements 412
References 413
Quasigroups as Boolean Functions, Their Equation Systems and Gröbner Bases 414
Introduction 414
Quasigroups as Vector Valued Boolean Functions 415
Lexicographic Ordering of Finite Quasigroups 415
Vector Valued Boolean Functions 415
Classification of Quasigroups 416
Systems of Quasigroup Equations and Gröbner Bases 417
Acknowledgement 418
References 419
A New Measure to Estimate Pseudo-Randomness of Boolean Functions and Relations with Gröbner Bases 420
Introduction 420
Normalized Average Number of Terms-NANT 421
NANT and SHA-Family of Hash Functions 422
Acknowledgement 424
References 424
Radical Computation for Small Characteristics 425
Introduction 425
Another Radical Computation Method for Positive Characteristic 426
Comparison of Computational Time and Discussion 426
Acknowledgements 428
References 428