On the algebraic degree stability of Boolean functions when restricted to affine spaces

We study the n-variable Boolean functions which keep their algebraic degree unchanged when they are restricted to any (affine) hyperplane, or more generally to any affine space of a given co-dimension k. For cryptographic applications it is of interest to determine functions f which have a relatively high degree and also maintain this degree when restricted to affine spaces of co-dimension k for k ranging from 1 to as high a value as possible. This highest value will be called the restriction degree stability of f, denoted by deg stab(f). We give several necessary and/or sufficient conditions for f to maintain its degree on spaces of co-dimension k. The value of deg stab(f) is determined for functions which are direct sums of monomial as well as for functions of degrees r ∈ {1, 2, n − 2, n − 1, n}; we also determine the symmetric functions which maintain their degree on any hyperplane. Finally, using our previous results and some computer assistance, we determine the behaviour of all the functions in 8 variables, therefore determining the optimal ones (i.e. with highest value of deg stab(f)) for each degree.