Arithmetic of Finite Fields

The complexity of computing the solutions of a system of multivariate polynomial equations by means of Gröbner bases computations is upper bounded by a function of the solving degree. In this paper, we discuss how to rigorously estimate the solving degree of a system, focusing on systems arising within public-key cryptography. In particular, we show that it is upper bounded by, and often equal to, the Castelnuovo-Mumford regularity of the ideal generated by the homogenization of the equations of the system, or by the equations themselves in case they are homogeneous. We discuss the underlying commutative algebra and clarify under which assumptions the commonly used results hold. In particular, we discuss the assumption of being in generic coordinates (often required for bounds obtained following this type of approach) and prove that systems that contain the field equations or their fake Weil descent are in generic coordinates. We also compare the notion of solving degree with that of degree of regularity, which is commonly used in the literature. We complement the paper with some examples of bounds obtained following the strategy that we describe.

Throughout this paper we let p be a prime number, let \(q=p^r\) and let \(\mathbb {F}_{q^n}\) denote a finite field with \(q^n\) elements, where n is a positive integer.

The last ten years have seen a tremendous growth in the interest and practicality of secure multiparty computation (MPC) and its possible applications. Secure MPC is indeed a very hot research topic and recent advances in the field have already been translated into commercial products world-wide. A major pillar in this advance has been in the case of active security with a dishonest majority, mainly due to the SPDZ-line of work protocols. This survey gives an overview of these protocols, with a focus of the original SPDZ paper (Damgård et al. CRYPTO 2012) and its subsequent optimizations.

In this paper we propose a HDL generator for finite-field multipliers on FPGAs. The generated multipliers are based on the CIOS variant of Montgomery multiplication. They are designed to exploit finely the DSPs available on most FPGAs, interleaving independent computations to maximize throughput and DSP’s workload. Beside their throughput-efficiency, these operators can dynamically adapt to different finite-fields by changing both operand width and precomputed elements.

From this flexible and efficient operator base, our HDL generator allows the exploration of a wide range of configurations. This is a valuable asset for specialized circuit designers who wish to tune state-of-the-art IPs and explore design space for their applications.

Multiplication is an expensive arithmetic operation, therefore there has been extensive research to find Karatsuba-like formulae reducing the number of multiplications involved when computing a bilinear map. The minimal number of multiplications in such formulae is called the bilinear complexity, and it is also of theoretical interest to asymptotically understand it. Moreover, when the bilinear maps admit some kind of invariance, it is also desirable to find formulae keeping the same invariance. In this work, we study trisymmetric, hypersymmetric, and Galois invariant multiplication formulae over finite fields, and we give an algorithm to find such formulae. We also generalize the result that the bilinear complexity and symmetric bilinear complexity of the two-variable multiplication in an extension field are linear in the degree of the extension, to trisymmetric bilinear complexity, and to the complexity of t-variable multiplication for any \(t\ge 3\).

The aim of this note is to give a construction and an enumeration of self-dual \(\theta \)-cyclic and \(\theta \)-negacyclic codes of length n over where p is a prime number and \(\theta \) is the Frobenius automorphism over . We use the notion of isodual codes to achieve this construction.

We deal with two problems related with the use of the Sakata’s algorithm in a specific class of bivariate codes (see [2, 8, 9]). The first one is to improve the general framework of locator decoding in order to apply it on such abelian codes. The second one is to find sufficient conditions to guarantee that the minimal set of polynomials given by the algorithm is exactly a Groebner basis of the locator ideal.

Dihedral codes, particular cases of quasi-cyclic codes, have a nice algebraic structure which allows to store them efficiently. In this paper, we investigate it and prove some lower bounds on their dimension and minimum distance, in analogy with the theory of BCH codes. This allows us to construct dihedral codes with prescribed minimum distance. In the binary case, we present some examples of optimal dihedral codes obtained by this construction.

Watermarking digital media is one of the important challenges for information hiding. Not only the watermark must be resistant to noise and against attempts of modification, legitimate users should not be aware that it is embedded in the media. One of the techniques for watermarking is using an special variant of spread-spectrum technique, called frequency hopping. It requires ensembles of periodic binary sequences with low off-peak autocorrelation and cross-correlation. Unfortunately, they are quite rare and difficult to find. The small Kasami, Kamaletdinov, and Extended Rational Cycle constructions are versatile, because they can also be converted into Costas-like arrays for frequency hopping. We study the implementation of such ensembles using linear feedback shift registers. This permits an efficient generation of sequences and arrays in real time in FPGAs. Such an implementation requires minimal memory usage and permits dynamic updating of sequences or arrays.

The aim of our work was to broaden current knowledge of sets of sequences with low correlation studying their implementation using linear feedback shift registers. A remarkable feature of these families is their similarities in terms of implementation and it may open new way to characterize sequences with low correlation, making it easier to generate them. It also validates a conjecture made by Moreno and Tirkel about arrays constructed using the method of composition.

