Skip to main content
main-content

Über dieses Buch

This book constitutes the refereed proceedings of the 18th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-18, held in Tarragona, Spain, in June 2009. The 22 revised full papers presented together with 7 extended absstracts were carefully reviewed and selected from 50 submissions. Among the subjects addressed are block codes, including list-decoding algorithms; algebra and codes: rings, fields, algebraic geometry codes; algebra: rings and fields, polynomials, permutations, lattices; cryptography: cryptanalysis and complexity; computational algebra: algebraic algorithms and transforms; sequences and boolean functions.

Inhaltsverzeichnis

Frontmatter

Codes

The Order Bound for Toric Codes

Abstract
In this paper we investigate the minimum distance of generalized toric codes using an order bound like approach. We apply this technique to a family of codes that includes the Joyner code. For some codes in this family we are able to determine the exact minimum distance.
Peter Beelen, Diego Ruano

An Extension of the Order Bound for AG Codes

Abstract
The most successful method to obtain lower bounds for the minimum distance of an algebraic geometric code is the order bound, which generalizes the Feng-Rao bound. By using a finer partition of the set of all codewords of a code we improve the order bounds by Beelen and by Duursma and Park. We show that the new bound can be efficiently optimized and we include a numerical comparison of different bounds for all two-point codes with Goppa distance between 0 and 2g − 1 for the Suzuki curve of genus g = 124 over the field of 32 elements.
Iwan Duursma, Radoslav Kirov

Sparse Numerical Semigroups

Abstract
We investigate the class of numerical semigroups verifying the property ρ i + 1 − ρ i  ≥ 2 for every two consecutive elements smaller than the conductor. These semigroups generalize Arf semigroups.
C. Munuera, F. Torres, J. Villanueva

From the Euclidean Algorithm for Solving a Key Equation for Dual Reed–Solomon Codes to the Berlekamp–Massey Algorithm

Abstract
The two primary decoding algorithms for Reed-Solomon codes are the Berlekamp-Massey algorithm and the Sugiyama et al. adaptation of the Euclidean algorithm, both designed to solve a key equation. This article presents a new version of the key equation and a way to use the Euclidean algorithm to solve it. A straightforward reorganization of the algorithm yields the Berlekamp-Massey algorithm.
Maria Bras-Amorós, Michael E. O’Sullivan

Rank for Some Families of Quaternary Reed-Muller Codes

Abstract
Recently, new families of quaternary linear Reed-Muller codes such that, after the Gray map, the corresponding ℤ4-linear codes have the same parameters and properties as the codes in the usual binary linear Reed-Muller family have been introduced. A structural invariant, the rank, for binary codes is used to classify some of these ℤ4-linear codes. The rank is established generalizing the known results about the rank for ℤ4-linear Hadamard and ℤ4-linear extended 1-perfect codes.
Jaume Pernas, Jaume Pujol, Mercè Villanueva

Optimal Bipartite Ramanujan Graphs from Balanced Incomplete Block Designs: Their Characterizations and Applications to Expander/LDPC Codes

Abstract
We characterize optimal bipartite expander graphs and give necessary and sufficient conditions for optimality. We determine the expansion parameters of the BIBD graphs and show that they yield optimal expander graphs that are also bipartite Ramanujan graphs. In particular, we show that the bipartite graphs derived from finite projective and affine geometries yield optimal Ramanujan graphs. This in turn leads to a theoretical explanation of the good performance of a class of LDPC codes.
Tom Høholdt, Heeralal Janwal

Simulation of the Sum-Product Algorithm Using Stratified Sampling

Abstract
Using stratified sampling a desired confidence level and a specified margin of error can be achieved with smaller sample size than under standard sampling. We apply stratified sampling to the simulation of the sum-product algorithm on a binary low-density parity-check code.
John Brevik, Michael E. O’Sullivan, Anya Umlauf, Rich Wolski

