Ebook: Algebraic Aspects of Digital Communications

Developments of the last few decades in digital communications have created a close link between mathematics and areas of computer science and electrical engineering. A collaboration between such areas now seems very natural due to problems which require deep knowledge and expertise in each area. A special role in such collaboration has played algebra and some of its branches such as algebraic geometry, computational algebra, group theory, etc. As a result of such cooperation now we have disciplines such as coding theory and cryptography which are considered a mix of mathematics, computer science, and electrical engineering.

Coding theory is one of the most important and direct applications of information theory. It is a branch of electrical engineering, digital communication, mathematics, and computer science designing efficient and reliable data transmission methods, so that redundancy in the data can be removed and errors induced by a noisy channel can be corrected. It started with Shannon, Hamming, and many others in the mid 20-th century and became one of the most active areas of research for most of the second half of the 20-th century. Algebraic coding theory was the main direction of coding theory, even though recently other ways of coding have been developed.

Cryptology, is the science of hiding information, and historically has received much attention from the public. As a science it also acquired a solid foundation in the second half of the 20-th century. It is a mixture of theoretical mathematics and computer science which focuses more in areas such as number theory, algebraic geometry, graph theory, algorithm analysis, etc. There have been many conferences and publications which have explored the common ground among such areas.

This volume comes out of the conference “New Challenges in Digital Communications”, Vlora, Albania, 2009. This Advanced Study Institute was funded by a NATO grant as a “Advanced Study Institute”. The conference focused precisely on connections between algebra, algebraic geometry, number theory, graph theory, and related areas of mathematics with coding theory and cryptography.

The conference which was organized at the University of Vlora, during April 27 - May 9, 2008 lasted two weeks and had lectures during the morning sessions and talks during late afternoons. There were over 130 participants in the institute from all over the world. The institute had 15 lecturers, namely:

A. Elezi, J. Gutierrez, W. C. Huffman, K. Magaard, J. Kozicki, G. Nebe, V. Pless, E. Previato, T. Shaska, F. Luca, S. Shpectorov, I. Shparlinski, A. Stein, V. Tonchev, V. Ustimenko, M. Ciperjani (invited speaker)

and the following additional speakers:

A. Kohnert, A. Gunther, A. Gomilko, C. Shor, S. Jakub Kotorowicz, A. Wrblewska, M. Wrobel, S. Chopuryan, L. Szalay, I. Siap, R. Sanjeeva, R. Scherbak, H.P.T. Viet, S. Chopuryean, G. Shaska, M. Ramosaco, N. Pjero

We want first to thank NATO, for providing the funds of the Institute. Without such support this institute would have not been possible.

We also want to thank the University of Vlora, which put all the time and effort in organizing such a big conference. Special thanks to the organizing staff especially Vice-Rector for Research and Development of the University of Vlora, Dr. Pranvera Resulaj, Gertian Balliu, Aulona Mustafaraj, Arjan Beqiri, Altin Mustafaraj, and all the students who volunteered with the conference. Special thanks to all the staff of the University of Vlora who were involved in all organizational tasks of the conference, especially the Department of Mathematics and the Department of Computer Science and Electrical Engineering, and the Vlora Conference Center at the University of Vlora. Further thanks to the Albanian coastguard of the city of Vlora for their help in making possible the boat trips for the conference participants.

We want to thank the Albanian Ministry of Science and Education for providing additional funding of such conference. Special thanks go to the Prime-minister’s advisor for education, Prof. Dr. M. Tafaj, and to the Vice-Minister for Education, Prof. Dr. Adriana Gjonaj for their support and encouragement during the conference.

Finally, we want to thank all the participants in the conference, especially Prof. Vera Pless, who came despite her health at the time, Prof. Shparlinski who came all the way from Sydney and all the other lecturers. Particular thanks to all the authors who contributed to this volume.