In 2008 Budaghyan, Carlet and Leander generalized a known instance of an APN function over the finite field \(\mathbb {F}_{2^{12}}\) and constructed two new infinite families of APN binomials over the finite field \(\mathbb {F}_{2^n}\), one for n divisible by 3, and one for n divisible by 4. By relaxing conditions, the family of APN binomials for n divisible by 3 was generalized to a family of differentially \(2^t\)-uniform functions in 2012 by Bracken, Tan and Tan; in this sense, the binomials behave in the same way as the Gold functions. In this paper, we show that when relaxing conditions on the APN binomials for n divisible by 4, they also behave in the same way as the Gold function \(x^{2^s+1}\) (with s and n not necessarily coprime). As a counterexample, we also show that a family of APN quadrinomials obtained as a generalization of a known APN instance over \(\mathbb {F}_{2^{10}}\) cannot be generalized to functions with \(2^t\)-to-1 derivatives by relaxing conditions in a similar way.

Permutations of the form \(F(x)=L_1(x^{-1})+L_2(x)\) with linear functions \(L_1,L_2\) are closely related to several interesting questions regarding CCZ-equivalence and EA-equivalence of the inverse function. In this paper, we show that F cannot be a permutation on binary fields if the kernel of \(L_1\) or \(L_2\) is large. A key step of our proof is an observation on the maximal size of a subspace V of \(\mathbb {F}_{2^n}\) that consists of Kloosterman zeros, i.e. a subspace V such that \(K_n(v)=0\) for every \(v \in V\) where \(K_n(v)\) denotes the Kloosterman sum of v.

Let p, t, q, n, m and r be positive integers, such that p is a prime number, \(q=p^t\), \(\gcd (q,n)=1\), \(m=\text{ ord}_n(q)\), and suppose that the prime factors of r divide n but not \((q^m-1)/n\), and that \(q^m \equiv 1 \pmod {4}\), if 4|r. Also let u such that \(u=\gcd (\frac{q^m-1}{q-1},\frac{q^m-1}{n})\). Assume that \(u=1\) or p is semiprimitive modulo u. Under these conditions, we are going to obtain the explicit factorization of the period polynomial of degree \(\gcd (\frac{q^{mr}-1}{q-1},\frac{q^{mr}-1}{nr})\) for the finite field \({\mathbb {F}}_{q^{mr}}\). In fact, we will see that such polynomial has always integer roots, meaning that the corresponding Gaussian periods are also integer numbers. As an application, we also determine the number of solutions of certain diagonal equations with constant exponent.

We consider rational functions of the form V(x)/U(x), where both V(x) and U(x) are relatively prime polynomials over the finite field \(\mathbb {F}_q\). Polynomials that permute the elements of a field, called permutation polynomials (PPs), have been the subject of research for decades. Let \({\mathcal {P}}^1(\mathbb {F}_q)\) denote \(\mathbb {F}_q\cup \{\infty \}\). If the rational function, V(x)/U(x), permutes the elements of \({\mathcal {P}}^1(\mathbb {F}_q)\), it is called a permutation rational function (PRF). Let \(N_d(q)\) denote the number of PPs of degree d over \(\mathbb {F}_q\), and let \(N_{v,u}(q)\) denote the number of PRFs with a numerator of degree v and a denominator of degree u. It follows that \(N_{d,0}(q) = N_d(q)\), so PRFs are a generalization of PPs. The number of monic degree 3 PRFs is known [11]. We develop efficient computational techniques for \(N_{v,u}(q)\), and use them to show \(N_{4,3}(q) = (q+1)q^2(q-1)^2/3\), for all prime powers \(q \le 307\), \(N_{5,4}(q) > (q+1)q^3(q-1)^2/2\), for all prime powers \(q \le 97\), and give a formula for \(N_{4,4}(q)\). We conjecture that these are true for all prime powers q. Let M(n, D) denote the maximum number of permutations on n symbols with pairwise Hamming distance D. Computing improved lower bounds for M(n, D) is the subject of much current research with applications in error correcting codes. Using PRFs, we obtain significantly improved lower bounds on \(M(q,q-d)\) and \(M(q+1,q-d)\), for \(d \in \{5,7,9\}\).

Normal bases in finite fields constitute a vast topic of large theoretical and practical interest. Recently, k-normal elements were introduced as a natural extension of normal elements. The existence and the number of k-normal elements in a fixed extension of a finite field are both open problems in full generality, and comprise a promising research avenue. In this paper, we first formulate a general lower bound for the number of k-normal elements, assuming that they exist. We further derive a new existence condition for k-normal elements using the general factorization of the polynomial \(x^m-1\) into cyclotomic polynomials. Finally, we provide an existence condition for normal elements in \({\mathbb {F}_{q^m}}\) with a non-maximal but high multiplicative order in the group of units of the finite field.