An efficient characterization of a family of hyper-bent functions with multiple trace terms

Journal of mathematical cryptology

article

Jean-Pierre Flori¹  Sihem Mesnager² 

[1]Institut Télécom

[2]Laboratoire Analyse, Department of Mathematics, University of Paris XIII and University of Paris VIII

关键词: Boolean functions;    Walsh–Hadamard transform;    maximum nonlinearity;    hyper-bent functions;    hyperelliptic curves;    Dickson polynomials;   

DOI  :  10.1515/jmc-2012-0013

学科分类：社会科学、人文和艺术（综合）

来源: De Gruyter

【 摘 要 】

Abstract. The connection between exponential sums and algebraic varieties has been known for at least six decades. Recently, Lisoněk exploited it to reformulate the Charpin–Gong characterization of a large class of hyper-bent functions in terms of numbers of points on hyperelliptic curves. As a consequence, he obtained a polynomial time and space algorithm for certain subclasses of functions in the Charpin–Gong family. In this paper, we settle a more general framework, together with detailed proofs, for such an approach and show that it applies naturally to a distinct family of functions proposed by Mesnager. Doing so, a polynomial time and space test for the hyper-bentness of functions in this family is obtained as well. Nonetheless, a straightforward application of such results does not provide a satisfactory criterion for explicit generation of functions in the Mesnager family. To address this issue, we show how to obtain a more efficient test leading to a substantial practical gain. We finally elaborate on an open problem about hyperelliptic curves related to a family of Boolean functions studied by Charpin and Gong.

【 授权许可】

CC BY|CC BY-NC-ND