Secondary constructions of bent functions and their enforcement

Previous Article
Canonical- systematic form for codes in hierarchical poset metrics
AMC Home
This Issue
Next Article
Characterization and constructions of self-dual codes over $\mathbb Z_2\times \mathbb Z_4$

August 2012, 6(3): 305-314. doi: 10.3934/amc.2012.6.305

Secondary constructions of bent functions and their enforcement

Claude Carlet ^1, , Fengrong Zhang ^2, and Yupu Hu ^3,

1.	LAGA, Universities of Paris 8 and Paris 13; CNRS, UMR 7539, Department of Mathematics, University of Paris 8, 2 rue de la liberté, 93526 Saint-Denis cedex 02, France
2.	School of Computer Science and Technology, China University of Mining and Technology, Xuzhou, Jiangsu 221116, China, and ISN, Xidian University, Xi'an, Shannxi 710071, China
3.	State Key Laboratory of Integrated Services Networks, Xidian university, P.O. Box 95, Taibai Road 2, Xi'an, Shannxi 710071, China

Received July 2011 Revised March 2012 Published August 2012

Abstract
Related Papers

Thirty years ago, Rothaus introduced the notion of bent function and presented a secondary construction (building new bent functions from already defined ones), which is now called the Rothaus construction. This construction has a strict requirement for its initial functions. In this paper, we first concentrate on the design of the initial functions in the Rothaus construction. We show how to construct Maiorana-McFarland's (M-M) bent functions, which can then be used as initial functions, from Boolean permutations and orthomorphic permutations. We deduce that at least $(2^n!\times 2^{2^n})(2^{2^n}\times2^{2^{n-1}})^2$ bent functions in $2n+2$ variables can be constructed by using Rothaus' construction. In the second part of the note, we present a new secondary construction of bent functions which generalizes the Rothaus construction. This construction requires initial functions with stronger conditions; we give examples of functions satisfying them. Further, we generalize the new secondary construction of bent functions and illustrate it with examples.

Keywords: Block cipher, Boolean function, stream cipher, orthomorphic permutation., Boolean permutation, bent function.

Mathematics Subject Classification: 06E30, 94A6.

Citation: Claude Carlet, Fengrong Zhang, Yupu Hu. Secondary constructions of bent functions and their enforcement. Advances in Mathematics of Communications, 2012, 6 (3) : 305-314. doi: 10.3934/amc.2012.6.305

References:

