Ebook: Information Security, Coding Theory and Related Combinatorics

This book contains papers based on lectures presented at the NATO Advanced Study Institute “Information Security and Related Combinatorics”, held in the beautiful town of Opatija at the Adriatic Coast of Croatia from May 31 to June 11, 2010. On behalf of all participants, we would like to thank the NATO Science for Peace and Security Programme for providing funds for the conference, as well as the local sponsors, which included the Ministry of Science and Education of the Republic of Croatia, the Croatian Academy of Sciences and Arts, the Primorsko-goranska County, the University of Rijeka and its Mathematics Department, the Foundation of the University of Rijeka, the Society of Mathematicians and Physicists, the Login Co., the Opatija Tourist Board, the City of Opatija, the City of Rijeka, and Brodokomerc.nova.

The Advanced Study Institute had fourteen lecturers: K.T. Arasu (USA), C. Colbourn (USA), F. Fuji-Hara (Japan). W. Haemers (The Netherlands), M. Jimbo (Japan), J.D. Key (USA), H. Kharaghani (Canada), C. Lam (Canada), S. Magliveras, (USA), J. Moori (South Africa), T. Shaska (USA), L. Storme (Belgium), V.D. Tonchev (USA), R. Wilson (USA), and was attended by over 60 graduate students and junior scientists from Albania, Armenia, Belgium, Bosnia and Herzegovina, Bulgaria, Croatia, Germany, Italy, Macedonia, The Netherlands, Russia, Turkey, and USA.

The unifying theme of the conference was combinatorial mathematics used in applications related to information security, cryptography, and coding theory.

The book will be of interest to mathematicians, computer scientists and engineers working in the area of digital communications, as well as to researchers and graduate students who are willing to learn more about the applications of combinatorial mathematics to problems arising in communications and information security. The majority of papers are surveys on topics that are subject to current research and are written in a tutorial text book style that makes this volume a good source as an additional text for a course in discrete mathematics or applied combinatorics. The book can be used in graduate courses of applied combinatorics with a focus on coding theory and cryptography.

Dean Crnković and Vladimir Tonchev

The design of a large number of cryptographic primitives is based on the intractability of the traditional discrete logarithm problem (tDLP). However, the well known quantum algorithm of P. Shor [9] solves the tDLP in polynomial time, thus rendering all cryptographic schemes based on tDLP ineffective, should quantum computers become a practical reality. In [5] M. Sramka et al. generalize the DLP to arbitrary finite groups. The DLP for a non-abelian group is based on a particular representation of a chosen family of groups, and a choice of a class of generators for these groups. In this paper we show that for PSL(2, p) = 〈α, β〉, p an odd prime, certain choices of generators (α, β) must be avoided to insure that the resulting generalized DLP is indeed intractable. For other types of generating pairs we suggest possible cryptanalytic attacks, reducing the new problem to the earlier case. We note however that the probability of success is asymptotic to 1/p as p → ∞. The second part of the paper summarizes our successful attack of the SL(2, 2ⁿ) based Tillich Zémor cryptographic hash function [2], and show how to construct collisions between palindromic strings of length 2n + 2.

A rooted tree is an ordinary tree with an equivalence condition: two trees are the same if and only if one can be transformed into the other by reordering subtrees. In this paper, we construct a bijection and use it to generate rooted trees (or forests) of any specified nodecount m uniformly at random. As an application, Raddum and Semaev [6] Raddum and Semaev propose a technique to solve systems of polynomial equations over ² as occurring in algebraic attacks on block ciphers. This approach is known as MRHS. In [3] Geiselmann, Matheis, and Steinwandt propose an ASIC hardware design to implement MRHS, and they show that the use of ASICs seems to enable significant performance gains over a software implementation of MRHS. What hasn't been asserted is the total time complexity of their platform, though individual components' runtimes are provided. If one supposes that deletions in MRHS occur as rooted trees generated uniformly at random, then one application of the proposed algorithm would be to contribute to such a time complexity; experiments are generated to provide statistical averages of key quantities.

