Constructing single- and multi-output boolean functions with maximal algebraic immunity

The aim of this paper is to construct boolean functions f : {0,1}(n) -> {0,1}(m), for which the graph gr(f) = {(x,f(x)), x is an element of {0, 1}n} subset of {0, 1}(n+m) has maximal algebraic immunity. This research is motivated by the need for appropriate boolean functions serving as building blocks of symmetric ciphers. Such functions should have large algebraic immunity for preventing vulnerability of the cipher against algebraic attacks. We completely solve the problem of constructing explicitely defined single-output functions for which the graph has maximal algebraic immunity. Concerning multi-output functions, we present an efficient algorithm, based on matroid union, which computes for given m,n,d the table of a function h : {0, 1}(n) -> {0, 1}(m) for which the algebraic immunity of the graph is greater than d. To the best of our knowledge, this is the first systematic method for constructing multioutput functions of high algebraic immunity.