Bent functions in the partial spread class generated by linear recurring sequences
Tóm tắt
We present a construction of partial spread bent functions using subspaces generated by linear recurring sequences (LRS). We first show that the kernels of the linear mappings defined by two LRS have a trivial intersection if and only if their feedback polynomials are relatively prime. Then, we characterize the appropriate parameters for a family of pairwise coprime polynomials to generate a partial spread required for the support of a bent function, showing that such families exist if and only if the degrees of the underlying polynomials are either 1 or 2. We then count the resulting sets of polynomials and prove that, for degree 1, our LRS construction coincides with the Desarguesian partial spread. Finally, we perform a computer search of all
$$\mathcal{PS}\mathcal{}^-$$
and
$$\mathcal{PS}\mathcal{}^+$$
bent functions of
$$n=8$$
variables generated by our construction and compute their 2-ranks. The results show that many of these functions defined by polynomials of degree
$$d=2$$
are not EA-equivalent to any Maiorana–McFarland or Desarguesian partial spread function.
Tài liệu tham khảo
Benjamin A.T., Bennett C.D.: The probability of relatively prime polynomials. Math. Mag. 80(3), 196–202 (2007).
Bush K.: Construction of symmetric Hadamard matrices. In: A Survey of Combinatorial Theory, pp. 81–83. Elsevier (1973).
Carlet C.: Boolean functions for cryptography and error correcting codes. In: Crama Y., Hammer P.L. (eds.) Boolean Models and Methods in Mathematics, Computer Science, and Engineering, 1st edn, pp. 257–397. Cambridge University Press, New York (2010).
Carlet C.: Boolean Functions for Cryptography and Coding Theory. Cambridge University Press, Cambridge (2021).
Carlet C., Gaborit P.: Hyper-bent functions and cyclic codes. J. Comb. Theory Ser. A 113(3), 466–482 (2006).
Carlet C., Mesnager S.: Four decades of research on bent functions. Des. Codes Cryptogr. 78(1), 5–50 (2016).
Dillon J.F.: Elementary hadamard difference sets. Ph.D. thesis, Univ. of Maryland (1974).
Dobbertin H.: Construction of bent functions and balanced Boolean functions with high nonlinearity. In: Preneel B. (ed.) Fast Software Encryption: Second International Workshop. Leuven, Belgium, 14–16 December 1994, Proceedings, Lecture Notes in Computer Science, vol. 1008, pp. 61–74. Springer (1994).
Gadouleau M., Mariot L., Picek S.: Bent functions from cellular automata. IACR Cryptol. ePrint Arch. 1272 (2020). https://eprint.iacr.org/2020/1272
Gelfand I.M., Kapranov M., Zelevinsky A.: Discriminants, Resultants, and Multidimensional Determinants. Springer, New York (2008).
Lidl R., Niederreiter H.: Introduction to Finite Fields and Their Applications. Cambridge University Press, Cambridge (1994).
Mariot L., Gadouleau M., Formenti E., Leporati A.: Mutually orthogonal latin squares based on cellular automata. Des. Codes Cryptogr. 88(2), 391–411 (2020).
Mariot L., Leporati A., Dennunzio A., Formenti E.: Computing the periods of preimages in surjective cellular automata. Nat. Comput. 16(3), 367–381 (2017).
McFarland R.L.: A family of difference sets in non-cyclic groups. J. Comb. Theory Ser. A 15(1), 1–10 (1973).
Mesnager S.: Bent Functions-Fundamentals and Results. Springer, New York (2016).
Polujan A.A., Pott A.: Cubic bent functions outside the completed Maiorana-McFarland class. Des. Codes Cryptogr. (2020). https://doi.org/10.1007/s10623-019-00712-y.
Rothaus O.S.: On ”bent" functions. J. Comb. Theory Ser. A 20(3), 300–305 (1976).
Sylvester J.J.: Xviii. on a theory of the syzygetic relations of two rational integral functions, comprising an application to the theory of Sturm’s functions, and that of the greatest algebraical common measure. Philos. Trans. R. Soc. Lond. (143), 407–548 (1853).
Weng G., Feng R., Qiu W.: On the ranks of bent functions. Finite Fields Their Appl. 13(4), 1096–1116 (2007).
Youssef A.M., Gong G.: Hyper-bent functions. In: Pfitzmann B. (ed.) Advances in Cryptology—EUROCRYPT 2001, International Conference on the Theory and Application of Cryptographic Techniques, Innsbruck, Austria, May 6–10, 2001, Proceeding, Lecture Notes in Computer Science, vol. 2045, pp. 406–419. Springer (2001).