Applied Algebra, Algebraic Algorithms and Error-Correcting Codes

There is a rich interplay between coding theory and computational complexity theory that has enriched both disciplines over the years. In particular, list decoding and closely related notions have been instrumental in several advances in explicit constructions of combinatorial objects with strong “random-like” properties, such as expander graphs, randomness extractors, and pseudorandom generators. Our aim here is to present

a unified list-decoding-centric view of the definition of these objects, and

the details of recent work due to the author, C. Umans, and S. Vadhan [3], where this viewpoint yields powerful results, namely the construction of unbalanced bipartite graphs with very strong expansion properties based on the list-decodable codes due to Parvaresh and Vardy [4]. In turn these expanders yield simple constructions of randomness extractors that are optimal up to constant factors.

The filter generator consists of a linear feedback shift register (LFSR) and a Boolean filtering function that combines bits from the shift register to create a key stream. The nonlinear combiner generator employs several (LFSRs) and a Boolean function that combines bit from all the registers to generate the key stream. A new attack on the filter generator has recently been described by Rønjom and Helleseth who also extended the attack to linear feedback shift registers over an extension field

GF

(2

m

). Some extensions and improvements of the attacks to the filter generator have been given by Rønjom, Gong and Helleseth. The purpose of this paper is to give a short overview of these attacks and to discuss how to extend these attacks to the nonlinear combiner generator.

In the last decade two old methods for decoding linear block codes have gained considerable interest,

iterative

decoding

as first described by Gallager in [1] and

list

decoding

as introduced by Elias [2]. In particular iterative decoding of lowdensity parity-check (LDPC) codes, has been an important subject of research, see e.g. [3] and the references therein. “Good“ LDPC codes are often randomly generated by computer, but recently codes with an algebraic or geometric structure have also been considered e.g [3] and [4]. The performance of the iterative decoder is typically studied by simulations and a theoretical analysis is more difficult.

Edwards curves have attracted great interest for several reasons. When curve parameters are chosen properly, the addition formulas use only 10

M

 + 1

S

. The formulas are

strongly unified

, i.e., work without change for doublings; even better, they are

complete

, i.e., work without change for all inputs. Dedicated doubling formulas use only 3

M

 + 4

S

, and dedicated tripling formulas use only 9

M

 + 4

S

.

This paper introduces

inverted Edwards coordinates

. Inverted Edwards coordinates (

X

1

:

Y

1

:

Z

1

) represent the affine point (

Z

1

/

X

1

,

Z

1

/

Y

1

) on an Edwards curve; for comparison, standard Edwards coordinates (

X

1

:

Y

1

:

Z

1

) represent the affine point (

X

1

/

Z

1

,

Y

1

/

Z

1

).

This paper presents addition formulas for inverted Edwards coordinates using only 9

M

 + 1

S

. The formulas are not complete but still are strongly unified. Dedicated doubling formulas use only 3

M

 + 4

S

, and dedicated tripling formulas use only 9

M

 + 4

S

. Inverted Edwards coordinates thus save 1

M

for each addition, without slowing down doubling or tripling.

We will discuss two different but related topics. We first give a connection between the Fourier spectrum of Boolean functions and subspaces of skew-symmetric subspaces where each nonzero element has a lower bound on its rank. Secondly, we discuss some connections between bent and near-bent functions.

Under the notion of list decoding, the decoder is allowed to output a small list of codeword such that the transmitted codeword is present in the list. Even though combinatorial limitations on list decoding had been known since the 1970’s, there was essentially no algorithmic progress till the breakthrough works of Sudan [14] and Guruswami-Sudan [11] in the mid to late 1990’s. There was again a lull in algorithmic progress till a couple of recent papers [12,8] closed the gap in our knowledge about combinatorial and algorithmic limitations of list decoding (for codes over large alphabets). This article surveys these latter algorithmic progress.

