On the Existence of Seedless Condensers: Exploring the Terrain
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910629135122432 |
|---|---|
| author | Chattopadhyay, Eshan Gurumukhani, Mohit Ringach, Noam |
| author_facet | Chattopadhyay, Eshan Gurumukhani, Mohit Ringach, Noam |
| contents | We prove several new results for seedless condensers in the context of three related classes of sources: Non-Oblivious Symbol Fixing (NOSF) sources, online NOSF (oNOSF) sources [AORSV, EUROCRYPT'20], and adversarial Chor-Goldreich (aCG) source [DMOZ, STOC'23]. We think of these sources as a sequence of random variables $\mathbf{X}=\mathbf{X}_1,\dots,\mathbf{X}_\ell$ on $\ell$ symbols where at least $g$ out of these $\ell$ symbols are "good" (i.e., have some min-entropy requirement), denoted as a $(g,\ell)$-source, and the remaining "bad" $\ell-g$ symbols may adversarially depend on these $g$ good blocks. The difference between each of these sources is realized by restrictions on the power of the adversary. Prior to our work, the only known seedless condenser upper or lower bound in these settings is due to [DMOZ, STOC'23], where they explicitly construct a seedless condenser for a restricted subset of $(g,\ell)$-aCG sources.
We show:
1) oNOSF sources
a) When $g\leq\ell/2$, we prove that condensing with error 0.99 above rate $\frac{1}{\lfloor \ell/g \rfloor}$ is impossible. In fact, we show that this is tight.
b) For $g> \ell/2$, we show the existence of excellent condensers for uniform oNOSF sources. In addition, we show the existence of similar condensers for oNOSF sources with only logarithmic min-entropy.
2) aCG sources
a) We observe that uniform aCG sources are equivalent to uniform oNOSF sources and consequently inherit the same results.
b) We show that one cannot condense beyond the min-entropy gap of each block or condense low min-entropy CG sources above rate $1/2$.
3) NOSF sources
a) We show that condensing with constant error above rate $\frac{g}{\ell}$ is impossible for uniform NOSF sources for any $g$ and $\ell$, thus ruling out the possibility of any non-trivial condensing. This shows a distinction between NOSF sources and oNOSF sources. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_15087 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the Existence of Seedless Condensers: Exploring the Terrain Chattopadhyay, Eshan Gurumukhani, Mohit Ringach, Noam Computational Complexity We prove several new results for seedless condensers in the context of three related classes of sources: Non-Oblivious Symbol Fixing (NOSF) sources, online NOSF (oNOSF) sources [AORSV, EUROCRYPT'20], and adversarial Chor-Goldreich (aCG) source [DMOZ, STOC'23]. We think of these sources as a sequence of random variables $\mathbf{X}=\mathbf{X}_1,\dots,\mathbf{X}_\ell$ on $\ell$ symbols where at least $g$ out of these $\ell$ symbols are "good" (i.e., have some min-entropy requirement), denoted as a $(g,\ell)$-source, and the remaining "bad" $\ell-g$ symbols may adversarially depend on these $g$ good blocks. The difference between each of these sources is realized by restrictions on the power of the adversary. Prior to our work, the only known seedless condenser upper or lower bound in these settings is due to [DMOZ, STOC'23], where they explicitly construct a seedless condenser for a restricted subset of $(g,\ell)$-aCG sources. We show: 1) oNOSF sources a) When $g\leq\ell/2$, we prove that condensing with error 0.99 above rate $\frac{1}{\lfloor \ell/g \rfloor}$ is impossible. In fact, we show that this is tight. b) For $g> \ell/2$, we show the existence of excellent condensers for uniform oNOSF sources. In addition, we show the existence of similar condensers for oNOSF sources with only logarithmic min-entropy. 2) aCG sources a) We observe that uniform aCG sources are equivalent to uniform oNOSF sources and consequently inherit the same results. b) We show that one cannot condense beyond the min-entropy gap of each block or condense low min-entropy CG sources above rate $1/2$. 3) NOSF sources a) We show that condensing with constant error above rate $\frac{g}{\ell}$ is impossible for uniform NOSF sources for any $g$ and $\ell$, thus ruling out the possibility of any non-trivial condensing. This shows a distinction between NOSF sources and oNOSF sources. |
| title | On the Existence of Seedless Condensers: Exploring the Terrain |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2312.15087 |