Constructing Boolean Functions Using Blended Representations

Abstract

In this paper, we study blended representations of Boolean functions, and construct the following two classes of Boolean functions. Two bounds on the $r$ -order nonlinearity were given by Carlet in the IEEE Transactions on Information Theory, vol. 54. In general, the second bound is better than the first bound. But it was unknown whether it is always better. Recently, Mesnager et al. constructed a class of Boolean functions where the second bound is strictly worse than the first bound, for $r=2$ . However, it is still an open problem for $r\geq 3$ . Using the blended representation, we construct a class of Boolean functions based on the trace function and show that the second bound can also be strictly worse than the first bound, for $r=3$ . The second class is based on the hidden weighted bit function, which seems to have the best cryptographic properties among all currently known functions.

Keywords

• Boolean functions
• blended representations
• nonlinearity
• algebraic immunity
• higher-order nonlinearity