It is well known that there is an intimate connection between algebraic descriptions of linear block codes in the form of generator or parity-check matrices, and combinatorial descriptions in the form of trellises. A conventional trellis for a linear code

C

is a directed labelled layered graph with unique start and final nodes, and all paths from the start to the final node spell out codewords. The trellis can be thought of as being laid out on a linear time axis. There is a rich theory of conventional trellises for linear block codes. Every linear block code has a unique minimal trellis, and several seemingly different constructions proposed, all yield this minimal trellis, which simultaneously minimizes all measures of trellis complexity. Tail-biting trellises are defined on circular time axes, and the underlying theory is a little more involved as there is no unique minimal trellis. Interestingly, the complexity of a tail-biting trellis can be much lower than that of the best possible conventional trellis. We extend the well-known BCJR construction for conventional trellises to linear tail-biting trellises, introducing the notion of a

displacement

matrix

. This implicitly induces a coset decomposition of the code. The BCJR-like labeling scheme yields a very simple specification for the tail-biting trellis for the dual code, with the dual trellis having the same statecomplexity profile as that of the primal code . We also show that the algebraic specification of Forney for state spaces of conventional trellises has a natural extension to tail-biting trellises. Finally we provide an automata-theoretic view of trellises and display some connections between well known results in finite automata and trellis theory.

The well-known Tsfasman-Vladut-Zink (TVZ) theorem states that for all prime powers q =

l

2

 ≥ 49 there exist sequences of linear codes over

${\mathbb{F}_q}$

with increasing length whose limit parameters

R

and

δ

(rate and relative minimum distance) are better than the Gilbert-Varshamov bound. The basic ingredients in the proof of the TVZ theorem are sequences of modular curves (or their corresponding function fields) having many rational points in comparison to their genus (more precisely, these curves attain the so-called Drinfeld-Vladut bound). Starting with such a sequence of curves and using Goppa’s construction of algebraic geometry (AG) codes, one easily obtains sequences of linear codes whose limit parameters beat the Gilbert-Varshamov bound.

We generalize Sudan’s list decoding algorithm without multiplicity to evaluation codes coming from arbitrary order domains. The number of correctable errors by the proposed method is larger than the original list decoding without multiplicity.

In this paper, codes which reduce the peak-to-average power ratio (PAPR) in multi-code code division multiple access (MC-CDMA) communication systems are studied. It is known that using bent functions to define binary codewords gives constant amplitude signals. Based on the concept of quarter bent functions, a new inequality relating the minimum order of terms of a bent function and the maximum Walsh spectral magnitude is proved, and it facilitates the generalization of some known results. In particular, a new simple proof of the non-existence of the homogeneous bent functions of degree

m

in 2

m

boolean variables for

m

 > 3 is obtained without invoking results from the difference set theory. We finally propose a new coding approach to achieve the constant amplitude transmission of codeword length 2

m

for both even

m

as well as odd

m

.

We compute the Walsh spectrum and hence the nonlinearity of a new family of quadratic multi-term APN functions. We show that the distribution of values in the Walsh spectrum of these functions is the same as the Gold function.

The code length of Tardos’s collusion-secure fingerprinting code (STOC’03) is of theoretically minimal order with respect to the number of malicious users (pirates); however, the constant factor should be further reduced for practical implementation. In this paper we give a collusion-secure fingerprinting code by mixing recent two improvements of Tardos code and modifying their pirates tracing algorithms. Our code length is significantly shorter than Tardos code, especially in the case of fewer pirates. For example, the ratio of our length relative to Tardos code in some practical situation with 4 pirates is 4.33%; while the lowest among the preceding codes in this case (S̆korić et al., 2007) is 9.87%.

We study crossed product algebras of degree 4, and present a new space-time code construction based on a particular crossed product division algebra which exhibits very good performance.

Here we study a weakness of the RC4 Key Scheduling Algorithm (KSA) that has already been noted by Mantin and Mironov. Consider the RC4 permutation

S

of

N

