Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR08-015 | 23rd January 2008 00:00

Extractors for Low-Weight Affine Sources


Authors: Anup Rao
Publication: 28th February 2008 15:30
Downloads: 3190


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 ane 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-xing 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.

ISSN 1433-8092 | Imprint