The bit extraction problem or t-resilient functions

We consider the following adversarial situation. Let n, m and t be arbitrary integers, and let f: 0, 1n → 0, 1m be a function. An adversary, knowing the function f, sets t of the n input bits, while the rest (n-t input, bits) are chosen at random (independently and with uniform probability distribution) The adversary tries to prevent the outcome of f from being uniformly distributed in 0, 1m. The question addressed is for what values of n, m and t does the adversary necessarily fail in biasing the outcome of f: 0, 1n → 0, 1m, when being restricted to set t of the input bits of f. We present various lower and upper bounds on m's allowing an affirmative answer. These bounds are relatively close for t ≤ n/3 and for t ≥ 2n/3. Our results have applications in the fields of faulttolerance and cryptography.