TY - GEN

T1 - Fast Learning Requires Good Memory

T2 - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016

AU - Raz, Ran

PY - 2016/12/14

Y1 - 2016/12/14

N2 - 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, Valiant and Wager [15] 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, b1), (a2, b2)..., where each at is uniformly distributed over {0,1}n and bt is the inner product of at and x, modulo 2. We show that any algorithm for parity learning, that uses less than n2/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 provenly and unconditionally secure as long as the attacker uses less than n2/25 memory 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.

AB - 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, Valiant and Wager [15] 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, b1), (a2, b2)..., where each at is uniformly distributed over {0,1}n and bt is the inner product of at and x, modulo 2. We show that any algorithm for parity learning, that uses less than n2/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 provenly and unconditionally secure as long as the attacker uses less than n2/25 memory 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.

UR - http://www.scopus.com/inward/record.url?scp=85009402308&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85009402308&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2016.36

DO - 10.1109/FOCS.2016.36

M3 - Conference contribution

AN - SCOPUS:85009402308

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 266

EP - 275

BT - Proceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016

PB - IEEE Computer Society

Y2 - 9 October 2016 through 11 October 2016

ER -