A Systems Theory Approach to Periodically Time-Varying Convolutional Codes by Means of Their Invariant Equivalent

Abstract
In this paper we construct (n,k,δ) time-variant convolutional codes of period τ. We use the systems theory to represent our codes by the input-state-output representation instead of using the generator matrix. The obtained code is controllable and observable. This construction generalizes the one proposed by Ogasahara, Kobayashi, and Hirasawa (2007). We also develop and study the properties of the time-invariant equivalent convolutional code and we show a lower bound for the free distance in the particular case of MDS block codes.
Joan-Josep Climent, Victoria Herranz, Carmen Perea, Virtudes Tomás

On Elliptic Convolutional Goppa Codes

Abstract
The algebraic geometric tools used by Goppa to construct block codes with good properties have been also used successfully in the setting of convolutional codes. We present here this construction carried out over elliptic curves, yielding a variety of codes which are optimal with respect to different bounds. We provide a number of examples for different values of their parameters, including some explicit strongly MDS convolutional codes. We also introduce some conditions for certain codes of this class to be MDS.
José Ignacio Iglesias Curto

The Minimum Hamming Distance of Cyclic Codes of Length 2p s

Abstract
We study cyclic codes of length 2p s over \(\mathbb {F}_{q}\), where p is an odd prime. Using the results of [1], we compute the minimum Hamming distance of these codes.
Hakan Özadam, Ferruh Özbudak

There Are Not Non-obvious Cyclic Affine-invariant Codes

Abstract
We show that an affine-invariant code C of length p m is not permutation equivalent to a cyclic code except in the obvious cases: m = 1 or C is either {0}, the repetition code or its dual.
José Joaquín Bernal, Ángel del Río, Juan Jacobo Simón

On Self-dual Codes over Z 16

Abstract
In this paper, we look at self-dual codes over the ring Z 16 of integers modulo 16. From any doubly even self-dual binary code, we construct codes over Z 16 and give a necessary and sufficient condition for the self-duality of induced codes. We then give an inductive algorithm for constructing all self-dual codes over Z 16 , and establish the mass formula, which counts the number of such codes.
Kiyoshi Nagata, Fidel Nemenzo, Hideo Wada

Cryptography

A Non-abelian Group Based on Block Upper Triangular Matrices with Cryptographic Applications

Abstract
The aim of this article is twofold. In the first place, we describe a special non-abelian group of block upper triangular matrices, and verify that choosing properly certain parameters, the order of the subgroup generated by one of these matrices can be as large as needed. Secondly, we propose and implement a new key exchange scheme based on these primitives. The security of the proposed system is based on discrete logarithm problem although a non-abelian group of matrices is used. The primary advantadge of this scheme is that no prime numbers are used and the efficiency is guaranteed by the use of a quick exponentiation algorithm for this group of matrices.
Rafael Álvarez, Leandro Tortosa, José Vicent, Antonio Zamora

Word Oriented Cascade Jump σ−LFSR

Abstract
Bit oriented cascade jump registers were recently proposed as building blocks for stream cipher. They are hardware oriented designed hence inefficient in software. In this paper word oriented cascade jump registers are presented based on the design idea of bit oriented cascade jump registers. Their constructions make use of special word oriented σ−LFSRs, which can be efficiently implemented on modern CPU and only require few memory. Experimental results show that one type of efficient word oriented cascade jump σ−LFSRs can be used as building blocks for software oriented stream cipher.
Guang Zeng, Yang Yang, Wenbao Han, Shuqin Fan

On Some Sequences of the Secret Pseudo-random Index j in RC4 Key Scheduling

