Concise Encyclopedia Of Coding Theory

Description

Most coding theory experts date the origin of the subject with the 1948 publication of A Mathematical Theory of Communication by Claude Shannon. Since then, coding theory has grown into a discipline with many practical applications (antennas, networks, memories), requiring various mathematical techniques, from commutative algebra, to semi-definite programming, to algebraic geometry. Most topics covered in the Concise Encyclopedia of Coding Theory are presented in short sections at an introductory level and progress from basic to advanced level, with definitions, examples, and many references. The book is divided into three parts: Part I fundamentals: cyclic codes, skew cyclic codes, quasi-cyclic codes, self-dual codes, codes and designs, codes over rings, convolutional codes, performance bounds Part II families: AG codes, group algebra codes, few-weight codes, Boolean function codes, codes over graphs Part III applications: alternative metrics, algorithmic techniques, interpolation decoding, pseudo-random sequences, lattices, quantum coding, space-time codes, network coding, distributed storage, secret-sharing, and code-based-cryptography. Features: • Suitable for students and researchers in a wide range of mathematical disciplines • Contains many examples and references • Most topics take the reader to the frontiers of research Cover......Page 1 Half Title......Page 2 Title Page......Page 4 Copyright Page......Page 5 Dedication......Page 6 Contents......Page 8 Preface......Page 24 Contributors......Page 30 I: Coding Fundamentals......Page 34 1.1. Introduction......Page 36 1.2. Finite Fields......Page 38 1.3. Codes......Page 40 1.4. Generator and Parity Check Matrices......Page 41 1.5. Orthogonality......Page 42 1.6. Distance and Weight......Page 43 1.7. Puncturing, Extending, and Shortening Codes......Page 45 1.8. Equivalence and Automorphisms......Page 46 1.9. Bounds on Codes......Page 48 1.9.1. The Sphere Packing Bound......Page 49 1.9.3. The Plotkin Bound......Page 50 1.9.5. The Linear Programming Bound......Page 51 1.9.6. The Gilbert Bound......Page 52 1.9.8. Asymptotic Bounds......Page 53 1.10. Hamming Codes......Page 54 1.11. Reed-Muller Codes......Page 55 1.12. Cyclic Codes......Page 56 1.13. Golay Codes......Page 61 1.14. BCH and Reed-Solomon Codes......Page 63 1.15. Weight Distributions......Page 66 1.16. Encoding......Page 68 1.17. Decoding......Page 71 1.18. Shannon's Theorem......Page 75 2.1. Notation and Introduction......Page 78 2.2. Subfield Subcodes......Page 79 2.3. Fundamental Constructions of Cyclic Codes......Page 80 2.4. The Minimum Distances of Cyclic Codes......Page 81 2.5. Irreducible Cyclic Codes......Page 82 2.6. BCH Codes and Their Properties......Page 83 2.6.1. The Minimum Distances of BCH Codes......Page 84 2.6.2. The Dimensions of BCH Codes......Page 85 2.6.3. Other Aspects of BCH Codes......Page 86 2.7. Duadic Codes......Page 87 2.8. Punctured Generalized Reed-Muller Codes......Page 88 2.9. Another Generalization of the Punctured Binary Reed-Muller Codes......Page 90 2.10. Reversible Cyclic Codes......Page 91 3.1. Introduction......Page 94 3.2. Equivalence and Isomorphism......Page 95 3.2.1. Prescribing Symmetries......Page 96 3.2.2. Determining Symmetries......Page 99 3.3. Some Central Classes of Codes......Page 100 3.3.1. Perfect Codes......Page 101 3.3.2. MDS Codes......Page 105 3.3.3. Binary Error-Correcting Codes......Page 106 4.1. Introduction......Page 112 4.2. Weight Enumerators......Page 114 4.3. Bounds for the Minimum Distance......Page 117 4.4.1. Gluing Theory......Page 121 4.4.2. Circulant Constructions......Page 122 4.4.4. Recursive Constructions......Page 123 4.4.5. Constructions of Codes with Prescribed Automorphisms......Page 125 4.5. Enumeration and Classification......Page 126 5.1. Introduction......Page 130 5.2. Designs Supported by Codes......Page 131 5.3. Perfect Codes and Designs......Page 132 5.4. The Assmus-Mattson Theorem......Page 134 5.5. Designs from Codes Meeting the Johnson Bound......Page 135 5.6. Designs and Majority Logic Decoding......Page 138 5.7. Concluding Remarks......Page 142 6.1. Introduction......Page 144 6.2. Quaternary Codes......Page 145 6.3. The Gray Map......Page 146 6.3.1. Kernels of Quaternary Codes......Page 147 6.4.1. Codes over Frobenius Rings......Page 148 6.4.2. Families of Rings......Page 150 6.4.3. The Chinese Remainder Theorem......Page 153 6.5. The MacWilliams Identities......Page 154 6.6. Generating Matrices......Page 156 6.7. The Singleton Bound and MDR Codes......Page 159 6.8. Conclusion......Page 160 7.1. Introduction......Page 162 7.2. Algebraic Structure......Page 163 7.3.1. The Chinese Remainder Theorem and Concatenated Decompositions of QC Codes......Page 165 7.3.2.1. Trace Representation......Page 167 7.3.2.2. Self-Dual and Complementary Dual QC Codes......Page 168 7.4.2. The Lally Bound......Page 170 7.4.3.1. Cyclic Codes and Distance Bounds From Their Zeros......Page 171 7.4.3.2. Spectral Theory of QC Codes......Page 173 7.4.3.3. Spectral Bounds for QC Codes......Page 174 7.5.1. Good Self-Dual QC Codes Exist......Page 176 7.5.2. Complementary Dual QC Codes Are Good......Page 180 7.6. Connection to Convolutional Codes......Page 181 8.1. Introduction......Page 184 8.2. Basic Properties of Skew-Polynomial Rings......Page 185 8.3. Skew Polynomials and Linearized Polynomials......Page 190 8.4. Evaluation of Skew Polynomials and Roots......Page 191 8.5. Algebraic Sets and Wedderburn Polynomials......Page 195 8.6. A Circulant Approach Toward Cyclic Block Codes......Page 199 8.7. Algebraic Theory of Skew-Cyclic Codes with General Modulus......Page 202 8.8. Skew-Constacyclic Codes and Their Duals......Page 207 8.9. The Minimum Distance of Skew-Cyclic Codes......Page 209 9.1. Introduction......Page 214 9.3. Code Equivalence and Cyclicity......Page 215 9.4. Additive Codes Which Are Cyclic in the Permutation Sense......Page 217 9.4.1. The Linear Case m = 1......Page 218 9.4.2. The General Case m 1......Page 220 9.4.3. Equivalence......Page 223 9.4.4. Duality and Quantum Codes......Page 224 9.5. Additive Codes Which Are Cyclic in the Monomial Sense......Page 226 9.5.1. The Linear Case m = 1......Page 227 9.5.2. The General Case m 1......Page 228 10.1. Introduction......Page 230 10.2.1. Definition of Convolutional Codes via Generator and Parity Check Matrices......Page 231 10.2.2. Distances of Convolutional Codes......Page 236 10.3.1. Constructions of MDS Convolutional Codes......Page 240 10.3.2. Constructions of MDP Convolutional Codes......Page 241 10.4. Connections to Systems Theory......Page 244 10.5.1.1. The Case = 0......Page 247 10.5.1.2. The General Case......Page 248 10.5.2. The Viterbi Decoding Algorithm......Page 250 10.6.1. Definition of 2D Convolutional Codes via Generator and Parity Check Matrices......Page 251 10.6.2. ISO Representations......Page 254 10.7. Connections to Symbolic Dynamics......Page 256 11.1. Definitions, Isometries, and Equivalence of Codes......Page 260 11.2. The Notion of Support in the Rank Metric......Page 263 11.3. MRD Codes and Optimal Anticodes......Page 265 11.4. Duality and the MacWilliams Identities......Page 269 11.5. Generalized Weights......Page 272 11.6. q-Polymatroids and Code Invariants......Page 278 12.1. Preliminaries { Krawtchouk Polynomials, Codes, and Designs......Page 284 12.2. General Linear Programming Theorems......Page 286 12.3. Universal Bounds......Page 288 12.4. Linear Programming on Sn-1......Page 294 12.5. Linear Programming in Other Coding Theory Problems......Page 298 13.1. Introduction......Page 300 13.2.1. Conic Programming and its Duality Theory......Page 301 13.2.3. Semide nite Programming......Page 303 13.3.1. Independence Number and Codes......Page 305 13.3.2. Semide nite Programming Bounds for the Independence Number......Page 306 13.4. Symmetry Reduction and Matrix *-Algebras......Page 308 13.4.2. Matrix *-Algebras......Page 309 13.4.3. Example: The Delsarte Linear Programming Bound......Page 310 13.4.4. Example: The Schrijver Semide nite Programming Bound......Page 311 13.5. Extensions and Rami cations......Page 312 II: Families of Codes......Page 316 14.1.1. Basic Properties of Galois Geometries......Page 318 14.1.2. Spreads and Partial Spreads......Page 320 14.2.2. Via the Parity Check Matrix......Page 321 14.2.3. Linear MDS Codes and Arcs in Galois Geometries......Page 322 14.2.4. Griesmer Bound and Minihypers......Page 325 14.3. Projective Reed-Muller Codes......Page 326 14.4. Linear Codes Defined by Incidence Matrices Arising from Galois Geometries......Page 328 14.5.1. Definitions......Page 330 14.5.3. Rank-Metric Codes......Page 332 14.5.4. Maximum Scattered Subspaces and MRD Codes......Page 334 14.5.5. Semifields and MRD Codes......Page 335 14.6. A Geometric Result Arising from a Coding Theoretic Result......Page 336 15. Algebraic Geometry Codes and Some Applications......Page 340 Introduction......Page 341 15.1. Notation......Page 344 15.2.1. Curves, Points, Function Fields, and Places......Page 345 15.2.2. Divisors......Page 346 15.2.4. Differential Forms......Page 347 15.2.5. Genus and the Riemann-Roch Theorem......Page 348 15.3.1. Algebraic Geometry Codes, Definitions, and Elementary Results......Page 349 15.3.2. Genus 0, Generalized Reed-Solomon and Classical Goppa Codes......Page 352 15.3.2.1. The CL Description......Page 353 15.3.2.2. The C Description......Page 354 15.4.1. Preamble......Page 356 15.4.2. The Tsfasman-Vladut-Zink Bound......Page 357 15.5. Improved Lower Bounds for the Minimum Distance......Page 359 15.5.1. Floor Bounds......Page 361 15.5.2. Order Bounds......Page 363 15.5.4. Geometric Bounds for Codes from Embedded Curves......Page 365 15.6.1.1. The Basic Algorithm......Page 366 15.6.1.2. Getting Rid of Algebraic Geometry: Error-Correcting Pairs......Page 369 15.6.1.4. Decoding Up to Half the Designed Distance: The Feng-Rao Algorithm and Error-Correcting Arrays......Page 370 15.6.2. List Decoding and the Guruswami-Sudan Algorithm......Page 372 15.7.1. History......Page 373 15.7.4. Janwa and Moreno's Proposals Using AG Codes......Page 375 15.7.5.3. Conclusion: Only Subfield Subcodes of AG Codes Remain Unbroken......Page 376 15.8.1.1. The *-Product from the Perspective of AG Codes......Page 377 15.8.1.2. Dimension of *-Products......Page 378 15.8.1.4. Automorphisms......Page 380 15.8.2. Frameproof Codes and Separating Systems......Page 381 15.8.3. Multiplication Algorithms......Page 382 15.8.4. Arithmetic Secret Sharing......Page 385 15.9.1. Motivation......Page 387 15.9.3. Tamo-Barg Codes......Page 389 15.9.4. Locally Recoverable Codes from Coverings of Algebraic Curves: Barg-Tamo-Vladut Codes......Page 390 15.9.6. Fibre Products of Curves and the Availability Problem......Page 392 16.1. Introduction......Page 396 16.2. Finite Dimensional Algebras......Page 397 16.3. Group Algebras......Page 400 16.4. Group Codes......Page 402 16.5. Self-Dual Group Codes......Page 406 16.6. Idempotent Group Codes......Page 407 16.7. LCP and LCD Group Codes......Page 408 16.8. Divisible Group Codes......Page 410 16.9. Checkable Group Codes......Page 412 16.10. Decoding Group Codes......Page 414 16.11. Asymptotic Results......Page 415 16.12. Group Codes over Rings......Page 416 17.1. Introduction......Page 418 17.2. Chain Rings, Galois Rings, and Alternative Distances......Page 420 17.3. Constacyclic Codes over Arbitrary Commutative Finite Rings......Page 424 17.4. Simple-Root Cyclic and Negacyclic Codes over Finite Chain Rings......Page 425 17.5. Repeated-Root Constacyclic Codes over Galois Rings......Page 432 17.6.1. All Constacyclic Codes of Length ps over R......Page 440 17.6.2. All Constacyclic Codes of Length 2ps over R......Page 445 17.6.3. All Constacyclic Codes of Length 4 ps over R......Page 447 17.6.4. -Constacyclic Codes of Length nps over R, - 2 F pm......Page 451 17.7. Extensions......Page 456 18.1. Introduction......Page 462 18.3. A Class of Special Finite Rings Rk (Type I)......Page 463 18.3.1 Case (i) k = 1......Page 464 18.3.2 Case (ii) k = 2......Page 465 18.3.3 Case (iii) k > 2......Page 466 18.3.4 Case (iv) Rk(p), p an Odd Prime......Page 468 18.4. A Class of Special Finite Rings R(k; p; uk = a) (Type II)......Page 474 18.5.1. R(2, p, u2 = u)......Page 477 18.5.2. R(3, 2, u3 = 1)......Page 479 18.5.3. R(3, 3, u3 = 1)......Page 480 18.6. Conclusion......Page 481 19.1. Generalities......Page 482 19.2.1. Weights......Page 483 19.3.3. Strongly Regular Graphs......Page 484 19.3.4. Parameters......Page 485 19.3.7. Field Change......Page 486 19.5. Cyclotomy......Page 487 19.5.1. The Van Lint-Schrijver Construction......Page 488 19.6.1. One-Dimensional Affine Rank 3 Groups......Page 489 19.7. Two-Character Sets in Projective Space......Page 490 19.7.2. Quadrics......Page 491 19.7.6. Sporadic Examples......Page 492 19.9.1. From Projective Code to Two-Weight Code......Page 494 19.9.2. From Two-Weight Code to Projective Code......Page 495 20. Linear Codes from Functions......Page 496 20.1. Introduction......Page 498 20.2.2.1. Representations of p-Ary Functions......Page 499 20.2.2.2. The Walsh Transform of a Vectorial Function......Page 501 20.2.3. Nonlinearity of Vectorial Boolean Functions and Bent Boolean Functions......Page 502 20.2.4. Plateaued Functions and More about Bent Functions......Page 504 20.2.5. Differential Uniformity of Vectorial Boolean Functions, PN, and APN Functions......Page 506 20.2.6. APN and Planar Functions over Fqm......Page 507 20.2.7. Dickson Polynomials......Page 508 20.3.1. The First Generic Construction......Page 509 20.3.2.1. The Defining Set Construction of Linear Codes......Page 511 20.4.1. A First Example of Codes from Boolean Functions: Reed-Muller Codes......Page 512 20.4.3. Binary Codes from the Preimage f��1(b) of Boolean Functions......Page 513 20.4.4. Codes with Few Weights from Bent Boolean Functions......Page 514 20.4.5. Codes with Few Weights from Semi-Bent Boolean Functions......Page 515 20.4.6. Linear Codes from Quadratic Boolean Functions......Page 516 20.4.8. Binary Codes CDf with Four Weights......Page 517 20.4.9. Binary Codes CDf with at Most Five Weights......Page 518 20.4.10. A Class of Two-Weight Binary Codes from the Preimage of a Type of Boolean Function......Page 519 20.4.12. Binary Codes with Few Weights from Plateaued Boolean Functions......Page 520 20.4.13. Binary Codes with Few Weights from Almost Bent Functions......Page 521 20.4.15. Binary Codes from the Images of Certain Functions on F2m......Page 522 20.5.1 A Generic Construction of Cyclic Codes with Polynomials......Page 523 20.5.2. Binary Cyclic Codes from APN Functions......Page 525 20.5.3. Non-Binary Cyclic Codes from Monomials and Trinomials......Page 528 20.5.4. Cyclic Codes from Dickson Polynomials......Page 531 20.6.1. Codes with Few Weights from p-Ary Weakly Regular Bent Functions Based on the First Generic Construction......Page 536 20.6.2. Linear Codes with Few Weights from Cyclotomic Classes and Weakly Regular Bent Functions......Page 537 20.6.3 Codes with Few Weights from p-Ary Weakly Regular Bent Functions Based on the Second Generic Construction......Page 540 20.6.4. Codes with Few Weights from p-Ary Weakly Regular Plateaued Functions Based on the First Generic Construction......Page 541 20.6.5. Codes with Few Weights from p-Ary Weakly Regular Plateaued Functions Based on the Second Generic Construction......Page 543 20.7. Optimal Linear Locally Recoverable Codes from p-Ary Functions......Page 554 20.7.1.3. Good Polynomials from Function Composition......Page 556 20.7.1.4. Good Polynomials from Dickson Polynomials of the First Kind......Page 557 20.7.1.5. Good Polynomials from the Composition of Functions Involving Dickson Polynomials......Page 558 21.1 Introduction......Page 560 21.2 Low-Density Parity Check Codes......Page 561 21.3 Decoding......Page 565 21.3.1. Decoder Analysis......Page 570 21.4 Codes from Finite Geometries......Page 573 21.5 Codes from Expander Graphs......Page 575 21.6 Protograph Codes......Page 578 21.7 Density Evolution......Page 581 21.8.1. Turbo Codes......Page 583 21.8.3. Spatially-Coupled LDPC Codes......Page 584 III: Applications......Page 586 22.1. Introduction......Page 588 22.2.1. Projective Metrics......Page 591 22.2.2. Combinatorial Metrics......Page 592 22.2.2.2. b-Burst Metrics......Page 594 22.3. Poset Metrics......Page 595 22.3.2. Graph Metrics......Page 598 22.4.1. Metrics over Rings of Integers......Page 599 22.4.3. Kaushik-Sharma Metrics......Page 600 22.5.1. Pomset Metrics......Page 601 22.5.2. m-Spotty Metrics......Page 602 22.6.1. The Asymmetric Metric......Page 603 22.7. Editing Metrics......Page 604 22.7.1. Bounds for Editing Codes......Page 605 22.8. Permutation Metrics......Page 606 23.1. Introduction......Page 608 23.2. Linear Codes with Prescribed Minimum Distance......Page 609 23.3. Linear Codes as Sets of Points in Projective Geometry......Page 610 23.3.1. Automorphisms of Projective Point Sets......Page 613 23.4. Projective Point Sets with Prescribed Automorphism Groups......Page 615 23.4.2. Observations for Permutation Groups......Page 618 23.4.3. Observations for Cyclic Groups......Page 619 23.6.2. Codes with Few Weights......Page 620 23.6.3. Divisible Codes......Page 621 23.6.4. Codes with Prescribed Gram Matrix......Page 622 23.6.5. Self-Orthogonal Codes......Page 624 23.6.6. LCD Codes......Page 625 23.7. Extensions of Codes......Page 627 23.8. Determining the Minimum Distance and Weight Distribution......Page 628 24.1. Introduction......Page 632 24.2. The Berlekamp-Welch Algorithm......Page 633 24.2.1. Correctness of the Algorithm RSDecode......Page 635 24.3.1. The Sudan Algorithm......Page 636 24.3.2 Correctness of the Algorithm RSListDecodeV1......Page 637 24.4. List-decoding of Reed-Solomon Codes Using Multiplicities......Page 638 24.4.1. Preparations......Page 639 24.4.2. The Guruswami-Sudan Algorithm......Page 640 24.4.4. Why Do Multiplicities Help?......Page 641 24.5. Decoding of Interleaved Reed-Solomon Codes under Random Error......Page 642 24.6. Further Reading......Page 644 25.1. Introduction......Page 646 25.2.1. Correlation Measures of Sequences......Page 647 25.2.2. Sequences with Low Periodic Autocorrelation......Page 652 25.2.3. Sequence Families with Low Periodic Correlation......Page 657 25.3. Shift Register Sequences......Page 659 25.3.1. Feedback Shift Registers......Page 660 25.3.2. Cycle Structure......Page 661 25.3.3. Cycle Joining and Splitting......Page 663 25.3.4. Cycle Structure of LFSRs......Page 664 25.4.1. Graphical Approach......Page 667 25.4.2. Combinatorial Approach......Page 669 25.4.3. Algebraic Approach......Page 673 26.1. Introduction......Page 678 26.2. Lattice Coding for the Gaussian Channel......Page 679 26.3.1. Channel Model and Design Criteria......Page 681 26.3.2. Lattices from Quadratic Fields......Page 682 26.4.1. Construction A......Page 684 26.4.2. Constructions D and D......Page 686 26.5. Variations of Lattice Coding Problems......Page 687 26.5.2. Wiretap Codes......Page 688 27.1. Introduction......Page 690 27.2. Preliminaries......Page 691 27.3. The Stabilizer Formalism......Page 693 27.4. Constructions via Classical Codes......Page 698 27.5. Going Asymmetric......Page 702 27.6. Other Approaches and a Conclusion......Page 704 28.1. Introduction......Page 706 28.2. Channel Models and Design Criteria......Page 707 28.2.1. Coherent Space-Time Coding......Page 708 28.2.2. Differential Space-Time Coding......Page 709 28.3.1. The Alamouti Code......Page 710 28.3.3. The Golden Code......Page 711 28.3.4. Cayley Codes......Page 712 28.4.1. Distributed Space-Time Coding......Page 713 28.4.3. Fast Decodable Space-Time Codes......Page 714 28.4.4. Secure Space-Time Coding......Page 716 29.1. Packet Networks......Page 718 29.2.1. Combinational Packet Networks......Page 720 29.2.3. The Unicast Problem......Page 722 29.2.4. Linear Network Coding Achieves Multicast Capacity......Page 723 29.2.5. Multicasting from Multiple Sources......Page 724 29.3. Random Linear Network Coding......Page 725 29.4.1. Vector Space, Matrix, and Combinatorial Preliminaries......Page 727 29.4.2. The Operator Channel......Page 730 29.5.1. Subspace Codes......Page 731 29.5.2. Coding Metrics on......Page 732 29.6.1. The Sphere Packing Bound......Page 734 29.6.3. The Anticode Bound......Page 735 29.6.4. Johnson-Type Bounds......Page 736 29.6.6. A Gilbert-Varshamov-Type Bound......Page 737 29.7.1. Lifted Rank-Metric Codes......Page 738 29.7.2. Padded Codes......Page 740 29.7.3. Lifted Ferrers Diagram Codes......Page 741 29.7.5. Further Constructions......Page 743 29.8.2. Decoding Lifted Delsarte-Gabidulin Codes......Page 744 29.8.3. Decoding a Union of Lifted FD Codes......Page 745 29.9. Conclusions......Page 746 30.1. Introduction......Page 748 30.2. Tornado Codes......Page 750 30.3. LT Codes......Page 755 30.4. Raptor Codes......Page 760 31. Codes for Distributed Storage......Page 768 31.1. Reed–Solomon Codes......Page 770 31.2. Regenerating Codes......Page 771 31.2.2. General Definition of a Regenerating Code......Page 772 31.2.3. Bound on File Size......Page 773 31.2.4. MSR and MBR Codes......Page 774 31.2.6. Polygon MBR Codes......Page 775 31.2.7.1. PM-MSR Codes......Page 776 31.2.7.2. PM-MBR Codes......Page 777 31.2.8. The Clay Code......Page 778 31.2.9. Variants of Regenerating Codes......Page 781 31.3. Locally Recoverable Codes......Page 782 31.3.1.1. Pyramid Codes......Page 783 31.3.2. All Symbol Locality......Page 784 31.3.3. LRCs over Small Field Size......Page 786 31.3.4.1. Codes with Sequential Recovery......Page 787 31.3.4.3. Codes with Availability......Page 788 31.3.4.5. Codes with (r, ) Locality......Page 789 31.3.5. Maximally Recoverable Codes......Page 790 31.4. Locally Regenerating Codes......Page 791 31.5. Efficient Repair of Reed-Solomon Codes......Page 792 31.6. Codes for Distributed Storage in Practice......Page 793 32.1. Introduction......Page 796 32.2. Kernel Based ECCs......Page 797 32.2.1. Kernel Based ECCs are Recursive GCCs......Page 799 32.3. Channel Splitting and Combining and the SC Algorithm......Page 802 32.4. Polarization Conditions......Page 804 32.4.1. Polarization Rate......Page 807 32.5.1. Polar Code Design......Page 808 32.6. Polar Codes Encoding Algorithms......Page 809 32.7. Polar Codes Decoding Algorithms......Page 810 32.7.1.1. SC for (u + v, v)......Page 811 32.7.1.2. SC for General Kernels......Page 813 32.7.2. The SCL Decoding Algorithm......Page 814 32.8. Summary and Concluding Remarks......Page 816 33.1. Introduction to Secret Sharing Schemes......Page 818 33.2. The First Construction of Secret Sharing Schemes......Page 820 33.3.1. Minimal Linear Codes and the Covering Problem......Page 823 33.3.2. The Second Construction of Secret Sharing Schemes......Page 824 33.3.3. Secret Sharing Schemes from the Duals of Minimal Codes......Page 825 33.3.4. Other Works on the Second Construction......Page 826 33.4. Multisecret Sharing with Linear Codes......Page 827 33.4.1. The Relation Between Multisecret Sharing and Codes......Page 828 33.4.2. Linear Threshold Schemes and MDS Codes......Page 829 34. Code-Based Cryptography......Page 832 34.1.1. Notation......Page 833 34.1.2. Background on Coding Theory......Page 834 34.2. Difficult Problems for Code-Based Cryptography: The Syndrome Decoding Problem and Its Variations......Page 836 34.3. Best-Known Attacks for the Syndrome Decoding Problem......Page 837 34.4.1. The McEliece and Niederreiter Frameworks......Page 840 34.4.2. Group-Structured McEliece Framework......Page 842 34.4.3. Moderate-Density Parity Check (MDPC) Codes......Page 843 34.5.1. Alekhnovich's Approach......Page 845 34.5.2. HQC: E cient Encryption from Random Quasi-Cyclic Codes......Page 846 34.5.3. Ouroboros Key-Exchange Protocol......Page 847 34.6. Examples of Parameters for Code-Based Encryption and Key Exchange......Page 848 34.7. Authentication: The Stern Zero-Knowledge Protocol......Page 849 34.8. Digital Signatures from Coding Theory......Page 850 34.8.2. The CFS Signature Scheme......Page 851 34.8.3. The WAVE Signature......Page 852 34.10. Rank-Based Cryptography......Page 853 Bibliography......Page 856 Index......Page 974