Constructions of balanced Boolean functions with high nonlinearity and high algebraic degree

Abstract

Three of the most essential criteria for cryptographically strong Boolean functions are balancedness, high nonlinearity and high algebraic degree. In this paper, we give two methods for constructing balanced Boolean functions with high nonlinearity via modifying Maiorana–McFarland type bent functions. The algebraic immunity of the constructed functions is also considered.

Keywords:

• algebraic degree
• balanced
• Boolean functions
• cryptography
• nonlinearity

2000 AMS Subject Classifications :

• 94A60
• 06E30

Acknowledgements

The authors would like to thank the anonymous reviewers and the editor for their comments that improved the technical and the editorial quality of this paper. This work was supported by the Natural Science Foundations of China (Nos. 61003299, 11201359), the Natural Science Basic Research Plan in Shaanxi Province of China (No. 2012JM8041) and the Fundamental Research Funds for the Central Universities.