We hope the volume will be useful to mathematicians, computer scientists, and engineers who need to explore such ties between algebra and coding theory and cryptography. Most of the papers focus on coding theory and some others in cryptography. While such topics were the main focus of the conference, we had lectures which focused more on theoretical aspects such as computational group theory, computational algebraic geometry, theta functions, etc. Such areas have always provided a furtile ground in the area of communications. We hope that such collection of papers will serve the scientific community in mathematics, computer science, and electrical engineering and foster closer relations among such communities.

T. Shaska and E. Hasimaj

Vlora, Albania

We describe the theory for additive codes over F₄ that are either cyclic or have a permutation automorphism of odd prime order. We particularly consider those codes that are self-orthogonal or self-dual under the trace inner product.

A formal notion of a Typ T of a self-dual linear code over a finite left R-module V is introduced which allows to give explicit generators of a finite complex matrix group, the associated Clifford-Weil group C(T) ≤ GL_|V| (C), such that the complete weight enumerators of self-dual isotropic codes of Type T span the ring of invariants of [Cscr ](T). This generalizes Gleason’s 1970 theorem to a very wide class of rings and also includes multiple weight enumerators (see Section 2.7), as these are the complete weight enumerators cwe_m (C) = cwe(R^m ⊗ C) of R^{m × m} -linear self-dual codes R^m ⊗ C ≤ (V^m)^N of Type T^m with associated Clifford-Weil group [Cscr ]_m(T) = [Cscr ](T^m). The finite Siegel Φ-operator mapping cwe_m(C) to cwe_m−1(C) hence defines a ring epimorphism Φ_m : Inv([Cscr ]_m(T)) ⇒ Inv([Cscr ]_m−1(T)) between invariant rings of complex matrix groups of different degrees. If R = V is a finite field, then the structure of [Cscr ]_m(T) allows to define a commutative algebra of [Cscr ]_m (T) double cosets, called a Hecke algebra in analogy to the one in the theory of lattices and modular forms. This algebra consists of self-adjoint linear operators on Inv([Cscr ]_m (T)) commuting with Φ_m. The Hecke-eigenspaces yield explicit linear relations among the cwe_m of self-dual codes C ≤ V^N.

In this series of three lectures delivered at the NATO Advanced Institute in Vlora, Albania, April 28-May 9, 2008, we present new error-correcting algorithms for geometric Goppa codes, based on rank-2 vector bundles over an algebraic curve. We review the construction of moduli spaces of vector bundles and relevant stratifications and give examples for the Klein curve. We propose questions of algebraic geometry that could be answered using coding theory and vice versa.

Code synchronization is an important component of reliable data transmission. The paper surveys recent direct constructions and algorithms for finding optimal syncronizable codes based on combinatorial designs.

These lecture notes are based on a series of three lectures given at the NATO Advanced Study Institute on New Challenges in Digital Communications in Vlora, Albania, 2008. The goal is to provide an elementary approach to elliptic and hyperelliptic curve cryptography with emphasis on the underlying mathematical problems. The first lecture entitled “Computational number theory, cryptography, and curves” provides selected problems from basic cryptographic schemes and shows why cryptography and computational number theory are so intertwined. In the second lecture entitled “Some (new) attacks to the elliptic curve discrete logarithm problem”, various attacks are presented and discussed. The last lecture is entitled “Real hyperelliptic curves”. It describes the use of hyperelliptic curves in cryptography and is a more specialized topic covering various new results on the real model of hyperelliptic curves. We only provide the lecture notes for the first lecture in this contribution. The other lecture notes will be made available through other journal publications.

This paper deals with products of moderate-size primes, familiarly known as smooth numbers. Smooth numbers play an crucial role in information theory, signal processing and cryptography.

We present various properties of smooth numbers relating to their enumeration, distribution and occurrence in various integer sequences. We then turn our attention to cryptographic applications in which smooth numbers play a pivotal role.

