## Abstract

We prove that any algorithm for learning parities requires either a memory of quadratic size or an exponential number of samples. This proves a recent conjecture of Steinhardt et al. (2016) and shows that for some learning problems, a large storage space is crucial. More formally, in the problem of parity learning, an unknown string x ∈ {0, 1} ^{n} was chosen uniformly at random. A learner tries to learn x from a stream of samples (a1,b _{1} ), (a2,b _{2} ) . . ., where each a _{t} is uniformly distributed over {0, 1} ^{n} and b _{t} is the inner product of a _{t} and x, modulo 2. We show that any algorithm for 2 parity learning that uses less than ^{n} _{25} bits of memory requires an exponential number of samples. Previously, there was no non-trivial lower bound on the number of samples needed for any learning problem, even if the allowed memory size is O(n) (where n is the space needed to store one sample). We also give an application of our result in the field of bounded-storage cryptography. We show an encryption scheme that requires a private key of length n, as well as time complexity of n per encryption/decryption of each bit, and is provably and unconditionally secure as long as the attacker uses less than ^{n} _{25} memory 2 bits and the scheme is used at most an exponential number of times. Previous works on bounded-storage cryptography assumed that the memory size used by the attacker is at most linear in the time needed for encryption/decryption.

Original language | English (US) |
---|---|

Article number | 3 |

Journal | Journal of the ACM |

Volume | 66 |

Issue number | 1 |

DOIs | |

State | Published - Dec 2018 |

## All Science Journal Classification (ASJC) codes

- Software
- Control and Systems Engineering
- Information Systems
- Hardware and Architecture
- Artificial Intelligence

## Keywords

- Bounded storage cryptography
- Branching program
- Learning
- Lower bounds
- Time-space tradeoff