Abstract
RC4 Key Scheduling Algorithm (KSA) uses a secret pseudo-random index j which is dependent on the secret key. Let S N be the permutation after the complete KSA of RC4. It is known that the value of j in round y + 1 can be predicted with high probability from S N [y] for the initial values of y and from \(S^{-1}_N[y]\) for the final values of y. This fact has been exploited in several recent works on secret key recovery from S N . In this paper, we perform extensive analysis of some special sequences of indices corresponding to the j values that leak useful information for key recovery. We present new theoretical results on the probability and the number of such sequences. As an application, we explain a new secret key recovery algorithm that can recover a 16 bytes secret key with a success probability of 0.1409. Our strategy has high time complexity at this point and requires further improvement to be feasible in practice.
Riddhipratim Basu, Subhamoy Maitra, Goutam Paul, Tanmoy Talukdar

Very-Efficient Anonymous Password-Authenticated Key Exchange and Its Extensions

Abstract
An anonymous password-authenticated key exchange (anonymous PAKE) protocol is designed to provide both password-only authentication and user anonymity. In this paper, we propose a very-efficient anonymous PAKE (called, VEAP) protocol that provides the most efficiency among their kinds in terms of computation and communication costs. The VEAP protocol guarantees semantic security of session keys in the random oracle model under the chosen target CDH problem, and unconditional user anonymity against a semi-honest server. If the pre-computation is allowed, the computation cost of the VEAP protocol is the same as the well-known Diffie-Hellman protocol! In addition, we extend the VEAP protocol in two ways.
SeongHan Shin, Kazukuni Kobara, Hideki Imai

Efficient Constructions of Deterministic Encryption from Hybrid Encryption and Code-Based PKE

Abstract
We build on the new security notion for deterministic encryption (PRIV) and the PRIV-secure schemes presented by Bellare et al at Crypto’07. Our work introduces: 1) A generic and efficient construction of deterministic length-preserving hybrid encryption, which is an improvement on the scheme sketched in the above paper; to our best knowledge, this is the first example of length-preserving hybrid encryption; 2) postquantum deterministic encryption (using the IND-CPA variant of code-based McEliece PKE) which enjoys a simplified construction, where the public key is re-used as a hash function.
Yang Cui, Kirill Morozov, Kazukuni Kobara, Hideki Imai

Algebra

Noisy Interpolation of Multivariate Sparse Polynomials in Finite Fields

Abstract
We consider the problem of recovering an unknown sparse multivariate polynomial \(f\in \mathbb{F}_p[X_1,\ldots,X_m]\) over a finite field \(\mathbb{F}_p\) of prime order p from approximate values of f(t 1,...,t m ) at polynomially many points \((t_1,\ldots,t_m)\in \mathbb{F}_p^m\) selected uniformly at random. Our result is based on a combination of bounds on exponential sums with the lattice reduction technique.
Álvar Ibeas, Arne Winterhof

New Commutative Semifields and Their Nuclei

Abstract
Commutative semifields in odd characteristic can be equivalently described by planar functions (also known as PN functions). We describe a method to construct a semifield which is canonically associated to a planar function and use it to derive information on the nuclei directly from the planar function. This is used to determine the nuclei of families of new commutative semifields of dimensions 9 and 12 in arbitrary odd characteristic.
Jürgen Bierbrauer

Spreads in Projective Hjelmslev Geometries

Abstract
We prove a necessary and sufficient condition for the existence of spreads in the projective Hjelmslev geometries \(PHG(R_R^{n+1})\). Further, we give a construction of projective Hjelmslev planes from spreads that generalizes the familiar construction of projective planes from spreads in PG(n,q).
Ivan Landjev

On the Distribution of Nonlinear Congruential Pseudorandom Numbers of Higher Orders in Residue Rings

Abstract
The nonlinear congruential method is an attractive alternative to the classical linear congruential method for pseudorandom number generation. In this paper we present new discrepancy bounds for sequences of s-tuples of successive nonlinear congruential pseudorandom numbers of higher orders modulo a composite integer M.
Edwin D. El-Mahassni, Domingo Gomez

Rooted Trees Searching for Cocyclic Hadamard Matrices over D 4t

