Notes on Bent Functions in Polynomial Forms

Abstract

The existence and construction of bent functions are two of the most widely studied problems in Boolean functions. For monomial functions f(x) = T rn 1 (axs), these problems were examined extensively and it was shown that the bentness of the monomial functions is complete for n ≤ 20. However, in the binomial function case, i.e. f(x) = T rn 1 (axs1 ) + T rk 1 (bxs2 ), this characterization is not complete and there are still open problems. In this paper, we give a summary of the literature on the bentness of binomial functions and show that there exist no bent functions of the form T rn 1 (axr(2m−1)) + T rm 1 (bxs(2m+1)) where n = 2m, gcd(r, 2m + 1) = 1, gcd(s, 2 m − 1) = 1. Also, we give a bent function example of the form fa,b(x) = T rn 1 (ax2m−1 ) + T r2 1(bx 2n−1 3 ) for n = 4, although, it is stated in [9] that there is no such bent function of this form for any value of a and b.

Keywords

• Boolean function
• Bent functions
• Walsh-Hadamard Transform
• Dillon exponents
• Kloosterman Sums

References

1. J. F. Dillon, Elementary Hadamard Difference Sets, Ph.D Dissertation, University of Maryland 1974.
2. H. Dobbertin, G. Leander, A. Canteaut, C. Carlet, P. Felke, P. Gaborit, Construction of bent functions via Niho power functions, J. Combin. Theory, ser. A, vol. 113, pp 779-798, 2006.
3. G. Leander, Monomial bent functions, IEEE Trans. Inf. Theory, vol. 2, no. 52, pp. 738-743, 2006.
4. A. Canteaut, P. Charpin, and G. Kyureghyan, A new class of monomial bent functions, Finite Fields Applicat., vol. 14, no. 1, pp 221-241, 2008.
5. P. Charpin and G. Kyureghyan, Cubic monomial bent functions: A subclass of M, SIAM J. Discr. Math., vol. 22, no. 2, pp. 650665,2008.
6. S. Mesnager, A new class of bent boolean functions in polynomial forms, in Proc. Int. Workshop on Coding and Cryptography, WCC 2009, pp. 5-18, 2009.
7. P. Charpin, G. Gong, Hyperbent functions, Kloosterman Sums and Dickson Polynomials, IEEE Trans. Inform. Theory 9(54), 4230-4238 (2008).
8. S. Mesnager, A new family of hyper-bent boolean functions in polynomial form, M. G. Parker Ed., in Proc. Twelfth Int. Conf. Cryptography and Coding, Cirencester, United Kingdom. IMACC 2009, Heidelberg, Germany, 2009, vol. 5921, LNCS, pp. 402-417.

9. S. Mesnager, A new class of bent and hyper-bent boolean functions in polynomial forms, Des. Codes Cryptography, 59(13):265-279, 2011.
10. B. Wang, C. Tang, Y. Qi, Y. Yang, M. Xu, A New Class of Hyper-bent Boolean Functions with Multiple Trace Terms, Cryptology ePrint Archive, Report 2011/600, 2011. http://eprint.iacr.org/.
11. S. Mesnager, Recent Results on Bent and Hyper-bent Functions and Their Link With Some Exponential Sums. IEEE Information Theory Workshop (ITW 2010), Dublin, August-September 2010.
12. G. Lachaud, J. Wolfmann, The Weights of the Orthogonals of the Extended Quadratic Binary Goppa Codes IEEE Trans. Inf. Theory, vol. 36, no 3, pp. 686-692, 1990.
13. R.Gold, Maximal Recursive Sequences with 3-valued Recursive Cross-Correlation Functions IEEE Trans. Inf. Theory, vol. 14, no 1, pp. 154-156, 1968.
14. J.F. Dillon, H. Dobbertin, New Cyclic Difference Sets with Singer Parameters Finite Fields and Their Applications, vol.10, no 3, pp. 342-389, 2004.
15. B. Wang, C. Tang, Y. Qi, and Y. Yang, A generalization of the class of hyper-bent Boolean functions in binomial forms, Cryptology ePrint Archive, Report 2011/698, 2011. http://eprint.iacr.org/.
16. S. Mesnager, J.-P. Flori, A note on hyper-bent functions via Dillon-like exponents, Cryptology ePrint Archive, Report 2012/033, 2012. http://eprint.iacr.org/.