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

Secondary constructions of bent functions and their enforcement

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

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.
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, (2000), 573.  doi: 10.1007/3-540-45539-6_40.  Google Scholar

[2]

C. Carlet, Two new classes of bent functions,, in, (1994), 77.   Google Scholar

[3]

C. Carlet, Generalized partial spreads,, IEEE Trans. Inform. Theory, 41 (1995), 1482.  doi: 10.1109/18.412693.  Google Scholar

[4]

C. Carlet, A construction of bent functions,, in, (1996), 47.  doi: 10.1017/CBO9780511525988.006.  Google Scholar

[5]

C. Carlet, On the confusion and diffusion properties of Maiorana-McFarland's and extended Maiorana-McFarland's functions,, J. Complexity, 20 (2004), 182.  doi: 10.1016/j.jco.2003.08.013.  Google Scholar

[6]

C. Carlet, On the secondary constructions of resilient and bent functions,, in, (2004), 3.   Google Scholar

[7]

C. Carlet, On bent and highly nonlinear balanced/resilient functions and their algebaric immunities,, in, (2006), 1.   Google Scholar

[8]

C. Carlet, Boolean functions for cryptography and error correcting codes,, in, (2010), 257.   Google Scholar

[9]

C. Carlet, H. Dobbertin and G. Leander, Normal extensions of bent functions,, IEEE Trans. Inform. Theory, 50 (2004), 2880.  doi: 10.1109/TIT.2004.836681.  Google Scholar

[10]

J. Dillon, "Elementary Hadamard Difference Sets,'', Ph.D thesis, (1974).   Google Scholar

[11]

H. Dobbertin, Construction of bent functions and balanced Boolean functions with high nonlinearity,, in, (1995), 61.  doi: 10.1007/3-540-60590-8_5.  Google Scholar

[12]

H. Dobbertin and G. Leander, Bent functions embedded into the recursive framework of $\mathbb Z$-bent functions,, Des. Codes Cryptogr., 49 (2008), 3.  doi: 10.1007/s10623-008-9189-3.  Google Scholar

[13]

P. Guillo, Completed GPS covers all bent functions,, J. Combin. Theory Ser. A, 93 (2001), 242.  doi: 10.1006/jcta.2000.3076.  Google Scholar

[14]

X.-D. Hou, New constructions of bent functions,, J. Combin. Inform. System Sci., 25 (2000), 173.   Google Scholar

[15]