[1]	A. Canteaut and M. Trabbia, Improved fast correlation attacks using parity-check equations of weight 4 and 5, in "EUROCRYPT 2000'' (ed. B. Preneel), Springer, (2000), 573-588. doi: 10.1007/3-540-45539-6_40.
[2]	C. Carlet, Two new classes of bent functions, in "EUROCRYPT'93'' (ed. T. Helleseth), Springer, (1994), 77-101.
[3]	C. Carlet, Generalized partial spreads, IEEE Trans. Inform. Theory, 41 (1995), 1482-1487. doi: 10.1109/18.412693.
[4]	C. Carlet, A construction of bent functions, in "Proceeding of the Third International Conference on Finite Fields and Applications'' (eds. S. Cohen and H. Niederreiter), Cambridge University Press, (1996), 47-58. doi: 10.1017/CBO9780511525988.006.
[5]	C. Carlet, On the confusion and diffusion properties of Maiorana-McFarland's and extended Maiorana-McFarland's functions, J. Complexity, 20 (2004), 182-204. doi: 10.1016/j.jco.2003.08.013.
[6]	C. Carlet, On the secondary constructions of resilient and bent functions, in "Proceedings of the Workshop on Coding, Cryptography and Combinatorics 2003'' (eds. K. Feng, H. Niederreiter and C. Xing), Birkhäuser Verlag, (2004), 3-28.
[7]	C. Carlet, On bent and highly nonlinear balanced/resilient functions and their algebaric immunities, in "AAECC 2006'' (eds. M. Fossorier et al.), Springer, (2006), 1-28.
[8]	C. Carlet, Boolean functions for cryptography and error correcting codes, in "Boolean Models and Methods in Mathematics, Computer Science, and Engineering'' (eds. Y. Crama and P. Hammer), Cambridge University Press, (2010), 257-397.
[9]	C. Carlet, H. Dobbertin and G. Leander, Normal extensions of bent functions, IEEE Trans. Inform. Theory, 50 (2004), 2880-2885. doi: 10.1109/TIT.2004.836681.
[10]	J. Dillon, "Elementary Hadamard Difference Sets,'' Ph.D thesis, Univ. Maryland, College Park, 1974.
[11]	H. Dobbertin, Construction of bent functions and balanced Boolean functions with high nonlinearity, in "Fast Software Encryption,'' Springer, (1995), 61-74. doi: 10.1007/3-540-60590-8_5.
[12]	H. Dobbertin and G. Leander, Bent functions embedded into the recursive framework of $\mathbb Z$-bent functions, Des. Codes Cryptogr., 49 (2008), 3-22. doi: 10.1007/s10623-008-9189-3.
[13]	P. Guillo, Completed GPS covers all bent functions, J. Combin. Theory Ser. A, 93 (2001), 242-260. doi: 10.1006/jcta.2000.3076.
[14]	X.-D. Hou, New constructions of bent functions, J. Combin. Inform. System Sci., 25 (2000), 173-189.
[15]	P. Langevin, G. Leander, P. Rabizzoni, P. Veron and J.-P. Zanotti, Classification of Boolean quartics forms in eight variables, availabel at http://langevin.univ-tln.fr/project/quartics/quartics.html
[16]	G. Leander, Monomial bent functions, IEEE Trans. Inform. Theory, 52 (2006), 738-743. doi: 10.1109/TIT.2005.862121.
[17]	G. Leander and G. McGuire, Construction of bent functions from near-bent functions, J. Combin. Theory Ser. A, 116 (2009), 960-970. doi: 10.1016/j.jcta.2008.12.004.
[18]	Q. Liu, Y. Zhang, C. Cheng and W. Lü, Construction and counting orthomorphism based on transversal, in "2008 International Conference on Computational Intelligence and Security,'' IEEE Computer Society, (2008), 369-373.
[19]	F. J. MacWilliams and N. J. A. Sloane, "The Theory of Error-Correcting Codes,'' North-Holland, Amsterdam, 1977.
[20]	R. I. McFarland, A family of difference sets in non-cyclic groups, J. Comb. Theory Ser. A, 15 (1973), 1-10. doi: 10.1016/0097-3165(73)90031-9.
[21]	Q. Meng, L. Chen and F. Fu, On homogeneous rotation symmetric bent functions, Discrete Appl. Math., 158 (2010), 1111-1117. doi: 10.1016/j.dam.2010.02.009.
[22]	J. D. Olsen, R. A. Scholtz and L. R. Welch, Bent-function sequence, IEEE Trans. Inform. Theory, 28 (1982), 858-864. doi: 10.1109/TIT.1982.1056589.
[23]	O. S. Rothaus, On "bent'' functions, J. Combin. Theory Ser. A, 20 (1976), 300-305. doi: 10.1016/0097-3165(76)90024-8.
[24]	J. Wolfmann, Bent functions and coding theory, in "Difference Sets, Sequences and their Correlation Properties'' (eds. A. Pott, P.V. Kumar, T. Helleseth and D. Jungnickel), Amsterdam, Kluwer, (1999), 393-417.
[25]	H. Zhen, H. Zhang, T. Cui and X. Du, A new method for construction of orthomorphic permutations (in Chinese), J. Electr. Inform. Tech., 31 (2009), 1438-1441.

show all references

References:

