An improvement to the Hasse-Weil bound and applications to character sums, cryptography and coding (Q509671): Difference between revisions

For \(C\), a projective, geometrically irreducible, nonsingular, algebraic curve of genus \(g\) defined over the finite field \(k:=\mathbb F_q\) of characteristic \(p\) and order \(q\), the Hasse-Weil-Serre (HWS) bound asserts that \(|\#C(k)-(q+1)|\leq g\cdot\lfloor 2\sqrt{q}\rfloor\) [\textit{J.-P. Serre}, C. R. Acad. Sci., Paris, Sér. I 296, 397--402 (1983; Zbl 0538.14015)]. This bound is sharp in general but can be improved in some specific cases. For instance if \(C\) admits a plane model of type \[ y^p-y=f(x)\in k[x], \tag{*} \] (see [\textit{O. Moreno} and \textit{C. J. Moreno}, Lect. Notes Comput. Sci. 673, 257--268 (1993; Zbl 0908.11020); \textit{T. Kaufman} and \textit{S. Lovett}, in: Proceedings of the 2011 IEEE 52nd annual symposium on foundations of computer science. Palm Springs, USA. Los Alamitos, CA: IEEE Computer Society. 788--796 (2011; Zbl 1292.94177)] for certain \(f(x)\), [\textit{A. Rojas-León} and \textit{D. Wan}, Math. Ann. 351, No. 2, 417--442 (2011; Zbl 1281.11064)] for large \(p\)). There are several applications of the aforementioned improvements in character sums, coding theory, finite geometry, dryptography, \dots. In the paper under review, the authors work out a further improvement for \(C\) defined by \((*)\) provided that \(p=2\), \(q=2^n\) with \(n\geq 3\) an odd integer. As a matter of fact, in this situation, they improve on the HWS's and Moreno-Moreno's bound, and show that Rojas-Leon and Wan approach also works for \(p=2\). The key facts to prove these results are the nullity of the Hasse-Witt of \(C\), which follows from the Deuring-Shafarevich theorem, the shape of its Newton polygon together with some results regarding abelian varieties. For example, the improvement above imply the following applications: {\parindent=6mm \begin{itemize}\item[(1)] Let the degree of \(f(x)\) be 3, and \(\chi: k\to \mathbb C^*\) a nontrivial additive character; then \[ \left|\sum_{\alpha\in k}\chi(f(\alpha))\right|\leq 2^{(n+1)/2}\tag{1} \] while the HWS bound implies an upper bound at least \(2^{(n+1)/2}\) in (1). \item[(2)] Details for this item can be found in [\textit{C. Carlet}, in: Boolean models and methods in mathematics, computer science, and engineering. Cambridge: Cambridge University Press. 257--397 (2010; Zbl 1209.94035)]: The nonlinearity \(NL(f)\) of \(f(x)\) is defined through the Walsh transfer and it is upper-bounded by a number in the interval \([A, B]\), where \(A=2^{n-1}-2^{(n-1)/2}\) and \(B=2^{n-1}-2^{n/2-1}\). It is known that \(A\) is attained if \(f(x)\) is quadratic. Here it is shown that this is also true whenever the degree of \(f(x)\) is 3 or 5. Thus we have enlarged the set of polynomials with high nonlinearity which are very useful in cryptography matters. \item[(3)] Improvement on the minimum distance of several classes of trace codes which are closely related to curves defined by (*) above. \end{itemize}}