Applied Algebra, Algebraic Algorithms and Error-Correcting Codes: 15th International Symposium, AAECC-15, Toulouse, France, May 12-16, 2003, Proceedings (Lecture Notes in Computer Science, 2643)

This book constitutes the refereed proceedings of the 15th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-15, held in Toulouse, France, in May 2003. The 25 revised full papers presented together with 2 invited papers were carefully reviewed and selected from 40 submissions. Among the subjects addressed are block codes; algebra and codes: rings, fields, and AG codes; cryptography; sequences; decoding algorithms; and algebra: constructions in algebra, Galois groups, differential algebra, and polynomials. Cryptography and the Methodology of Provable Security....Pages 1-5 Dynamical Systems Generated by Rational Functions....Pages 6-17 Homotopy Methods for Equations over Finite Fields....Pages 18-23 Three Constructions of Authentication/Secrecy Codes....Pages 24-33 The Jacobi Model of an Elliptic Curve and Side-Channel Analysis....Pages 34-42 Fast Point Multiplication on Elliptic Curves through Isogenies....Pages 43-50 Interpolation of the Elliptic Curve Diffie-Hellman Mapping....Pages 51-60 An Optimized Algebraic Method for Higher Order Differential Attack....Pages 61-70 Fighting Two Pirates....Pages 71-78 Copyright Control and Separating Systems....Pages 79-86 Unconditionally Secure Homomorphic Pre-distributed Commitments....Pages 87-97 A Class of Low-Density Parity-Check Codes Constructed Based on Reed-Solomon Codes with Two Information Symbols....Pages 98-107 Relative Duality in MacWilliams Identity....Pages 108-118 Good Expander Graphs and Expander Codes: Parameters and Decoding....Pages 119-128 On the Covering Radius of Certain Cyclic Codes....Pages 129-138 Unitary Error Bases: Constructions, Equivalence, and Applications....Pages 139-149 Differentially 2-Uniform Cocycles — The Binary Case....Pages 150-157 The Second and Third Generalized Hamming Weights of Algebraic Geometry Codes....Pages 158-168 Error Correcting Codes over Algebraic Surfaces....Pages 169-179 A Geometric View of Decoding AG Codes....Pages 180-190 Performance Analysis of M-PSK Signal Constellations in Riemannian Varieties....Pages 191-203 Improvements to Evaluation Codes and New Characterizations of Arf Semigroups....Pages 204-215 Optimal 2-Dimensional 3-Dispersion Lattices....Pages 216-225 On g -th MDS Codes and Matroids....Pages 226-234 On the Minimum Distance of Some Families of Z 2 k -Linear Codes....Pages 235-243 Quasicyclic Codes of Index l over F q Viewed as F q [ x ]-Submodules of F q l [ x ]/〈 x m −1〉....Pages 244-253 Fast Decomposition of Polynomials with Known Galois Group....Pages 254-264 TheAAECCsymposiumwasstartedinJune1983byAlainPoli(Toulouse),who, together with Roger Desq, Daniel Lazard, and Paul Camion, organized the ?rst conference. The meaning of the acronym AAECC changed from “Applied - gebra and Error Correcting Codes” to “Applied Algebra, Algebraic Algorithms, and Error Correcting Codes.” One reason for this was the increasing importance of complexity, particularly for decoding algorithms. During the AAECC-12 s- posium the conference committee decided to enforce the theory and practice of the coding side as well as the cryptographic aspects. Algebra was conserved, as in the past, but was slightly more oriented to algebraic geometry codes, ?nite ?elds, complexity, polynomials, and graphs. For AAECC-15 the main subjects covered were: – Block codes. – Algebra and codes: rings, ?elds, AG codes. – Cryptography. – Sequences. – Algorithms, decoding algorithms. – Algebra: constructions in algebra, Galois groups, di?erential algebra, po- nomials. The talks of the six invited speakers characterized the aims of AAECC-15: – P. Sole (“Public Key Cryptosystems Based on Rings”). – S. Lin (“Combinatorics Low Density Parity Check Codes”). – J. Stern (“Cryptography and the Methodology of Provable Security”). – D. Costello (“Graph-Based Convolutional LDPC Codes”). – I. Shparlinsky (“Dynamical Systems Generated by Rational Functions”). – A. Lauder (“Algorithms for Multivariate Polynomials over Finite Fields”).