Constructions of Cryptographically Significant Boolean Functions Using Primitive Polynomials

Abstract

It is known that Boolean functions used in stream and block ciphers should have good cryptographic properties to resist algebraic attacks. Up until now, there have been several constructions of Boolean functions achieving optimum algebraic immunity. However, most of their nonlinearities are very low. Carlet and Feng studied a class of Boolean functions with optimum algebraic immunity and deduced the lower bound of its nonlinearity, which is good, but not very high. Moreover, the main practical problem with this construction is that it cannot be implemented efficiently. In this paper, we put forward a new method to construct cryptographically significant Boolean functions by using primitive polynomials, and construct three infinite classes of Boolean functions with good cryptographic properties: balancedness, optimum algebraic degree, optimum algebraic immunity, and a high nonlinearity.