[1]	A. Canteaut and M. Trabbia, Improved fast correlation attacks using parity-check equations of weight 4 and 5, in "EUROCRYPT 2000'' (ed. B. Preneel), Springer, (2000), 573-588. doi: 10.1007/3-540-45539-6_40.
[2]	C. Carlet, Two new classes of bent functions, in "EUROCRYPT'93'' (ed. T. Helleseth), Springer, (1994), 77-101.
[3]	C. Carlet, Generalized partial spreads, IEEE Trans. Inform. Theory, 41 (1995), 1482-1487. doi: 10.1109/18.412693.
[4]	C. Carlet, A construction of bent functions, in "Proceeding of the Third International Conference on Finite Fields and Applications'' (eds. S. Cohen and H. Niederreiter), Cambridge University Press, (1996), 47-58. doi: 10.1017/CBO9780511525988.006.
[5]	C. Carlet, On the confusion and diffusion properties of Maiorana-McFarland's and extended Maiorana-McFarland's functions, J. Complexity, 20 (2004), 182-204. doi: 10.1016/j.jco.2003.08.013.
[6]	C. Carlet, On the secondary constructions of resilient and bent functions, in "Proceedings of the Workshop on Coding, Cryptography and Combinatorics 2003'' (eds. K. Feng, H. Niederreiter and C. Xing), Birkhäuser Verlag, (2004), 3-28.
[7]	C. Carlet, On bent and highly nonlinear balanced/resilient functions and their algebaric immunities, in "AAECC 2006'' (eds. M. Fossorier et al.), Springer, (2006), 1-28.
[8]	C. Carlet, Boolean functions for cryptography and error correcting codes, in "Boolean Models and Methods in Mathematics, Computer Science, and Engineering'' (eds. Y. Crama and P. Hammer), Cambridge University Press, (2010), 257-397.
[9]	C. Carlet, H. Dobbertin and G. Leander, Normal extensions of bent functions, IEEE Trans. Inform. Theory, 50 (2004), 2880-2885. doi: 10.1109/TIT.2004.836681.
[10]	J. Dillon, "Elementary Hadamard Difference Sets,'' Ph.D thesis, Univ. Maryland, College Park, 1974.
[11]	H. Dobbertin, Construction of bent functions and balanced Boolean functions with high nonlinearity, in "Fast Software Encryption,'' Springer, (1995), 61-74. doi: 10.1007/3-540-60590-8_5.
[12]	H. Dobbertin and G. Leander, Bent functions embedded into the recursive framework of $\mathbb Z$-bent functions, Des. Codes Cryptogr., 49 (2008), 3-22. doi: 10.1007/s10623-008-9189-3.
[13]	P. Guillo, Completed GPS covers all bent functions, J. Combin. Theory Ser. A, 93 (2001), 242-260. doi: 10.1006/jcta.2000.3076.
[14]	X.-D. Hou, New constructions of bent functions, J. Combin. Inform. System Sci., 25 (2000), 173-189.
[15]	P. Langevin, G. Leander, P. Rabizzoni, P. Veron and J.-P. Zanotti, Classification of Boolean quartics forms in eight variables, availabel at http://langevin.univ-tln.fr/project/quartics/quartics.html
[16]	G. Leander, Monomial bent functions, IEEE Trans. Inform. Theory, 52 (2006), 738-743. doi: 10.1109/TIT.2005.862121.
[17]	G. Leander and G. McGuire, Construction of bent functions from near-bent functions, J. Combin. Theory Ser. A, 116 (2009), 960-970. doi: 10.1016/j.jcta.2008.12.004.
[18]	Q. Liu, Y. Zhang, C. Cheng and W. Lü, Construction and counting orthomorphism based on transversal, in "2008 International Conference on Computational Intelligence and Security,'' IEEE Computer Society, (2008), 369-373.
[19]	F. J. MacWilliams and N. J. A. Sloane, "The Theory of Error-Correcting Codes,'' North-Holland, Amsterdam, 1977.
[20]	R. I. McFarland, A family of difference sets in non-cyclic groups, J. Comb. Theory Ser. A, 15 (1973), 1-10. doi: 10.1016/0097-3165(73)90031-9.
[21]	Q. Meng, L. Chen and F. Fu, On homogeneous rotation symmetric bent functions, Discrete Appl. Math., 158 (2010), 1111-1117. doi: 10.1016/j.dam.2010.02.009.
[22]	J. D. Olsen, R. A. Scholtz and L. R. Welch, Bent-function sequence, IEEE Trans. Inform. Theory, 28 (1982), 858-864. doi: 10.1109/TIT.1982.1056589.
[23]	O. S. Rothaus, On "bent'' functions, J. Combin. Theory Ser. A, 20 (1976), 300-305. doi: 10.1016/0097-3165(76)90024-8.
[24]	J. Wolfmann, Bent functions and coding theory, in "Difference Sets, Sequences and their Correlation Properties'' (eds. A. Pott, P.V. Kumar, T. Helleseth and D. Jungnickel), Amsterdam, Kluwer, (1999), 393-417.
[25]	H. Zhen, H. Zhang, T. Cui and X. Du, A new method for construction of orthomorphic permutations (in Chinese), J. Electr. Inform. Tech., 31 (2009), 1438-1441.