(usually 256) bytes and denote it by

S

N

after the KSA. Under reasonable assumptions we present a simple proof that each permutation byte after the KSA is significantly biased (either positive or negative) towards many values in the range 0, ...,

N

 − 1. These biases are independent of the secret key and thus present an evidence that the permutation after the KSA can be distinguished from random permutation without any assumption on the secret key. We also present a detailed empirical study over Mantin’s work when the theoretical formulae vary significantly from experimental results due to repetition of short keys in RC4. Further, it is explained how these results can be used to identify new distinguishers for RC4 keystream.

The number of correctable/uncorrectable errors of weight half the minimum distance plus one for the first-order Reed-Muller codes is determined. From a cryptographic viewpoint, this result immediately leads to the exact number of Boolean functions of

m

variables with nonlinearity 2

m

 − 2

 + 1. The notion of

larger half

and

trial set

, which is introduced by Helleseth, Kløve, and Levenshtein to describe the monotone structure of correctable/uncorrectable errors, plays a significant role in the result.

In this paper, we propose a new method for fault tolerant computation over

GF

(2

k

) for use in public key cryptosystems. In particular, we are concerned with the active side channel attacks, i.e., fault attacks. We define a larger ring in which new computation is performed with encoded elements while arithmetic structure is preserved. Computation is decomposed into parallel, mutually independent, identical channels, so that fault effects do not spread to the other channels. By assuming certain fault models, our proposed model provides protection against their error propagation. Also, we provide an analysis of the error detection and correction capabilities of our proposed model.

Finding new classes of permutation polynomials is a challenging problem. Blockhuis at al. investigated the permutation behavior of polynomials of the form

$\sum_{i=0}^{n-1}a_iX^{2^i+1}$

over

${\mathbb F}_{{2^n}}$

. In this paper, we extend their results and propose as a new conjecture that if

n

 = 2

e

then

X

2

is the only unitary permutation polynomial of this type.

We describe some constructions of orthonormal lattices in totally real subfields of cyclotomic fields, obtained by endowing their ring of integers with a trace form. We also describe constructions of quaternion division algebras over such fields. Orthonormal lattices and quaternion division algebras over totally real fields find use in wireless networks in ultra wideband communication, and we describe the application.

New quaternary Plotkin constructions are given and are used to obtain new families of quaternary codes. The parameters of the obtained codes, such as the length, the dimension and the minimum distance are studied. Using these constructions new families of quaternary Reed-Muller codes are built with the peculiarity that after using the Gray map the obtained ℤ

4

-linear codes have the same parameters as the codes in the classical binary linear Reed-Muller family.

This paper proposes a joint coding with three functions: source coding, channel coding, and public-key encryption. A codeword is simply generated as a product of an encoding matrix and a sparse information word. This encoding method has much lower encoding complexity than the conventional coding techniques in which source coding, encryption, and channel coding are successively applied to an information word. The encoding matrix is generated by using two linear error control codes and randomly generated nonsingular matrices. Encryption is based on the intractableness of factorizing a matrix into randomly constructed factor matrices, and of decoding an error control code defined by a random parity-check matrix. Evaluation shows that the proposed joint coding gives a lower bit error rate and a superior compression ratio than the conventional codings.

The notion of key-privacy for encryption schemes was formally defined by Bellare, Boldyreva, Desai and Pointcheval in Asiacrypt 2001. This security notion has the application possibility in circumstances where anonymity is important. In this paper, we investigate the key-privacy issues of McEliece public-key encryption and its significant variants. To our best knowledge, it is the first time to consider key-privacy for such code-based public-key encryption, in the literature. We examine that the key-privacy is not available in the plain McEliece scheme, but can be achieved by some modification, with showing a rigorous proof. We believe that key-privacy confirmation will further magnify the application of McEliece and other code-based cryptography.

Consider a pair of correlated Gaussian sources (

X

1

,

X

2

). Two separate encoders observe the two components and communicate compressed versions of their observations to a common decoder. The decoder is interested in reconstructing a linear combination of