Let Σ = {0, 1} be the binary alphabet, and A = {0, 01, 11} be the set of three strings 0, 01, 11 over Σ. Let A^* denote the Kleene closure of A, ⁰ the set of nonnegative integers, and ⁺ the set of positive integers. A sequence in A^* is called a Jacobsthal binary sequence. Let J(n) denote the set of Jacobsthal binary sequences of length n. For k ∊ ⁺, {s₁, s₂, . . . , s_k} ⊂ ⁰, and n − 1 ≥ s₁ > s₂ > .. . > s_k ≥ 0, let J₁(n; s₁, s₂, . . . , s_k) denote the subset J₁(n; s₁, s₂, . . . , s_k) = {a_n−1a_n−2 . . . a₁a₀ ∊ J(n) : a_si = 1 (1 ≤ i ≤ k)}, of J(n), and let N₁(n; s₁, s₂, . . . , s_k) = |J₁(n; s₁, s₂, . . . , s_k)|. When k = 1, a formula for N₁(n; s) has been derived recently. In this paper we consider the general case of N₁(n; s₁, s₂, . . . , s_k), and study some other special types of Jacobsthal binary sequences. Some identities involving these numbers are also given.

We present in this article the basic properties of projective geometry, coding theory, and cryptography, and show how finite geometry can contribute to coding theory and cryptography. In this way, we show links between three research areas, and in particular, show that finite geometry is not only interesting from a pure mathematical point of view, but also of interest for applications. We concentrate on introducing the basic concepts of these three research areas and give standard references for all these three research areas. We also mention particular results involving ideas from finite geometry, and particular results in cryptography involving ideas from coding theory.

Genus 2 curves have been an object of much mathematical interest since eighteenth century and continued interest to date. They have become an important tool in many algorithms in cryptographic applications, such as factoring large numbers, hyperelliptic curve cryptography, etc. Choosing genus 2 curves suitable for such applications is an important step of such algorithms. In existing algorithms often such curves are chosen using equations of moduli spaces of curves with decomposable Jacobians or Humbert surfaces.

In these lectures we will cover basic properties of genus 2 curves, moduli spaces of (n,n)-decomposable Jacobians and Humbert surfaces, modular polynomials of genus 2, Kummer surfaces, theta-functions and the arithmetic on the Jacobians of genus 2, and their applications to cryptography. The lectures are intended for graduate students in algebra, cryptography, and related areas.

The explicit construction of covering arrays arises in many disparate applications in which factors or components interact. Despite this, current computational tools are effective only when the number of factors is small, while probabilistic methods are typically effective only when the number of factors is very large. Consequently combinatorial constructions have played, and continue to play, a significant role. Although some direct constructions from codes, Steiner systems, Hadamard matrices, and arrays over the finite field provide very useful examples, the workhorses of the combinatorial methods are the recursive constructions. There are two main classes of recursive techniques, the cut-and-paste or Roux-type constructions, and the column replacement techniques. After describing both for strength two, the focus is on column replacement techniques. In particular, constructions that use hash families to select columns from smaller covering arrays are examined, in order to understand the interplay among properties of the hash families and covering arrays needed to produce effective constructions. This leads to specializations both of hash families and covering arrays that merit further investigation.

Binary perfect sequences and their variations have applications in various areas such as signal processing, synchronizing and distance measuring radars. This survey discusses their p-ary analogs, other variations and related matters. Many new results are also presented.

Recent advances in technology have produced a requirement for new implementations of good error-correcting codes. Such applications of codes also require efficient encoding and decoding methods.

The method of permutation decoding was first developed by Mac-Williams in the early 60's and can be used when a code has a sufficiently large automorphism group to ensure the existence of a set of automorphisms, called a PD-set, that has some specific properties.

We describe here the method, and why it works, and give a short survey of permutation decoding using codes that arise from combinatorial structures such as graphs, designs and finite geometries, including some recent results in the search for PD-sets.

We will discuss two methods for constructing codes and designs from finite groups (mostly simple finite groups). This is a survey of the collaborative work by the author with J D Key and B Rorigues.

Let G be a finite group acting primitively on the sets Ω₁ and Ω₂. We describe a construction of 1-designs with block set Ω₁ and block set Ω₂, having G as an automorphism group. Applying this construction method we obtain a unital 2-(q³+1, q+1, 1), and a semi-symmetric (q⁴−q³+q², q²−q, (1)) from the unitary group U₃(q), where q = 3, 4, 5, 7. From the unital and the semi-symmetric design we build a projective plane PG(2, q²). Further, we describe other combinatorial structures constructed from these unitary groups and structures constructed from U₄(2), U₄(3) and L₂(49).

We also construct self-orthogonal codes obtained from the row span over ₂ or ₃ of the incidence (resp. adjacency) matrices of mostly self-orthogonal designs (resp. strongly regular graphs) defined by the action of the simple unitary groups U₃(q) for q = 3, 4, 7 and U₄(q) for q = 2, 3 and the linear group L₂(49) on the conjugacy classes of some of their maximal subgroups. Some of the codes are optimal or near optimal for the given length and dimension.

