Direct Approaches for Generic Constructions of Plateaued Functions and Bent Functions Outside M#
Pages 1400 - 1418
Abstract
The problem of designing explicit bent and plateaued functions has been researched for several decades. However, finding new bent functions outside the well-known completed Maiorana-McFarland class <inline-formula> <tex-math notation="LaTeX">$\mathcal {M}^{\#}$ </tex-math></inline-formula> is still a challenge. Plateaued functions have been characterized in many different ways, but there is no general and rigorous mathematical method to generate them directly, except for the ones in the spirit of the well-known Maiorana-McFarland constructions or those obtained through adaptations of the secondary constructions of bent functions. Jeong and Lee recently made significant advances regarding algorithms for constructing balanced plateaued functions with maximal algebraic degrees in [IEEE Trans. Inf. Theory, 70(2), 1408-1421, 2024]. Due to the gap between our significant interest in the notion of plateaued functions and the knowledge we have on it, our motivation is to bring further results on the constructions of plateaued functions that allow us to understand their structure better. This article creates a framework of new generic constructions of bent and plateaued functions by studying Boolean functions of the form <inline-formula> <tex-math notation="LaTeX">$h(x)=f(x)+F(f_{1}(x),\ldots, f_{r}(x))$ </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">$f_{i}(x)=f(x)+f(x+\mu _{i})$ </tex-math></inline-formula> for each <inline-formula> <tex-math notation="LaTeX">$1\leq i\leq r$ </tex-math></inline-formula>. We firstly prove that h and f have the same extended Walsh-Hadamard spectrum if <inline-formula> <tex-math notation="LaTeX">$D_{\mu _{i}}D_{\mu _{j}}f=0$ </tex-math></inline-formula> for any <inline-formula> <tex-math notation="LaTeX">$1\leq i\lt j\leq r$ </tex-math></inline-formula>. This result extends a previous construction of bent functions to any Boolean functions. The strength of such a result is that it allows us to obtain several plateaued functions of high algebraic degrees from known ones with low algebraic degrees, which was a significant and challenging problem raised in the literature. Such a result is a real challenge and breaks a deadlock since no mathematical method allows the general constructions of plateaued functions. We next give an extended affine equivalent form of the function h, which provides us with another compelling perspective to design new bent functions (including those which are outside <inline-formula> <tex-math notation="LaTeX">$\mathcal {M}^{\#}$ </tex-math></inline-formula> from certain known ones inside <inline-formula> <tex-math notation="LaTeX">$\mathcal {M}^{\#}$ </tex-math></inline-formula>) and plateaued functions. Finally, we present four generic constructions of bent functions outside <inline-formula> <tex-math notation="LaTeX">$\mathcal {M}^{\#}$ </tex-math></inline-formula> from generalized Maiorana-McFarland functions.
References
[1]
A. Bapić and E. Pasalic, “A new method for secondary constructions of vectorial bent functions,” Des., Codes Cryptogr., vol. 89, no. 11, pp. 2463–2475, Nov. 2021.
[2]
A. Bapić and E. Pasalic, “Constructions of (vectorial) bent functions outside the completed Maiorana–McFarland class,” Discrete Appl. Math., vol. 314, pp. 197–212, Jun. 2022.
[3]
A. Braeken, “Cryptographic properties of Boolean functions and S-boxes,” Ph.D. thesis, Dept. Electronic ESAT., Katholieke Universiteit Leuven, Leuven, Belgium, 2006.
[4]
L. Budaghyan, C. Carlet, T. Helleseth, A. Kholosha, and S. Mesnager, “Further results on Niho bent functions,” IEEE Trans. Inf. Theory, vol. 58, no. 11, pp. 6979–6985, Nov. 2012.
[5]
A. Canteaut and P. Charpin, “Decomposing bent functions,” IEEE Trans. Inf. Theory, vol. 49, no. 8, pp. 2004–2019, Aug. 2003.
[6]
A. Canteaut, M. Daum, H. Dobbertin, and G. Leander, “Finding nonnormal bent functions,” Discrete Appl. Math., vol. 154, no. 2, pp. 202–218, Feb. 2006.
[7]
C. Carlet, “Two new classes of bent functions,” in Advances in Cryptology—EUROCRYPT’93 (Lecture Notes in Computer Science), vol. 765. Berlin, Germany: Springer, 1994, pp. 77–101.
[8]
C. Carlet, “On the confusion and diffusion properties of Maiorana–McFarland’s and extended Maiorana–McFarland’s functions,” J. Complex., vol. 20, pp. 182–204, Jan. 2004.
[9]
C. Carlet, “On the secondary constructions of resilient and bent functions,” in Coding, Cryptography and Combinatorics (Progress in Computer Science and Applied Logic), vol. 23. Basel, Switzerland: Birkhäuser Verlag, 2004, pp. 3–28.
[10]
C. Carlet, “Boolean and vectorial plateaued functions and APN functions,” IEEE Trans. Inf. Theory, vol. 61, no. 11, pp. 6272–6289, Nov. 2015.
[11]
C. Carlet, Boolean Functions for Cryptography Coding Theory. Cambridge, U.K.: Cambridge Univ. Press, 2020.
[12]
C. Carlet and S. Mesnager, “Four decades of research on bent functions,” Des., Codes Cryptogr., vol. 78, no. 1, pp. 5–50, Jan. 2016.
[13]
C. Carlet and E. Prouff, “On plateaued functions and their constructions,” in Fast Software Encryption (Lecture Notes in Computer Science), vol. 2887. Berlin, Germany: Springer, 2003, pp. 54–73.
[14]
N. Cepak, “On bent functions lying outside the completed Maiorana–McFarland class and permutations via translators,” Ph.D. dissertation, Dept. Faculty of Mathematics, Univ. Primorska, Koper, Slovenia, 2018.
[15]
P. Charpin and G. Kyureghyan, “Cubic monomial bent functions: A subclass of M,” SIAM J. Discr. Math., vol. 22, no. 2, pp. 650–665, 2008.
[16]
P. Charpin and G. M. Kyureghyan, “On a class of permutation polynomials over F2n,” in Sequences and Their Applications (Lecture Notes in Computer Science), vol. 5203. Berlin, Germany: Springer-Verlag, 2008, pp. 368–376.
[17]
R. S. Coulter, “On the evaluation of a class of Weil sums in characteristic 2,” New Zealand J. Math., vol. 28, no. 2, pp. 171–184, 1999.
[18]
T. W. Cusick, “Highly nonlinear plateaued functions,” IET Inf. Secur., vol. 11, no. 2, pp. 78–81, Mar. 2017.
[19]
J. Dillon, “Elementary Hadamard difference sets,” Ph.D. dissertation, Dept. Netw. Commun. Lab., Univ. Maryland, College Park, MD, USA, 1974.
[20]
J. F. Dillon and H. Dobbertin, “New cyclic difference sets with singer parameters,” Finite Fields Appl., vol. 10, no. 3, pp. 342–389, Jul. 2004.
[21]
C. Ding, “A construction of binary linear codes from Boolean functions,” Discrete Math., vol. 339, no. 9, pp. 2288–2303, Sep. 2016.
[22]
C. Ding, Z. Heng, and Z. Zhou, “Minimal binary linear codes,” IEEE Trans. Inf. Theory, vol. 64, no. 10, pp. 6536–6545, Oct. 2018.
[23]
Z. Heng, C. Ding, and Z. Zhou, “Minimal linear codes over finite fields,” Finite Fields Appl., vol. 54, pp. 176–196, Nov. 2018.
[24]
S. Hodžić, E. Pasalic, and Y. Wei, “A general framework for secondary constructions of bent and plateaued functions,” Des., Codes Cryptogr., vol. 88, no. 10, pp. 2007–2035, Oct. 2020.
[25]
S. Hodžic, E. Pasalic, Y. Wei, and F. Zhang, “Designing plateaued Boolean functions in spectral domain and their classification,” IEEE Trans. Inf. Theory, vol. 65, no. 9, pp. 5865–5879, Sep. 2019.
[26]
J. Y. Hyun, J. Lee, and Y. Lee, “Explicit criteria for construction of plateaued functions,” IEEE Trans. Inf. Theory, vol. 62, no. 12, pp. 7555–7565, Dec. 2016.
[27]
J. Jeong and Y. Lee, “Algorithms for constructing balanced plateaued functions with maximal algebraic degrees,” IEEE Trans. Inf. Theory, vol. 70, no. 2, pp. 1408–1421, Feb. 2024.
[28]
L. Kölsch, “On the inverses of Kasami and Bracken–Leander exponents,” Des., Codes Cryptogr., vol. 88, no. 12, pp. 2597–2621, Dec. 2020.
[29]
K. Li, C. Li, T. Helleseth, and L. Qu, “Further investigations on permutation based constructions of bent functions,” J. Combinat. Theory A, vol. 199, Oct. 2023, Art. no.
[30]
Y. Li, H. Kan, S. Mesnager, J. Peng, C. H. Tan, and L. Zheng, “Generic constructions of (Boolean and vectorial) bent functions and their consequences,” IEEE Trans. Inf. Theory, vol. 68, no. 4, pp. 2735–2751, Apr. 2022.
[31]
Y. Li, H. Kan, J. Peng, C. H. Tan, and B. Liu, “A new 10-variable cubic bent function outside the completed Maiorana–McFarland class,” IEICE Trans. Fundamentals Electron., Commun. Comput. Sci., vol. 104, no. 9, pp. 1353–1356, 2021.
[32]
Y. Li, J. Gao, H. Kan, J. Peng, L. Zheng, and C. Chen, “Characterization for a generic construction of bent functions and its consequences,” IEICE Trans. Fundam. Electron., Commun. Comput. Sci., vol. 107, no. 9, pp. 1570–1574, 2024.
[33]
Y. Li, J. Peng, H. Kan, and L. Zheng, “Minimal binary linear codes from vectorial Boolean functions,” IEEE Trans. Inf. Theory, vol. 69, no. 5, pp. 2955–2968, May 2023.
[34]
S. Liu, F. Zhang, E. Pasalic, S. Xia, and Z. Zhuo, “Further study on constructing bent functions outside the completed Maiorana–McFarland class,” IET Inf. Secur., vol. 14, no. 6, pp. 654–660, Nov. 2020.
[35]
S. Kudin and E. Pasalic, “A complete characterization of D0 ⋂ M# and a general framework for specifying bent functions in C outside M#,” Des., Codes Cryptogr., vol. 90, no. 8, pp. 1783–1796, 2022.
[36]
S. Kudin, E. Pasalic, N. Cepak, and F. Zhang, “Permutations without linear structures inducing bent functions outside the completed Maiorana–McFarland class,” Cryptogr. Commun., vol. 14, no. 1, pp. 101–116, Jan. 2022.
[37]
R.-L. McFarland, “A family of noncyclic difference sets,” J. Combinat. Theory, A, vol. 15, no. 1, pp. 1–10, 1973.
[38]
S. Mesnager, “On semi-bent functions and related plateaued functions over the Galois field F2n,” in Open Problems in Mathematics and Computational Science. Cham, Switzerland: Springer, 2014, pp. 243–273.
[39]
S. Mesnager, “Several new infinite families of bent functions and their duals,” IEEE Trans. Inf. Theory, vol. 60, no. 7, pp. 4397–4407, Jul. 2014.
[40]
S. Mesnager, “Further constructions of infinite families of bent functions from new permutations and their duals,” Cryptogr. Commun., vol. 8, no. 2, pp. 229–246, Apr. 2016.
[41]
S. Mesnager, Bent Functions: Fundamentals and Results. Cham, Switzerland: Springer, 2016, pp. 1–544.
[42]
S. Mesnager, “Linear codes with few weights from weakly regular bent functions based on a generic construction,” Cryptogr. Commun., vol. 9, no. 1, pp. 71–84, Jan. 2017.
[43]
S. Mesnager, “Linear codes from functions,” in Concise Encyclopedia of Coding Theory. New York, NY, USA: Taylor & Francis, 2021, ch. 20.
[44]
S. Mesnager, F. Özbudak, and A. Sınak, “Linear codes from weakly regular plateaued functions and their secret sharing schemes,” Des., Codes Cryptogr., vol. 87, nos. 2–3, pp. 463–480, Mar. 2019.
[45]
S. Mesnager and A. Sinak, “Several classes of minimal linear codes with few weights from weakly regular plateaued functions,” IEEE Trans. Inf. Theory, vol. 66, no. 4, pp. 2296–2310, Apr. 2020.
[46]
S. Mesnager and A. Sinak, “Infinite classes of six-weight linear codes derived from weakly regular plateaued functions,” in Proc. Int. Conf. Inf. Secur. Cryptol. (ISCTURKEY), Dec. 2020, pp. 93–100.
[47]
S. Mesnager and A. Sınak, “Minimal linear codes derived from weakly regular bent and plateaued functions,” J. Algebra Appl., vol. 23, no. 7, Jun. 2024, Art. no. 10.1142/s021949882550077x.
[48]
S. Mesnager, C. Tang, and Y. Qi, “Generalized plateaued functions and admissible (Plateaued) functions,” IEEE Trans. Inf. Theory, vol. 63, no. 10, pp. 6139–6148, Oct. 2017.
[49]
A. Sınak, “Minimal linear codes from weakly regular plateaued balanced functions,” Discrete Math., vol. 344, no. 3, Mar. 2021, Art. no.
[50]
A. Sınak, “Minimal linear codes with six-weights based on weakly regular plateaued balanced functions,” Int. J. Inf. Secur. Sci., vol. 10, no. 3, pp. 86–98, 2021.
[51]
E. Pasalic, A. Bapić, F. Zhang, and Y. Wei, “Explicit infinite families of bent functions outside the completed Maiorana–McFarland class,” Des., Codes Cryptogr., vol. 91, pp. 2365–2393, Mar. 2023.
[52]
E. Pasalic, A. Bapić, F. Zhang, and Y. Wei, “Using Pτ property for designing bent functions provably outside the completed Maiorana–McFarland class,” Des., Codes Cryptogr., vol. 92, no. 9, pp. 2639–2654, Sep. 2024. 10.1007/s10623-024-01407-9.,: https://doi.org/10.1007/s10623-024-01407-9
[53]
E. Pasalic, A. Polujan, S. Kudin, and F. Zhang, “Design and analysis of bent functions using M-subspaces,” IEEE Trans. Inf. Theory, vol. 70, no. 6, pp. 4464–4477, Jun. 2024.
[54]
E. Pasalic, F. Zhang, S. Kudin, and Y. Wei, “Vectorial bent functions weakly/strongly outside the completed Maiorana–McFarland class,” Discrete Appl. Math., vol. 294, pp. 138–151, May 2021.
[55]
A. Polujan, “Boolean and vectorial functions: A design-theoretic point of view,” Ph.D. dissertation, Dept. Math., Otto von Guericke Univ. Magdeburg, Magdeburg, Germany, 2021. [Online]. Available: https://d-nb.info/1239811446/34
[56]
A. A. Polujan and A. Pott, “Cubic bent functions outside the completed Maiorana–McFarland class,” Des., Codes Cryptogr., vol. 88, no. 9, pp. 1701–1722, Sep. 2020.
[57]
O. S. Rothaus, “On ‘bent’ functions,” J. Combinat. Theory A, vol. 20, no. 3, pp. 300–305, May 1976.
[58]
C. Tang, Z. Zhou, Y. Qi, X. Zhang, C. Fan, and T. Helleseth, “Generic construction of bent functions and bent idempotents with any possible algebraic degrees,” IEEE Trans. Inf. Theory, vol. 63, no. 10, pp. 6149–6157, Oct. 2017.
[59]
L. Wang, B. Wu, Z. Liu, and D. Lin, “Three new infinite families of bent functions,” Sci. China Inf. Sci., vol. 61, no. 3, Mar. 2018, Art. no.
[60]
G. Xu, X. Cao, and S. Xu, “Several new classes of Boolean functions with few Walsh transform values,” Appl. Algebra Eng. Commun. Comput., vol. 28, no. 2, pp. 155–176, 2017.
[61]
G. Xu, L. Qu, and X. Cao, “Minimal linear codes from Maiorana–McFarland functions,” Finite Fields Appl., vol. 65, Aug. 2020, Art. no.
[62]
G. Xu, L. Qu, and G. Luo, “Minimal linear codes from weakly regular bent functions,” in Proc. Int. Conf. Sequences Appl. (SETA), Saint Petersburg, Russia, Sep. 2020, pp. 22–25.
[63]
G. Xu, L. Qu, and G. Luo, “Minimal linear codes from weakly regular bent functions,” Cryptogr. Commun., vol. 14, no. 2, pp. 415–431, 2022.
[64]
F.-R. Zhang, C. Carlet, Y.-P. Hu, and T.-J. Cao, “Secondary constructions of highly nonlinear Boolean functions and disjoint spectra plateaued functions,” Inf. Sci., vol. 283, pp. 94–106, Nov. 2014.
[65]
F. Zhang, E. Pasalic, A. Bapić, and B. Wang, “Constructions of several special classes of cubic bent functions outside the completed Maiorana–McFarland class,” Inf. Comput., vol. 297, Mar. 2024, Art. no.
[66]
F. Zhang, E. Pasalic, N. Cepak, and Y. Wei, “Bent functions in C and D outside the completed Maiorana–McFarland class,” in Codes, Cryptology and Information Security (Lecture Notes in Computer Science), vol. 10194. Berlin, Germany: Springer-Verlag, 2017, pp. 298–313.
[67]
F. Zhang, E. Pasalic, N. Cepak, and Y. Wei, “Further analysis of bent functions from C and D which are provably outside or inside M#,” Discrete Appl. Math., vol. 285, pp. 458–472, Jan. 2020.
[68]
F. Zhang, E. Pasalic, Y. Wei, and N. Cepak, “Constructing bent functions outside the Maiorana–McFarland class using a general form of rothaus,” IEEE Trans. Inf. Theory, vol. 63, no. 8, pp. 5336–5349, Aug. 2017.
[69]
F. Zhang, Y. Wei, and E. Pasalic, “Constructions of Bent—Negabent functions and their relation to the completed Maiorana—McFarland class,” IEEE Trans. Inf. Theory, vol. 61, no. 3, pp. 1496–1506, Mar. 2015.
[70]
F. Zhang, E. Pasalic, R. Rodríguez, and Y. Wei, “Minimal binary linear codes: A general framework based on bent concatenation,” Des., Codes Cryptogr., vol. 90, no. 5, pp. 1289–1318, May 2022.
[71]
L. Zheng, J. Peng, H. Kan, and Y. Li, “Several new infinite families of bent functions via second order derivatives,” Cryptogr. Commun., vol. 12, no. 6, pp. 1143–1160, Nov. 2020.
[72]
Y. Zheng and X.-M. Zhang, “Plateaued functions,” in Information and Communication Security (Lecture Notes in Computer Science), vol. 1726, V. Varadharajan and Y. Mu, Eds., Berlin, Germany: Springer, 1999, pp. 284–300.
[73]
Y. Zheng and X.-M. Zhang, “On plateaued functions,” IEEE Trans. Inf. Theory, vol. 47, no. 3, pp. 1215–1223, Mar. 2001.
Index Terms
- Direct Approaches for Generic Constructions of Plateaued Functions and Bent Functions Outside M#
Index terms have been assigned to the content through auto-classification.
Recommendations
Generalized Plateaued Functions and Admissible (Plateaued) Functions
Plateaued functions are very important crypto- graphic functions due to their various desirable cryptographic characteristics. We point out that plateaued functions are more general than bent functions (that is, functions with maximum nonlinearity). Some ...
A construction of bent functions from plateaued functions
In this presentation, a technique for constructing bent functions from plateaued functions is introduced and analyzed. This generalizes earlier techniques for constructing bent from near-bent functions. Using this construction, we obtain a big variety ...
New secondary constructions of Bent functions
In this paper, we first present a novel secondary construction of bent functions (building new bent functions from two already defined ones). Furthermore, the algebraic degree and algebraic immunity of the constructed functions are analysed. Finally, we ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
0018-9448 © 2024 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.
Publisher
IEEE Press
Publication History
Published: 13 November 2024
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 23 Feb 2025