2017-03-17

# An improvement to the Hasse–Weil bound and applications to character sums, cryptography and coding

## Publication

### Publication

*
Advances in Mathematics
,
Volume 309
p. 238-
253
*

The Hasse–Weil bound is a deep result in mathematics and has found wide applications in mathematics, theoretical computer science, information theory etc. In general, the bound is tight and cannot be improved. However, for some special families of curves the bound could be improved substantially. In this paper, we focus on the Hasse–Weil bound for the curve defined by y^{p} − y = f(x) over the finite field F_{q}, where p is the characteristic of F_{q}. In 1993, Moreno–Moreno [7] gave an improvement to the Hasse–Weil bound for this family of curves. Recently, Kaufman and Lovett [4, FOCS2011] showed that the Hasse–Weil bound can be improved for this family of curves with f(x) = g(x) + h(x), where g(x) is a polynomial of degree ≪
$\sqrt{q}$ and h(x) is a sparse polynomial of arbitrary degree but bounded weight degree. The other recent improvement by Rojas-Leon and Wan [9, Math. Ann. 2011] shows that an extra
$\sqrt{p}$ can be removed for this family of curves if p is very large compared with polynomial degree of f(x) and log_{p} q.

In this paper, we focus on the most interesting case for applications, namely p = 2. We show that the Hasse–Weil bound for this special family of curves can be improved if q = 2^{n} with odd n ⩾ 3 which is the same case where Serre [10] improved the Hasse–Weil bound. However, our improvement is greater than Serre's and Moreno–Morenao's improvements for this special family of curves. Furthermore, our improvement works for p = 2 compared with the requirement of large p by Rojas-Leon and Wan. In addition, our improvement finds interesting applications to character sums, cryptography and coding theory. The key idea behind is that this curve has the Hasse–Witt invariant 0 and we show that the Hasse–Weil bound can be improved for any curves with the Hasse–Witt invariant 0. The main tool used in our proof involves Newton polygon and some results in algebraic geometry.

Additional Metadata | |
---|---|

Points, Algebraic curves, Abelian varities, Zeta function, Character sum, Codes, Nonlinearity | |

dx.doi.org/10.1016/j.aim.2017.01.011 | |

Advances in Mathematics | |

Organisation | Cryptology |

Cramer, R.J.F, & Xing, C. (2017). An improvement to the Hasse–Weil bound and applications to character sums, cryptography and coding.
Advances in Mathematics, 309, 238–253. doi:10.1016/j.aim.2017.01.011 |