X

1

and

X

2

to within a mean-square distortion of

D

. We obtain an inner bound to the optimal rate-distortion region for this problem. A portion of this inner bound is achieved by a scheme that reconstructs the linear function directly rather than reconstructing the individual components

X

1

and

X

2

first. This results in a better rate region for certain parameter values. Our coding scheme relies on lattice coding techniques in contrast to more prevalent random coding arguments used to demonstrate achievable rate regions in information theory. We then consider the case of linear reconstruction of

K

sources and provide an inner bound to the optimal rate-distortion region. Some parts of the inner bound are achieved using the following coding structure: lattice vector quantization followed by “correlated” lattice-structured binning.

We review a binary sequence based on the generalized cyclotomy of order 2 with respect to

p

3

, where

p

is an odd prime. Linear complexities, minimal polynomials and autocorrelation of these sequences are computed.

Given a linear code

${\mathcal C}$

, the fundamental problem of trellis decoding is to find a coordinate permutation of

${\mathcal C}$

that yields a code

${\mathcal C}'$

whose minimal trellis has the least state-complexity among all codes obtainable by permuting the coordinates of

${\mathcal C}$

. By reducing from the problem of computing the pathwidth of a graph, we show that the problem of finding such a coordinate permutation is NP-hard, thus settling a long-standing conjecture.

We analyze the lattice structure and linear complexity of a new inversive pseudorandom number generator recently introduced by Niederreiter and Rivat. In particular, we introduce a new lattice test which is much stronger than its predecessors and prove that this new generator passes it up to very high dimensions. Such a result cannot be obtained for the conventional inversive generator with currently known methods. We also analyze the behavior of two explicit inversive generators under this new test and present lower bounds on the linear complexity profile of binary sequences derived from these three inversive generators.

Reed-Solomon (RS) codes over GF(2

m

) have traditionally been the most popular non-binary codes in almost all practical applications. The distance properties of RS codes result in excellent performance under hard-decision bounded-distance decoding. In this work, we consider certain subcodes of RS codes over GF(

q

m

) whose

q

-ary traces are BCH codes over GF(

q

). The properties of these subcodes are studied and low-complexity hard-decision and soft-decision decoders are proposed. The decoders are analyzed, and their performance is compared with that of comparable RS codes. Our results suggest that these subcodes of RS codes could have some advantages when compared to RS codes.

The aim of this paper is to show the connection between certain, previously constructed multi-block and asymmetric space-time codes. The Gram determinants of the two constructions coincide, and hence the corresponding lattices share the same density. Using the notion of density, we define the normalized minimum determinant and give an implicit lower bound depending on the center of the cyclic division algebra in use. The calculation of the normalized minimum determinant is then performed in practice by using explicit code constructions.

Guruswami and Patthak, among many results, gave a randomized algorithm for computing the evaluation of regular functions of the Garcia-Stichtenoth tower at a large degree place. An algorithm, along the same lines, for Bezerra-Garcia tower is given. This algorithm uses Kummer theorem.

The design of signal constellations for multi-antenna radio communications naturally leads to the problem of finding lattices of square complex matrices with a fixed minimum squared determinant. Since [5] cyclic division algebras, their orders and related structures have become standard material for researchers seeking to construct good MIMO-lattices. In recent submissions [3], [8] we studied the problem of identifying those cyclic division algebras that have the densest possible maximal orders. That approach was based on the machinery of Hasse invariants from class field theory for classifying the cyclic division algebras. Here we will recap the resulting lower bound from [3], preview the elementary upper bounds from [4] and compare these with some suggested constructions. As the lattices of the shape

E

8

are known to be the densest (with respect to the usual Euclidean metric) in an 8-dimensional space it is natural to take a closer look at lattices of 2x2 complex matrices of that shape. We derive a much tighter upper bound to the minimum determinant of such lattices using the theory of invariants.