Let X and Y be compact Riemann surfaces and let φ : X ⇒ Y be a ramified covering of a finite degree n. Let [Pscr ]_Y ⊂ Y be a finite set of points that includes all branch points of φ and let [Pscr ]_X = φ⁻¹([Pscr ]_Y). Let X₀ = X \ [Pscr ]_X and Y₀ = Y \ [Pscr ]_Y. Pick a base point y ∊ Y₀ and let x ∊ φ⁻¹(y). Since the restriction of φ to X₀ is a covering, it induces an embedding φ^* of π₁(X₀, x) into π₁(Y₀, y) as a subgroup of index n. We describe an algorithm that, given canonical generators of π₁(Y₀, y), computes canonical generators of π₁(X₀, x). The monodromy group G of the covering φ is naturally isomorphic to the factor group of π₁(Y₀, y) over its largest normal subgroup contained in φ^*(π₁(X₀, x)). In light of this our algorithm can be used to compute standard generators for subgroups of G. The algorithm is implemented in GAP, and it was used to determine the containment among the Hurwitz loci of Riemann surfaces of low genus.

Let χ be an irreducible, smooth, projective curve of genus g ≥ 2 defined over the complex field C. Then there is a covering π : χ → P¹, where P¹ denotes the projective line. The problem of expressing branch points of the covering π in terms of the transcendentals (period matrix, thetanulls, e.g.) is classical. It goes back to Riemann, Jacobi, Picard and Rosenhein. Many mathematicians, including Picard and Thomae, have offered partial treatments for this problem. In this work, we address the problem for cyclic curves of genus 2, 3, and 4 and find relations among theta functions for curves with automorphisms. We consider curves of genus g > 1 admitting an automorphism σ such that χ^σ has genus zero and σ generates a normal subgroup of the automorphism group Aut(χ) of χ.

To characterize the locus of cyclic curves by analytic conditions on its Abelian coordinates, in other words, theta functions, we use some classical formulas, recent results of Hurwitz spaces, and symbolic computations, especially for genera 2 and 3. For hyperelliptic curves, we use Thomae’s formula to invert the period map and discover relations among the classical thetanulls of cyclic curves. For non hyperelliptic curves, we write the equations in terms of thetanulls.

Fast genus 2 curve arithmetic in the Jacobian of the curve is used in cryptography and is based on inverting the moduli map for genus 2 curves and on some other relations on theta functions. We determine similar formulas and relations for genus 3 hyperelliptic curves and offer an algorithm for how this can be done for higher genus curves. It is still to be determined whether our formulas for g = 3 can be used in cryptographic applications as in g = 2.

In this paper we consider some properties of stream ciphers related to arithmetical dynamical systems defined in [41] over commutative ring K. We modify the stream cipher algorithm proposed in [40] by adding the key management block based on the idea of “hidden discrete logarithm”. The straightforward generalization of such encryption can be used in a public key mode. We introduce much more general algorithms in terms of automata related to Directed Algebraic Graphs with High Girth Indicator. In finite case we use only directed graphs of irreflexive binary relations such that numbers of inputs and outputs are the same for each node (balanced directed graphs). The families of such regular graphs of bounded degree with growing girth indicator and the size which is close to the maximal possible value (or order close to minimum) can be used for the design of encryption algorithm. One of the important parameters of the Turing machine related to the family is the speed of growth of the girth indicator. Natural upper bound for such speed can be obtained in terms of Extremal graph theory for balanced directed graphs which is motivated be Erdös’ Even Circuit Theorem which bounds the size of a simple graph without even cycle. Explicit constructions of such families can be used not only in Cryptography but in the Coding Theory as well.

The family of infinite algebraic directed graphs with the large girth indicator can be defined over infinite commutative ring K. Some theoretical examples of encryption algorithms related to such families are considered in the case of K = Z and Gaussian complex numbers. They use prime generating polynomials (Matijasevic’s polynomials) and can be implemented on classical Turing machine or Probabilistic machine (Quantum computer, in particular).