ECCC-Report TR16-113https://eccc.weizmann.ac.il/report/2016/113Comments and Revisions published for TR16-113en-usFri, 22 Jul 2016 12:24:04 +0300
Paper TR16-113
| Time-Space Hardness of Learning Sparse Parities |
Gillat Kol,
Ran Raz,
Avishay Tal
https://eccc.weizmann.ac.il/report/2016/113We define a concept class ${\cal F}$ to be time-space hard (or memory-samples hard) if any learning algorithm for ${\cal F}$ requires either a memory of size super-linear in $n$ or a number of samples super-polynomial in $n$, where $n$ is the length of one sample.
A recent work shows that the class of all parity functions is time-space hard [Raz16]. Building on [Raz16], we show that the class of all sparse parities of Hamming weight $\ell$ is time-space hard, as long as $\ell \geq \omega(\log n / \log \log n)$. Consequently, linear-size DNF Formulas, linear-size Decision Trees and logarithmic-size Juntas are all time-space hard. Our result is more general and provides time-space lower bounds for learning any concept class of parity functions.
We give applications of our results in the field of bounded-storage cryptography. For example, for every $\omega(\log n) \leq k \leq n$, we obtain an encryption scheme that requires a private key of length $k$, and time complexity of $n$ per encryption/decryption of each bit, and is provenly and unconditionally secure as long as the attacker uses at most $o(nk)$ memory bits and the scheme is used at most $2^{o(k)}$ times. Previously, this was known only for $k=n$ [Raz16].Fri, 22 Jul 2016 12:24:04 +0300https://eccc.weizmann.ac.il/report/2016/113