The cross-realm client-to-client password-based authenticated key exchange (C2C-PAKE) is protocol which two clients in two different realms with different passwords exchange a session key through their corresponding servers. Recently, a provably secure cross-realm C2C-PAKE scheme with the optimal number of rounds for a client is pointed out that the scheme is insecure against an undetectable on-line dictionary attack and an unknown-key share attack. In this paper, we propose a new cross-realm C2C-PAKE scheme with the optimal number of rounds for a client, which has resistances to previously considered attacks which should be prevented, including undetectable on-line dictionary attacks and unknown-key share attacks. Moreover, our scheme assumes no pre-established secure channels between different realms, but just basic setups of ID-based systems.

Let

F

n

be the binary

n

-cube, or binary Hamming space of dimension

n

, endowed with the Hamming distance, and

${\cal E}^n$

(respectively,

${\cal O}^n$

) the set of vectors with even (respectively, odd) weight. For

r

 ≥ 1 and

x

 ∈ 

F

n

, we denote by

B

r

(

x

) the ball of radius

r

and centre

x

. A code

C

 ⊆ 

F

n

is said to be

r

-identifying if the sets

B

r

(

x

) ∩ 

C

,

x

 ∈ 

F

n

, are all nonempty and distinct. A code

$C\subseteq {\cal E}^n$

is said to be

r

-discriminating if the sets

B

r

(

x

) ∩ 

C

,

$x\in {\cal O}^n$

, are all nonempty and distinct. We show that the two definitions, which were given for general graphs,are equivalent in the case of the Hamming space, in the following sense: for any odd

r

, there is a bijection between the set of

r

-identifying codes in

F

n

and the set of

r

-discriminating codes in

F

n

 + 1

.

In this paper we present a theoretical construction of Rotation Symmetric Boolean Functions (RSBFs) on odd number of variables with maximum possible algebraic immunity

(AI)

and further these functions are not symmetric. Our RSBFs are of better nonlinearity than the existing theoretical constructions with maximum possible

AI

. To get very good nonlinearity, which is important for practical cryptographic design, we generalize our construction to a construction cum search technique in the RSBF class. We find 7, 9, 11 variable RSBFs with maximum possible

AI

having nonlinearities 56, 240, 984 respectively with very small amount of search after our basic construction.

There are characteristics of Hadamard matrices that enable an exhaustive search using algorithmic techniques. The search derives primarily from the eigenvalues which are constant after the Hadamard matrix is multiplied by its transpose. Generally this would be a performance concern but there are additional properties that enable the eigenvalues to be predicted. Here an algorithm is given to obtain a Hadamard matrix from a matrix of 1s using optimisation techniques on a row-by-row basis.

The split-radix FFT computes a size-

n

complex DFT, when

n

is a large power of 2, using just

$4n\lg n-6n+8$

arithmetic operations on real numbers. This operation count was first announced in 1968, stood unchallenged for more than thirty years, and was widely believed to be best possible.

Recently James Van Buskirk posted software demonstrating that the split-radix FFT is

not

optimal. Van Buskirk’s software computes a size-

n

complex DFT using only

$(34/9+o(1))n\lg n$

arithmetic operations on real numbers. There are now three papers attempting to explain the improvement from 4 to 34/9: Johnson and Frigo,

IEEE Transactions on Signal Processing

, 2007; Lundy and Van Buskirk,

Computing

, 2007; and this paper.

This paper presents the “tangent FFT,” a straightforward in-place cache-friendly DFT algorithm having exactly the same operation counts as Van Buskirk’s algorithm. This paper expresses the tangent FFT as a sequence of standard polynomial operations, and pinpoints how the tangent FFT saves time compared to the split-radix FFT. This description is helpful not only for understanding and analyzing Van Buskirk’s improvement but also for minimizing the memory-access costs of the FFT.

