Extractors for Low-Weight Affine Sources
Extractors for Low-Weight Affine Sources
复制标题
低权重仿射源提取器
DOI：
10.1109/ccc.2009.36
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Anup Rao
中科院分区：
文献类型：
--
作者：
Anup Rao
我们为\ empph提供多项式的可计算提取器{低重量的affince}。因此，如果相应的线性空间具有低重量载体的基础通用常数$ c，\ epsilon $，我们的提取器可以从重量$ k ^{\ epsilon} $ dimension $ k $的仿射来源提取几乎所有熵^{ - k^{\ omega（1）}} $。我们的技术涉及构建新的\ empph {Condersers} \ empph {随机源的仿射}。
We give polynomial time computable extractors for \emph{low-weight affince sources}. A distribution is affine if it samples a random points from some unknown low dimensional subspace of $\mathbb{F}_2^n$. 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,\epsilon$, our extractors can extract almost all the entropy from weight $k^{\epsilon}$ affine sources of dimension $k$, as long as $k ≫ \log ^c n$, with error $2^{-k^{\Omega(1)}}$. In particular, our results give 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 \emph{condensers} for \emph{affine somewhere random sources}.