P. Langevin, G. Leander, P. Rabizzoni, P. Veron and J.-P. Zanotti, Classification of Boolean quartics forms in eight variables,, availabel at \url{http://langevin.univ-tln.fr/project/quartics/quartics.html}, ().   Google Scholar

[16]

G. Leander, Monomial bent functions,, IEEE Trans. Inform. Theory, 52 (2006), 738.  doi: 10.1109/TIT.2005.862121.  Google Scholar

[17]

G. Leander and G. McGuire, Construction of bent functions from near-bent functions,, J. Combin. Theory Ser. A, 116 (2009), 960.  doi: 10.1016/j.jcta.2008.12.004.  Google Scholar

[18]

Q. Liu, Y. Zhang, C. Cheng and W. Lü, Construction and counting orthomorphism based on transversal,, in, (2008), 369.   Google Scholar

[19]

F. J. MacWilliams and N. J. A. Sloane, "The Theory of Error-Correcting Codes,'', North-Holland, (1977).   Google Scholar

[20]

R. I. McFarland, A family of difference sets in non-cyclic groups,, J. Comb. Theory Ser. A, 15 (1973), 1.  doi: 10.1016/0097-3165(73)90031-9.  Google Scholar

[21]

Q. Meng, L. Chen and F. Fu, On homogeneous rotation symmetric bent functions,, Discrete Appl. Math., 158 (2010), 1111.  doi: 10.1016/j.dam.2010.02.009.  Google Scholar

[22]

J. D. Olsen, R. A. Scholtz and L. R. Welch, Bent-function sequence,, IEEE Trans. Inform. Theory, 28 (1982), 858.  doi: 10.1109/TIT.1982.1056589.  Google Scholar

[23]

O. S. Rothaus, On "bent'' functions,, J. Combin. Theory Ser. A, 20 (1976), 300.  doi: 10.1016/0097-3165(76)90024-8.  Google Scholar

[24]

J. Wolfmann, Bent functions and coding theory,, in, (1999), 393.   Google Scholar

[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.   Google Scholar

show all references

References:
[1]

A. Canteaut and M. Trabbia, Improved fast correlation attacks using parity-check equations of weight 4 and 5,, in, (2000), 573.  doi: 10.1007/3-540-45539-6_40.  Google Scholar

[2]

C. Carlet, Two new classes of bent functions,, in, (1994), 77.   Google Scholar

[3]

C. Carlet, Generalized partial spreads,, IEEE Trans. Inform. Theory, 41 (1995), 1482.  doi: 10.1109/18.412693.  Google Scholar

[4]

C. Carlet, A construction of bent functions,, in, (1996), 47.  doi: 10.1017/CBO9780511525988.006.  Google Scholar

[5]

C. Carlet, On the confusion and diffusion properties of Maiorana-McFarland's and extended Maiorana-McFarland's functions,, J. Complexity, 20 (2004), 182.  doi: 10.1016/j.jco.2003.08.013.  Google Scholar

[6]

C. Carlet, On the secondary constructions of resilient and bent functions,, in, (2004), 3.   Google Scholar

[7]

C. Carlet, On bent and highly nonlinear balanced/resilient functions and their algebaric immunities,, in, (2006), 1.   Google Scholar

[8]

C. Carlet, Boolean functions for cryptography and error correcting codes,, in, (2010), 257.   Google Scholar

[9]

C. Carlet, H. Dobbertin and G. Leander, Normal extensions of bent functions,, IEEE Trans. Inform. Theory, 50 (2004), 2880.  doi: 10.1109/TIT.2004.836681.  Google Scholar

[10]

J. Dillon, "Elementary Hadamard Difference Sets,'', Ph.D thesis, (1974).   Google Scholar

[11]

H. Dobbertin, Construction of bent functions and balanced Boolean functions with high nonlinearity,, in, (1995), 61.  doi: 10.1007/3-540-60590-8_5.  Google Scholar

[12]

H. Dobbertin and G. Leander, Bent functions embedded into the recursive framework of $\mathbb Z$-bent functions,, Des. Codes Cryptogr., 49 (2008), 3.  doi: 10.1007/s10623-008-9189-3.  Google Scholar

[13]

P. Guillo, Completed GPS covers all bent functions,, J. Combin. Theory Ser. A, 93 (2001), 242.  doi: 10.1006/jcta.2000.3076.  Google Scholar

[14]

X.-D. Hou, New constructions of bent functions,, J. Combin. Inform. System Sci., 25 (2000), 173.   Google Scholar

[15]

P. Langevin, G. Leander, P. Rabizzoni, P. Veron and J.-P. Zanotti, Classification of Boolean quartics forms in eight variables,, availabel at \url{http://langevin.univ-tln.fr/project/quartics/quartics.html}, ().   Google Scholar

[16]

G. Leander, Monomial bent functions,, IEEE Trans. Inform. Theory, 52 (2006), 738.  doi: 10.1109/TIT.2005.862121.  Google Scholar

[17]

G. Leander and G. McGuire, Construction of bent functions from near-bent functions,, J. Combin. Theory Ser. A, 116 (2009), 960.  doi: 10.1016/j.jcta.2008.12.004.  Google Scholar

[18]

Q. Liu, Y. Zhang, C. Cheng and W. Lü, Construction and counting orthomorphism based on transversal,, in, (2008), 369.   Google Scholar

[19]

F. J. MacWilliams and N. J. A. Sloane, "The Theory of Error-Correcting Codes,'', North-Holland, (1977).   Google Scholar

[20]

R. I. McFarland, A family of difference sets in non-cyclic groups,, J. Comb. Theory Ser. A, 15 (1973), 1.  doi: 10.1016/0097-3165(73)90031-9.  Google Scholar

[21]

Q. Meng, L. Chen and F. Fu, On homogeneous rotation symmetric bent functions,, Discrete Appl. Math., 158 (2010), 1111.  doi: 10.1016/j.dam.2010.02.009.  Google Scholar

[22]

J. D. Olsen, R. A. Scholtz and L. R. Welch, Bent-function sequence,, IEEE Trans. Inform. Theory, 28 (1982), 858.  doi: 10.1109/TIT.1982.1056589.  Google Scholar

[23]

O. S. Rothaus, On "bent'' functions,, J. Combin. Theory Ser. A, 20 (1976), 300.  doi: 10.1016/0097-3165(76)90024-8.  Google Scholar

[24]

J. Wolfmann, Bent functions and coding theory,, in, (1999), 393.   Google Scholar

[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.   Google Scholar

[1]

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

[2]

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

[3]

Yi Ming Zou. Dynamics of boolean networks. Discrete & Continuous Dynamical Systems - S, 2011, 4 (6) : 1629-1640. doi: 10.3934/dcdss.2011.4.1629

[4]

Constanza Riera, Pantelimon Stănică. Landscape Boolean functions. Advances in Mathematics of Communications, 2019, 13 (4) : 613-627. doi: 10.3934/amc.2019038

[5]

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

[6]

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

[7]

Franziska Hinkelmann, Reinhard Laubenbacher. Boolean models of bistable biological systems. Discrete & Continuous Dynamical Systems - S, 2011, 4 (6) : 1443-1456. doi: 10.3934/dcdss.2011.4.1443

[8]

Yongwu Rong, Chen Zeng, Christina Evans, Hao Chen, Guanyu Wang. Topology and dynamics of boolean networks with strong inhibition. Discrete & Continuous Dynamical Systems - S, 2011, 4 (6) : 1565-1575. doi: 10.3934/dcdss.2011.4.1565

[9]

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

[10]

Ethel Mokotoff. Algorithms for bicriteria minimization in the permutation flow shop scheduling problem. Journal of Industrial & Management Optimization, 2011, 7 (1) : 253-282. doi: 10.3934/jimo.2011.7.253

[11]

Ricardo P. Beausoleil, Rodolfo A. Montejo. A study with neighborhood searches to deal with multiobjective unconstrained permutation problems. Journal of Industrial & Management Optimization, 2009, 5 (2) : 193-216. doi: 10.3934/jimo.2009.5.193

[12]

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

[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]

Yu Zhou. On the distribution of auto-correlation value of balanced Boolean functions. Advances in Mathematics of Communications, 2013, 7 (3) : 335-347. doi: 10.3934/amc.2013.7.335

[15]

SelÇuk Kavut, Seher Tutdere. Highly nonlinear (vectorial) Boolean functions that are symmetric under some permutations. Advances in Mathematics of Communications, 2020, 14 (1) : 127-136. doi: 10.3934/amc.2020010

[16]

Peter Müller, Gábor P. Nagy. On the non-existence of sharply transitive sets of permutations in certain finite permutation groups. Advances in Mathematics of Communications, 2011, 5 (2) : 303-308. doi: 10.3934/amc.2011.5.303

[17]

Tim Gutjahr, Karsten Keller. Equality of Kolmogorov-Sinai and permutation entropy for one-dimensional maps consisting of countably many monotone parts. Discrete & Continuous Dynamical Systems - A, 2019, 39 (7) : 4207-4224. doi: 10.3934/dcds.2019170

[18]

Yuri Latushkin, Alim Sukhtayev. The Evans function and the Weyl-Titchmarsh function. Discrete & Continuous Dynamical Systems - S, 2012, 5 (5) : 939-970. doi: 10.3934/dcdss.2012.5.939

[19]

J. William Hoffman. Remarks on the zeta function of a graph. Conference Publications, 2003, 2003 (Special) : 413-422. doi: 10.3934/proc.2003.2003.413

[20]

Hassan Emamirad, Philippe Rogeon. Semiclassical limit of Husimi function. Discrete & Continuous Dynamical Systems - S, 2013, 6 (3) : 669-676. doi: 10.3934/dcdss.2013.6.669

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (12)
  • HTML views (0)
  • Cited by (12)

Other articles
by authors

[Back to Top]