In 2012, Diem introduced a new figure of merit for cryptographic sequences called expansion complexity. In this paper, we slightly modify this notion to obtain the so-called irreducible-expansion complexity which is more suitable for certain applications. We analyze both, the classical and the modified expansion complexity. Moreover, we also study the expansion complexity of the explicit inversive congruential generator.

We improve lower bounds on the k th-order nonlinear complexity of pseudorandom sequences over finite fields, including explicit inversive sequences and sequences obtained from Hermitian function fields, and we establish a probabilistic result on the behavior of the k th-order nonlinear complexity of random sequences over finite fields.

For a prime power q, let $\alpha_q$ be the standard function in the asymptotic theory of codes, that is, $\alpha_q(\delta)$ is the largest asymptotic information rate that can be achieved for a given asymptotic relative minimum distance $\delta$ of q-ary codes. In recent years the Tsfasman–Vlăduţ–Zink lower bound on $\alpha_q(\delta)$ was improved by Elkies, Xing, Niederreiter and Özbudak, and Maharaj. In this paper we show further improvements on these bounds by using distinguished divisors of global function fields. We also show improved lower bounds on the corresponding function $\alpha_q^{\rm lin}$ for linear codes.

In this correspondence, two classes of cyclotomic linear codes over GF(q) of order 3 are constructed and their weight distributions are determined. The two classes are two-weight codes and contain optimal codes. They are not equivalent to irreducible cyclic codes in general when q > 2.

We construct two families of authentication schemes using highly nonlinear functions on finite fields of characteristic 2. This leads to improvements on an earlier construction by Ding and Niederreiter if one chooses, for instance, an almost bent function as the highly nonlinear function

Recently, highly nonlinear functions have been successfully employed to construct authentication codes with and without secrecy. In this paper, we construct four classes of systematic authentication codes from perfect nonlinear functions and almost-perfect nonlinear functions. The systematic authentication codes presented in this paper are either better than existing codes or as good as the best codes known.

In this correspondence, we study disjoint linear codes and give constructions of families of disjoint linear codes based on algebraic function fields. It turns out that, for some parameters, our constructions improve on a result of Johansson and Pasalic.

We establish the existence of periodic sequences over a finite field which simultaneously achieve the maximum value (for the given period length) of the linear complexity and of the k-error linear complexity for small values of k. This disproves a conjecture of Ding, Xiao, and Shan (1991). The result is of relevance for the theory of stream ciphers.

Irreducible cyclic codes have been an interesting subject of study for many years. The weight distribution of some of them have been determined. We determine the minimum distance and certain weights of the duals of binary irreducible cyclic codes. We show that the weight distribution of these codes is determined by the cyclotomic numbers of certain order. As a byproduct, we describe a class of double-error correcting codes.

Rueppel (1986) conjectured that periodic binary sequences have expected linear complexity close to the period length N. In this paper, we determine the expected value of the linear complexity of N-periodic sequences explicitly and confirm Rueppel's conjecture for arbitrary finite fields. Cryptographically strong sequences should not only have a large linear complexity, but also the change of a few terms should not cause a significant decrease of the linear complexity. This requirement leads to the concept of the k-error linear complexity of N-periodic sequences. We present a method to establish a lower bound on the expected k-error linear complexity of N-periodic sequences based on the knowledge of the counting function /spl Nscr//sub N/,/sub 0/(c), i.e., the number of N-periodic sequences with given linear complexity c. For some cases, we give explicit formulas for that lower bound and we also determine /spl Nscr//sub N,0/(c).

Based on a construction of Xing, Niederreiter, and Lam (see ibid., vol.45, p.2498-2501, 1999), some new linear codes are found from suitable algebraic curves over finite fields. These codes have better parameters compared with Brouwer's table.

Based on curves over finite fields with many rational points, we present two constructions of linear codes from local expansions of functions at a fixed rational point. It turns out that codes from our constructions have the same bound on their parameters as Goppa's (1981) geometry codes. Furthermore, we prove that our second construction is equivalent to Goppa's construction. Finally, an additional construction of linear codes from maximal curves shows that these codes have better parameters than Goppa's geometry codes from maximal curves for a certain interval of parameters.

A generalization of algebraic-geometry codes based on function fields over finite fields with many places of small degree is presented. It turns out that many good linear codes can be obtained from these generalized algebraic-geometry codes. In particular, we calculate some examples of q-ary linear codes for q=2,3, 5. These examples show that many best possible linear codes can be found from our construction.

This note points out programs to implement Niederreiter's low-discrepancy sequences.

A distribution on n-bit strings is called $(\varepsilon ,e)$-locally random, if for every choice of $e \leqslant n$ positions the induced distribution on e-bit strings is in the $L_1 $-norm at most $\varepsilon $ away from the uniform distribution on e-bit strings. Local randomness in polynomial random number generators (RNG) that are candidate one-way functions is established. Let N be a squarefree integer and let $f_1 , \ldots ,f_\ell $ be polynomials with coefficients in $\mathbb{Z}_N = {\mathbb{Z} / {N\mathbb{Z}}}$. The RNG that stretches a random $x \in \mathbb{Z}_N $ into the sequence of least significant bits of $f_1 (x), \ldots ,f_\ell (x)$ is studied. It is shown that this RNG provides local randomness if for every prime divisor p of N the polynomials $f_1 , \ldots ,f_\ell $ are linearly independent modulo the subspace of polynomials of degree $ \leqslant 1$ in $\mathbb{Z}_p [x]$. Also established is local randomness in polynomial random function generators. This yields candidates for cryptographic hash functions. The concept of local randomness in families of functions extends the concept of universal families of hash functions by Carter and Wegman [J. Comput. System Sci., 18 (1979) pp. 143–154]. The proofs of the results rely on upper bounds for exponential sums.