New constructions of balanced Boolean functions with high nonlinearity and optimal algebraic degree

Abstract

In this paper, we propose a technique for constructing balanced Boolean functions on even numbers of variables. The main technique is to utilize a set of disjoint spectra functions and a special Boolean permutation to derive a balanced Boolean function with high nonlinearity and optimal algebraic degree. It is shown that the functions we construct are different from both Maiorana-McFarland's (M-M) super-class functions introduced by Carlet and modified M-M super-class functions presented by Zeng and Hu. Furthermore, we show that they have no nonzero linear structures.

Keywords:

• stream cipher
• Boolean function
• balanced function
• nonlinearity
• algebraic degree

2000 AMS Subject Classifications :

• 94A60
• 06E30

Acknowledgements

This work was supported in part by National Science Foundation of China (60833008, 60832001), 973 Project (2007CB311201), Fundamental Research Funds for the Central Universities (K50510010015), and Science and Technology on Communication Security Laboratory (9140C110201110C1102).