Extractors for Low-Weight Affine Sources

Anup Rao
Institute for Advanced Study

We give polynomial time computable extractors for low-weight affine sources. A distribution is affine if it samples a random point from some unknown low dimensional subspace of F^n_2 . A distribution is low weight affine if the corresponding linear space has a basis of low-weight vectors. Low-weight affine sources are thus a generalization of the well studied models of bit-fixing sources (which are just weight 1 affine sources). For universal constants c,e , our extractors can extract almost all the entropy from weight k affine sources of dimension k, as long as k > log^c n, with error 2^{-k^Omega(1)} . This gives new extractors for low entropy bit-fixing sources with exponentially small error, a parameter that is important for the application of these extractors to cryptography. Our techniques involve constructing new condensers for affine somewhere random sources.

Back to Expanders in Pure and Applied Mathematics