Constructing Boolean functions with (potentially) optimal algebraic immunity based on multiplicative decompositions of finite fields

摘要

In this paper, we investigate on constructing cryptographically significant Boolean functions with n variables based on decompositions of the multiplicative group of the finite field F of the form F* = U × V, where U and V are cyclic subgroups of F* satisfying (|U|, |V|) = 1. For positive integers s, m and n = 2m, we obtain classes of unbalanced functions with optimal algebraic immunity in the cases |U| = 2 + 1, |V| = (2−1)/(2+1) and |U| = 2−1, |V| = (2−1)/(2−1), respectively, where in the latter case the optimal algebraic immunity is based on correctness of the Tu-Deng conjecture. Functions belonging to both classes can be modified to be balanced ones with (potentially) optimal algebraic immunity and optimal algebraic degree, and computer experiments show that they also have high nonlinearity and good immunity against fast algebraic attacks. As by-products, variants of the Tu-Deng conjecture and combinatorial results on binary strings in analogy to it are also obtained.