Abstract:
An $(n,k)$-affine source over a finite field $F$ is a random variable $X=(X_1,...,X_n) \in F^n$, which is uniformly distributed over an (unknown) $k$-dimensional affine subspace of $ F^n$. We show how to (deterministically) extract practically all the randomness from affine sources, for any field of size larger than $n^c$ (where $c$ is a large enough constant). Our main results are as follows: (For arbitrary $k$): For any $n,k$ and any $F$ of size larger than $n^{20}$, we give an explicit construction for a function $D: F^n \rightarrow {\mathbb F}^{k-1}$, such that for any $(n,k)$-affine source $X$ over $F$, the distribution of $D(X)$ is $\epsilon$-close to uniform, where $\epsilon$ is polynomially small in $|F|$. (For $k=1$): For any $n$ and any $F$ of size larger than $n^{c}$, we give an explicit construction for a function $D: {\mathbb F}^n \rightarrow \{0,1\}^{(1-\delta) \log_2 |F|}$, such that for any $(n,1)$-affine source $X$ over $F$, the distribution of $D(X)$ is $\epsilon$-close to uniform, where $\epsilon$ is polynomially small in $|F|$. Here, $\delta > 0$ is an arbitrary small constant, and $c$ is a constant depending on $\delta$.