The novel algebraic structure for the cyclic codes, Cyclic Multiplicative Groups (CMGs) over polynomial ring, is proposed in this paper. According to this algorithm, traditional cyclic codes can be considered as a subclass in these cyclic codes. With CMGs structure, more plentiful good cyclic code cosets can be found in any polynomial rings than other methods. An arbitrary polynomial in polynomial ring can generate cyclic codes in which length of codewords depend on order of the polynomial. Another advantage of this method is that a longer code can be generated from a smaller polynomial ring. Moreover, our technique is flexibly and easily implemented in term of encoding as well as decoding. As a result, the CMGs can contribute a new point of view in coding theory. The significant advantages of proposed cyclic code cosets can be applicable in the modern communication systems and crypto-systems.

The uniform distribution of the trace map lends itself very well to the construction of binary and non-binary codes from Galois fields and Galois rings. In this paper we study the distribution of the trace map with the argument

ax

2

over the Galois field

GF

(

p

,2). We then use this distribution to construct two-weight, self-orthogonal, trace codes.

Recently, 9-variable Boolean functions having nonlinearity 241, which is strictly greater than the bent concatenation bound of 240, have been discovered in the class of Rotation Symmetric Boolean Functions (RSBFs) by Kavut, Maitra and Yücel. In this paper, we present several 9-variable Boolean functions having nonlinearity of 242, which we obtain by suitably generalizing the classes of RSBFs and Dihedral Symmetric Boolean Functions (DSBFs). These functions do not have any zero in the Walsh spectrum values, hence they cannot be made balanced easily. This result also shows that the covering radius of the first order Reed-Muller code

R

(1, 9) is at least 242.

In this paper we consider some properties of quasi-cyclic codes over the integer residue rings. A quasi-cyclic code over ℤ

k

, the ring of integers modulo

k

, reduces to a direct product of quasi-cyclic codes over

${\mathbb{Z}}_{p_i^{e_i}}$

,

$k = \prod_{i=1}^s p_i^{e_i}$

,

p

i

a prime. Let

T

be the standard shift operator. A linear code

$\mathcal{C}$

over a ring

R

is called an

l

-quasi-cyclic code if

$T^l(c) \in \mathcal{C}$

, whenever

$ c\in \mathcal{C}$

. It is shown that if (

m

,

q

) = 1,

q

 = 

p

r

,

p

a prime, then an

l

-quasi-cyclic code of length

lm

over ℤ

q

is a direct product of quasi-cylcic codes over some Galois extension rings of ℤ

q

. We have discussed about the structure of the generator of a 1-generator

l

-quasi-cyclic code of length

lm

over ℤ

q

. A method to obtain quasi-cyclic codes over ℤ

q

, which are free modules over ℤ

q

, has been discussed.

We consider a generalization of the codes defined by norm and trace functions on finite fields introduced by Olav Geil. The codes in the new family still satisfy Geil’s duality properties stated for norm-trace codes. That is, it is easy to find a minimal set of parity checks guaranteeing correction of a given number of errors, as well as the set of monomials generating the corresponding code. Furthermore, we describe a way to find the minimal set of parity checks and the corresponding generating monomials guaranteeing correction at least of

generic

errors. This gives codes with even larger dimensions.

We prove an upper bound on the covering radius of linear codes over

${\mathbb{F}_q}$

in terms of their generalized Hamming weights. We show that this bound is strengthened if we know that the codes satisfy the chain condition or a partial chain condition. We show that this bound improves all prior bounds. Necessary conditions for equality are also presented.

Several applications of our bound are presented. We give tables of improved bounds on the covering radius of many cyclic codes using their generalized Hamming weights. We show that most cyclic codes of length ≤ 39 satisfy the chain condition or partial chain condition up to level 5. We use these results to derive tighter bounds on the covering radius of cyclic codes.

We examine the mechanism of homomorphic encryptions based on the subgroup membership problem. Using the mechanism, we construct a homomorphic encryption of a direct sum of groups.