Explicit Resilient Functions Matching Ajtai-Linial
From MaRDI portal
Abstract: A Boolean function on n variables is q-resilient if for any subset of at most q variables, the function is very likely to be determined by a uniformly random assignment to the remaining n-q variables; in other words, no coalition of at most q variables has significant influence on the function. Resilient functions have been extensively studied with a variety of applications in cryptography, distributed computing, and pseudorandomness. The best known balanced resilient function on n variables due to Ajtai and Linial ([AL93]) is Omega(n/(log^2 n))-resilient. However, the construction of Ajtai and Linial is by the probabilistic method and does not give an efficiently computable function. In this work we give an explicit monotone depth three almost-balanced Boolean function on n bits that is Omega(n/(log^2 n))-resilient matching the work of Ajtai and Linial. The best previous explicit construction due to Meka [Meka09] (which only gives a logarithmic depth function) and Chattopadhyay and Zuckermman [CZ15] were only n^{1-c}-resilient for any constant c < 1. Our construction and analysis are motivated by (and simplifies parts of) the recent breakthrough of [CZ15] giving explicit two-sources extractors for polylogarithmic min-entropy; a key ingredient in their result was the construction of explicit constant-depth resilient functions. An important ingredient in our construction is a new randomness optimal oblivious sampler which preserves moment generating functions of sums of variables and could be useful elsewhere.
Recommendations
- Cryptology and Network Security
- scientific article; zbMATH DE number 1676649
- Applied Cryptography and Network Security
- A construction of resilient functions with high nonlinearity
- scientific article; zbMATH DE number 1543052
- On construction of a class of nonlinear resilient functions
- On the divisibility properties and nonlinearity of resilient functions
- Construction of resilient functions with high nonlinearity and optimal algebraic degree
- scientific article; zbMATH DE number 1406784
- An infinite class of counterexamples to a conjecture concerning nonlinear resilient functions
Cited in
(13)- Explicit two-source extractors and resilient functions
- On extractors and exposure-resilient functions for sublogarithmic entropy
- Tree tribes and lower bounds for switching lemmas
- Randomness extraction in \(\mathsf{AC}^0\) and with small locality
- An Efficient Reduction from Two-Source to Nonmalleable Extractors: Achieving Near-Logarithmic Min-Entropy
- Biasing Boolean functions and collective coin-flipping protocols over arbitrary product distributions
- Non-malleable extractors and non-malleable codes: partially optimal constructions
- scientific article; zbMATH DE number 7561729 (Why is no real title available?)
- scientific article; zbMATH DE number 7250143 (Why is no real title available?)
- scientific article; zbMATH DE number 7650110 (Why is no real title available?)
- Two-source and affine non-malleable extractors for small entropy
- Black-box non-interactive zero knowledge from vector trapdoor hash
- Bit-fixing extractors for almost-logarithmic entropy
This page was built for publication: Explicit Resilient Functions Matching Ajtai-Linial
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575815)