Abstract
A new reduction on the size of the search space for cocyclic Hadamard matrices over dihedral groups D 4t is described, in terms of the so called central distribution. This new search space adopt the form of a forest consisting of two rooted trees (the vertices representing subsets of coboundaries) which contains all cocyclic Hadamard matrices satisfying the constraining condition. Experimental calculations indicate that the ratio between the number of constrained cocyclic Hadamard matrices and the size of the constrained search space is greater than the usual ratio.
Víctor Álvarez, José Ándrés Armario, María Dolores Frau, Félix Gudiel, Amparo Osuna

Extended Abstracts

Interesting Examples on Maximal Irreducible Goppa Codes

Abstract
A full categorization of irreducible classical Goppa codes of degree 4 and length 9 is given: it is an interesting example in the context of finding an upper bound for the number of Goppa codes which are permutation non-equivalent and irreducible and maximal with fixed parameters q, n and r (\({\mathbb F}_q\) is the field of the Goppa code, the Goppa polynomial has coefficients in \({\mathbb F}_{q^n}\) and its degree is r) using group theory techniques.
Marta Giorgetti

Repeated Root Cyclic and Negacyclic Codes over Galois Rings

Abstract
In this notice we describe the ideal structure of all cases of cyclic and negacyclic codes of length p s over a Galois ring alphabet that have not yet been discussed in the literature. Unlike in the cases reported earlier in the literature by various authors, the ambient spaces here are never chain rings. These ambient rings do nonetheless share the properties of being local and having a simple socle.
Sergio R. López-Permouth, Steve Szabo

Construction of Additive Reed-Muller Codes

Abstract
The well known Plotkin construction is, in the current paper, generalized and used to yield new families of ℤ24-additive codes, whose length, dimension as well as minimum distance are studied. These new constructions enable us to obtain families of ℤ24-additive codes such that, under the Gray map, the corresponding binary codes have the same parameters and properties as the usual binary linear Reed-Muller codes. Moreover, the first family is the usual binary linear Reed-Muller family.
Jaume Pujol, J. Rifà, L. Ronquillo

Gröbner Representations of Binary Matroids

Abstract
Several constructions in binary linear block codes are also related to matroid theory topics. These constructions rely on a given order in the ground set of the matroid. In this paper we define the Gröbner representation of a binary matroid and we show how it can be used for studying different sets bases, cycles, activity intervals, etc.
M. Borges-Quintana, M. A. Borges-Trenard, E. Martínez-Moro

A Generalization of the Zig-Zag Graph Product by Means of the Sandwich Product

Abstract
In this paper we develop a generalization of the zig-zag graph product created by Reingold, Vadhan, and Widgerson[8]. We do this by using a broader definition of directed and undirected graphs in which incidence is determined by functions from the edge set to the vertex set. We introduce the sandwich product of graphs and show how our general zig-zag product is a sandwich product.
David M. Monarres, Michael E. O’Sullivan

Novel Efficient Certificateless Aggregate Signatures

Abstract
We propose a new efficient certificateless aggregate signature scheme which has the advantages of both aggregate signatures and certificateless cryptography. The scheme is proven existentially unforgeable against adaptive chosen-message attacks under the standard computational Diffie-Hellman assumption. Our scheme is also efficient in both communication and computation. The proposal is practical for message authentication in many-to-one communications.
Lei Zhang, Bo Qin, Qianhong Wu, Futai Zhang

Bounds on the Number of Users for Random 2-Secure Codes

Abstract
An illegal re-distribution problem is a problem that a regular user who received content re-distributes without legal permutation. This becomes a social problem all over the world. As it is indicated in [2], this problem has been known since a few or more handred years ago. Boneh and Shaw formalize this problem as collusion-secure fingerprinting (c-secure code) for digital data [2]. After their work, study of c-secure code has become one of popular research stream for information security [1]. One of remarkable results is called Tardos’s code [5]. Tardos’s code achieved to construct approximately optimal length c-secure codes with random coding method.
Manabu Hagiwara, Takahiro Yoshida, Hideki Imai

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise