Bundles, presemifields and nonlinear functions

Bundles are equivalence classes of functions derived from equivalence classes of transversals. They preserve measures of resistance to differential and linear cryptanalysis. For functions over GF(2 ⁿ ), affine bundles coincide with EA-equivalence classes. From equivalence classes (“bundles”) of presemifields of order p ⁿ , we derive bundles of functions over GF(p ⁿ ) of the form λ(x)*ρ(x), where λ, ρ are linearised permutation polynomials and * is a presemifield multiplication. We prove there are exactly p bundles of presemifields of order p ² and give a representative of each. We compute all bundles of presemifields of orders p ⁿ ≤ 27 and in the isotopism class of GF(32) and we measure the differential uniformity of the derived λ(x)*ρ(x). This technique produces functions with low differential uniformity, including PN functions (p odd), and quadratic APN and differentially 4-uniform functions (p = 2).     

A Characterization of Binary Bent Functions

A recent paper by Carlet introduces a general class of binary bent functions on (GF(2))ⁿ(neven) whose elements are expressed by means of characteristic functions (indicators) of (n/2)-dimensional vector-subspaces of (GF(2))ⁿ. An extended version of this class is introduced in the same paper; it is conjectured that this version is equal to the whole class of bent functions. In the present paper, we prove that this conjecture is true.     

Patterson-Wiedemann construction revisited

In 1983, Patterson and Wiedemann constructed Boolean functions on n=15 input variables having nonlinearity strictly greater than 2^n-1-2^(n-1)/2. Construction of Boolean functions on odd number of variables with such high nonlinearity was not known earlier and also till date no other construction method of such functions are known. We note that the Patterson-Wiedemann construction can be understood in terms of interleaved sequences as introduced by Gong in 1995 and subsequently these functions can be described as repetitions of a particular binary string. As example we elaborate the cases for n=15,21. Under this framework, we map the problem of finding Patterson-Wiedemann functions into a problem of solving a system of linear inequalities over the set of integers and provide proper reasoning about the choice of the orbits. This, in turn, reduces the search space. Similar analysis also reduces the complexity of calculating autocorrelation and generalized nonlinearity for such functions. In an attempt to understand the above construction from the group theoretic view point, we characterize the group of all GF(2)-linear transformations of GF(2^ab) which acts on PG(2,2^a).     

On hardware and software implementation of arithmetic in finite fields of characteristic 7 for calculation of pairings

We study scheme (hardware) and program (software) methods of multiplication of polynomials over fields of characteristic 7 in order to apply them to pairing-based cryptographic protocols on hyperelliptic curves of genus three. We consider hardware and software implementations of arithmetic in GF(7), GF(7²), GF(7 ⁿ ), GF(7⁷ⁿ ), and GF(7¹⁴ⁿ ) and estimate the complexity of corresponding schemes and programs.     

A New Characterization of Semi-bent and Bent Functions on Finite Fields*

We present a new characterization of semi-bent and bent quadratic functions on finite fields. First, we determine when a GF(2)-linear combination of Gold functions Tr(x²ⁱ+1) is semi-bent over GF(2ⁿ), n odd, by a polynomial GCD computation. By analyzing this GCD condition, we provide simpler characterizations of semi-bent functions. For example, we deduce that all linear combinations of Gold functions give rise to semi-bent functions over GF(2^p) when p belongs to a certain class of primes. Second, we generalize our results to fields GF(pⁿ) where p is an odd prime and n is odd. In that case, we can determine whether a GF(p)-linear combination of Gold functions Tr(x^pi+1) is (generalized) semi-bent or bent by a polynomial GCD computation. Similar to the binary case, simple characterizations of these p-ary semi-bent and bent functions are provided. Parts of this paper were presented at the 2002 IEEE International Symposium on Information Theory [10]     

Fast algorithms for determining the linear complexities of sequences over GF(p m) with the period 3n

In this paper, for the the primes p such that 3 is a divisor of p ? 1, we prove a result which reduces the computation of the linear complexity of a sequence over GF(p ^m) (any positive integer m) with the period 3n (n and p ^m ? 1 are coprime) to the computation of the linear complexities of three sequences with the period n. Combined with some known algorithms such as generalized Games-Chan algorithm, Berlekamp-Massey algorithm and Xiao-Wei-Lam-Imamura algorithm, we can determine the linear complexity of any sequence over GF(p ^m) with the period 3n (n and p ^m ? 1 are coprime) more efficiently.     

Recurrent Methods for Constructing Irreducible Polynomials over GF(2s)

The paper is devoted to some results concerning the constructive theory of the synthesis of irreducible polynomials over Galois fields GF(q), q=2^s. New methods for the construction of irreducible polynomials of higher degree over GF(q) from a given one are worked out. The complexity of calculations does not exceed O(n³) single operations, where n denotes the degree of the given irreducible polynomial. Furthermore, a recurrent method for constructing irreducible (including self-reciprocal) polynomials over finite fields of even characteristic is proposed.     

Sur le critère de propagation de degré ℓ et d'ordre k

We determine the Boolean functions on GF(2)ⁿ which satisfy the propagation criterion of degree ℓ and order k ≥ n - ℓ - 2. All of theses functions are quadratic. We design nonquadratic Boolean functions satisfying the criterion PC(ℓ) of order k by using the Maiorana-McFarland construction involving nonlinear mappings derived from nonlinear codes.     

On some probabilistic approximations for AES-like s-boxes

Several recently proposed block ciphers such as AES, Camellia, Shark, Square and Hierocrypt use s-boxes that are based on the inversion mapping over GF(2ⁿ). In order to hide the simple algebraic structure in this mapping, an affine transformation over F₂ is usually used after the output of the s-box. In some ciphers, an additional affine transformation is used before the input of the s-box as well. In this paper, we study the algebraic properties of a simple approximation in the form s(x)=ax^-1+b, a,b∈GF(2ⁿ) for such s-boxes. The implication of this result on the cryptanalysis of these ciphers remains an open problem.     

Trace Representation of Legendre Sequences

In this paper, a Legendre sequence of period p for any odd prime p is explicitely represented as a sum of trace functions from GF(2 ⁿ ) to GF(2), where n is the order of 2 mod p.     

Maximally Nonlinear Functions and Bent Functions

We give a construction of bent functions in 2n variables, here n is odd, by using maximally nonlinear functions on GF(2 ⁿ ).     

On the classification of semifield flocks

A classical lemma of Weil is used to characterise quadratic polynomials f with coefficients GF(qⁿ), q odd, with the property that f(x) is a non-zero square for all x∈GF(q). This characterisation is used to prove the main theorem which states that there are no subplanes of order q contained in the set of internal points of a conic in PG(2,qⁿ) for q?4n²−8n+2. As a corollary to this theorem it then follows that the only semifield flocks of the quadratic cone of PG(3,qⁿ) for those q exceeding this bound are the linear flocks and the Kantor-Knuth semifield flocks.     

AES side-channel countermeasure using random tower field constructions

Masking schemes to secure AES implementations against side-channel attacks is a topic of ongoing research. The most sensitive part of the AES is the non-linear SubBytes operation, in particular, the inversion in GF(2⁸), the Galois field of 2⁸ elements. In hardware implementations, it is well known that the use of the tower of extensions ${GF(2)\subset GF(2^2)\subset GF(2^4)\subset GF(2^8)}$ leads to a more efficient inversion. We propose to use a random isomorphism instead of a fixed one. Then, we study the effect of this randomization in terms of security and efficiency. Considering the field extension GF(2⁸)/GF(2⁴), the inverse operation leads to computation of its norm in GF(2⁴). Hence, in order to thwart side-channel attack, we manage to spread the values of norms over GF(2⁴). Combined with a technique of boolean masking in tower fields, our countermeasure strengthens resistance against first-order differential side-channel attacks.     

Enumeration of matrices of given rank with submatrices of given rank

The authors determine the number of (n+m)×t matrices A¹ of rank r+v, over a finite field GF(q), whose last m rows are those of a given matrix A of rank r+v over GF(q) and whose first n rows have a given rank u.     

Self-Orthogonal and Self-Dual Codes Constructed via Combinatorial Designs and Diophantine Equations

Combinatorial designs have been widely used, in the construction of self-dual codes. Recently, new methods of constructing self-dual codes are established using orthogonal designs (ODs), generalized orthogonal designs (GODs), a set of four sequences and Diophantine equations over GF(p). These methods had led to the construction of many new self-dual codes over small finite fields and rings. In this paper, we used some methods to construct self-orthogonal and self dual codes over GF(p), for some primes p. The construction is achieved by using some special kinds of combinatorial designs like orthogonal designs and GODs. Moreover, we combine eight circulant matrices, a system of Diophantine equations over GF(p), and a recently discovered array to obtain a new construction method. Using this method new self-dual and self-orthogonal codes are obtained. Specifically, we obtain new self-dual codes [32,16,12] over GF(11) and GF(13) which improve the previously known distances.     

Quadratic Double Circulant Codes over Fields

A generalization of the Pless symmetry codes to different fields is presented. In particular new infinite families of self-dual codes over GF(4), GF(5), GF(7), and GF(9) are introduced. It is proven that the automorphism group of some of these codes contains the group PSL₂(q). New codes over GF(4) and GF(5), with better minimum weight than previously known codes, are given.     

Factorization of Q(h(T)(x)) over a finite field where Q(x) is irreducible and h(T)(x) is linear—I

Let GF(q) be the finite field of order q, let Q(x) be an irreducible polynomial in GF(q)(x), and let h(T)(x) be a linear polynomial in GF(q)[x], where T:x→x^q. We use properties of the linear operator h(T) to give conditions for Q(h(T)(x)) to have a root of arbitrary degree k over GF(q), and we describe how to count the irreducible factors of Q(h(T)(x)) of degree k over GF(q). In addition we compare our results with those Ore which count the number of irreducible factors belonging to a linear polynomial having index k.     

Regular orientable imbeddings of complete graphs

This paper classifies the regular imbeddings of the complete graphs K_n in orientable surfaces. Biggs showed that these exist if and only if n is a prime power p^e, his examples being Cayley maps based on the finite field F = GF(n). We show that these are the only examples, and that there are $\text{φ(n ? 1)}\text{e}$ isomorphism classes of such maps (where φ is Euler's function), each corresponding to a conjugacy class of primitive elements of F, or equivalently to an irreducible factor of the cyclotomic polynomial Φ_{n ? 1}(z) over GF(p). We show that these maps are all equivalent under Wilson's map-operations H_i, and we determined for which n they are reflexible or self-dual.     

Decompositions of vector spaces over GF(2) into disjoint equidimensional affine spaces

We investigate the possibilities for decomposing the vector space [GF(2)]ⁿ into a set of 2^r?d (necessarily disjoint) d dimensional affine subspaces.