The adjacency matrix of a graph can be interpreted as the incidence matrix of a design, or as the generator matrix of a binary code. Here these relations play a central role. We consider graphs for which the corresponding design is a (symmetric) block design or (group) divisible design. Such graphs are strongly regular (in case of a block design) or very similar to a strongly regular graph (in case of a divisible design). Many constructions and properties for these kind of graphs are obtained. We also consider the binary code of a strongly regular graph, work out some theory and give several examples.

The theory of error-correcting codes is a vast and fast-moving area with many open problems. The objective of this paper is to survey where the current boundaries of knowledge are in a few selected areas, by listing the smallest unsolved cases. Our hope is that these lists will motivate further computational to move these boundaries.

Quantum jump codes were introduced by Alber et al. (2001). Quantum jump codes have a close connection with combinatorial designs called t-SEED (t-spontaneaus emission error design). In this paper, we give a brief survey of quantum jump codes together with some new results. Firstly, fundamental properties of a t-error correcting quantum jump code are described. Secondly, a few examples of jump codes are given and an upper bound on the dimension of a jump code with a fixed length and given error correcting ability is derived. A relation between a t-SEED and a jump code is discussed and various constructions of t-SEEDs are given.

Mutually unbiased unit Hadamard (MUUH) matrices have been studied for almost 40 years. Recent interest in such matrices has been motivated by their applications to quantum information theory. In this paper, we introduce the class of mutually unbiased complex Hadamard (MUCH) matrices having as sntries fourth roots of unity. The number of MUCH matrices of order 2n, n odd, is at most 2, and the bound is attained for n = 1,5,9. Certain pairs of mutually unbiased complex Hadamard matrices of order m can be used to construct pairs of unbiased real Hadamard matrices of order 2m. We then turn our attention to the class of mutually unbiased real Hadamard matrices of order 16n² which seem to be the most interesting ones. Mutually unbiased weighing (MUW) matrices are introduced for the first time. Further study of these objects look quite promising.

In this paper, we give a survey of multi-structured designs and their various applications. Multi-structured designs are block designs with additional structure imposed on the blocks. Combinatorial conditions of the further block structure depend on applications. Examples of multi-structured designs are nested designs, row-column designs, splitting design, etc. Their constructions have been independently studied for a long time and often use similar techniques. Cyclic multi-structured designs are related to various types of sequences which have many applications to modern communications. The paper consists of three parts. The first part deals with classical multi-structured designs which are used in experimental designs and authentication systems. The second part reviews several applications to optical and wireless communications which use cyclic multi-structured designs. Finally, in the third part, we discuss algebraic and geometric construction methods which are commonly used for many types of multi-structured designs.

The first infinite families of symmetric designs were obtained from finite projective geometries, Hadamard matrices, and difference sets. Some of these symmetric designs have applications to coding theory, cryptography, and authentication schemes. Recently, new ideas have been introduced in constructing designs using balanced generalized weighing matrices and regular Hadamard matrices. These have led to several new families of symmetric designs and related configurations such as quasi-residual designs. The first part of this paper aims to survey these new developments as well as recent results about families of symmetric designs. The second part of the paper concerns quasi-residual designs and their non-embeddability.

The Smith normal form and the invariant factors of an integer matrix are introduced. We give selected examples of how invariant factors, a chain of linear codes, and self-dual codes have appeared and been applied in the theory of combinatorial designs. In the latter part of these notes, we are concerned with diagonal forms of various incidence matrices arising from designs and uniform hypergraphs. Results on diagonal forms of such matrices can be applied to a certain zero-sum Ramsey-type problem.

The coding-theoretical interest in combinatorial designs defined by subspaces of a finite geometry was motivated in the 1960's by their use for the construction of majority-logic decodable codes. In 1973, Hamada computed the ranks of the incidence matrices of finite geometry designs over the underlying finite field and made the conjecture that geometric designs have minimum rank among all designs with the given parameters. In all proved cases of the conjecture, the geometric designs not only have minimum rank, but are also the unique (up to isomorphism) designs of minimum rank. Until recently, only a handful of non-geometric designs were known that share the same rank with geometric designs. This paper discusses some recently discovered infinite families of non-geometric designs that have the same parameters and the same rank as certain geometric designs.