TY - GEN

T1 - Time-space hardness of learning sparse parities

AU - Kol, Gillat

AU - Raz, Ran

AU - Tal, Avishay

N1 - Publisher Copyright:
© 2017 ACM.
Copyright:
Copyright 2018 Elsevier B.V., All rights reserved.

PY - 2017/6/19

Y1 - 2017/6/19

N2 - We define a concept class F to be time-space hard (or memory-samples hard) if any learning algorithm for 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 [Raz, FOCS'16]. Building on [Raz, FOCS'16], we show that the class of all sparse parities of Hamming weight l is time-space hard, as long as l ≥ ω(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 ω(log n) ≤ k ≤ 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 provably and unconditionally secure as long as the attacker uses at most o(nk) memory bits and the scheme is used at most 2o(k) times. Previously, this was known only for k = n [Raz, FOCS'16].

AB - We define a concept class F to be time-space hard (or memory-samples hard) if any learning algorithm for 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 [Raz, FOCS'16]. Building on [Raz, FOCS'16], we show that the class of all sparse parities of Hamming weight l is time-space hard, as long as l ≥ ω(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 ω(log n) ≤ k ≤ 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 provably and unconditionally secure as long as the attacker uses at most o(nk) memory bits and the scheme is used at most 2o(k) times. Previously, this was known only for k = n [Raz, FOCS'16].

KW - Bounded storage cryptography

KW - Branching program

KW - Fourier analysis

KW - Lower bounds

KW - PAC learning

KW - Time-space tradeoff

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

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

U2 - 10.1145/3055399.3055430

DO - 10.1145/3055399.3055430

M3 - Conference contribution

AN - SCOPUS:85024404621

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 1067

EP - 1080

BT - STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing

A2 - McKenzie, Pierre

A2 - King, Valerie

A2 - Hatami, Hamed

PB - Association for Computing Machinery

T2 - 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017

Y2 - 19 June 2017 through 23 June 2017

ER -