[1]	Bimal Mandal, Aditi Kar Gangopadhyay. A note on generalization of bent boolean functions. Advances in Mathematics of Communications, 2021, 15 (2) : 329-346. doi: 10.3934/amc.2020069
[2]	Nishant Sinha. Internal state recovery of Espresso stream cipher using conditional sampling resistance and TMDTO attack. Advances in Mathematics of Communications, 2021, 15 (3) : 539-556. doi: 10.3934/amc.2020081
[3]	Stefano Barbero, Emanuele Bellini, Rusydi H. Makarim. Rotational analysis of ChaCha permutation. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021057
[4]	Claude Carlet, Khoongming Khoo, Chu-Wee Lim, Chuan-Wen Loe. On an improved correlation analysis of stream ciphers using multi-output Boolean functions and the related generalized notion of nonlinearity. Advances in Mathematics of Communications, 2008, 2 (2) : 201-221. doi: 10.3934/amc.2008.2.201
[5]	Li Zhang, Xiaofeng Zhou, Min Chen. The research on the properties of Fourier matrix and bent function. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 571-578. doi: 10.3934/naco.2020052
[6]	Washiela Fish, Jennifer D. Key, Eric Mwambene. Partial permutation decoding for simplex codes. Advances in Mathematics of Communications, 2012, 6 (4) : 505-516. doi: 10.3934/amc.2012.6.505
[7]	Junchao Zhou, Yunge Xu, Lisha Wang, Nian Li. Nearly optimal codebooks from generalized Boolean bent functions over $ \mathbb{Z}_{4} $. Advances in Mathematics of Communications, 2022, 16 (3) : 485-501. doi: 10.3934/amc.2020121
[8]	Yi Ming Zou. Dynamics of boolean networks. Discrete and Continuous Dynamical Systems - S, 2011, 4 (6) : 1629-1640. doi: 10.3934/dcdss.2011.4.1629
[9]	Constanza Riera, Pantelimon Stănică. Landscape Boolean functions. Advances in Mathematics of Communications, 2019, 13 (4) : 613-627. doi: 10.3934/amc.2019038
[10]	Sihem Mesnager, Gérard Cohen. Fast algebraic immunity of Boolean functions. Advances in Mathematics of Communications, 2017, 11 (2) : 373-377. doi: 10.3934/amc.2017031
[11]	Claude Carlet, Serge Feukoua. Three basic questions on Boolean functions. Advances in Mathematics of Communications, 2017, 11 (4) : 837-855. doi: 10.3934/amc.2017061
[12]	Franziska Hinkelmann, Reinhard Laubenbacher. Boolean models of bistable biological systems. Discrete and Continuous Dynamical Systems - S, 2011, 4 (6) : 1443-1456. doi: 10.3934/dcdss.2011.4.1443
[13]	Nian Li, Qiaoyu Hu. A conjecture on permutation trinomials over finite fields of characteristic two. Advances in Mathematics of Communications, 2019, 13 (3) : 505-512. doi: 10.3934/amc.2019031
[14]	Ethel Mokotoff. Algorithms for bicriteria minimization in the permutation flow shop scheduling problem. Journal of Industrial and Management Optimization, 2011, 7 (1) : 253-282. doi: 10.3934/jimo.2011.7.253
[15]	Ricardo P. Beausoleil, Rodolfo A. Montejo. A study with neighborhood searches to deal with multiobjective unconstrained permutation problems. Journal of Industrial and Management Optimization, 2009, 5 (2) : 193-216. doi: 10.3934/jimo.2009.5.193
[16]	Amin Sakzad, Mohammad-Reza Sadeghi, Daniel Panario. Cycle structure of permutation functions over finite fields and their applications. Advances in Mathematics of Communications, 2012, 6 (3) : 347-361. doi: 10.3934/amc.2012.6.347
[17]	Xiang Wang, Wenjuan Yin. New nonexistence results on perfect permutation codes under the hamming metric. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021058
[18]	Hotaka Udagawa, Taiji Okano, Toshimichi Saito. Permutation binary neural networks: Analysis of periodic orbits and its applications. Discrete and Continuous Dynamical Systems - B, 2022 doi: 10.3934/dcdsb.2022097
[19]	Yongwu Rong, Chen Zeng, Christina Evans, Hao Chen, Guanyu Wang. Topology and dynamics of boolean networks with strong inhibition. Discrete and Continuous Dynamical Systems - S, 2011, 4 (6) : 1565-1575. doi: 10.3934/dcdss.2011.4.1565
[20]	Jian Liu, Sihem Mesnager, Lusheng Chen. Variation on correlation immune Boolean and vectorial functions. Advances in Mathematics of Communications, 2016, 10 (4) : 895-919. doi: 10.3934/amc.2016048

2021 Impact Factor: 1.015

Tools

Metrics

Other articles
by authors

on AIMS
Claude Carlet Fengrong Zhang Yupu Hu
on Google Scholar
Claude Carlet Fengrong Zhang Yupu Hu

[Back to Top]