The bit extraction problem or t-resilient functions
- 1 January 1985
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 396-407
- https://doi.org/10.1109/sfcs.1985.55
Abstract
We consider the following adversarial situation. Let n, m and t be arbitrary integers, and let f : {0, 1}n → {0, 1}m 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, 1}m. The question addressed is for what values of n, m and t does the adversary necessarily fail in biasing the outcome of f : {0,1}n → {0, 1}m, 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.Keywords
This publication has 4 references indexed in Scilit:
- Towards a strong communication complexity theory or generating quasi-random sequences from two communicating slightly-random sourcesPublished by Association for Computing Machinery (ACM) ,1985
- A simple parallel algorithm for the maximal independent set problemPublished by Association for Computing Machinery (ACM) ,1985
- The complexity of parallel computation on matroidsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- Deterministic simulation of probabilistic constant depth circuitsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985