Nonlinear Vector Resilient Functions

An (n, m, k)-resilient function is a function $$ f:\mathbb{F}_2^n \to \mathbb{F}_2^m $$ such that every possible output m-tuple is equally likely to occur when the values of k arbitrary inputs are fixed by an adversary and the remaining n - k input bits are chosen independently at random. In this paper we propose a new method to generate a (n + D + 1,m,d - 1)-resilient function for any non-negative integer D whenever a [n, m, d] linear code exists. This function has algebraic degree D and nonlinearity at least $$ 2^{n + D} - 2^n \left\lfloor {\sqrt {2^{n + D + 1} } } \right\rfloor + 2^{n - 1} $$. If we apply this method to the simplex code, we can get a (t(2m ™ 1) + D + 1, m, t2m™1 ™ 1)-resilient function with algebraic degree D for any positive integers m, t and D. Note that if we increase the input size by D in the proposed construction, we can get a resilient function with the same parameter except algebraic degree increased by D.