期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2010
卷号：2010
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：In the {\em learning parities with noise} problem ---well-studied in learning theory and cryptography--- we
have access to an oracle that, each time we press a button,
returns a random vector a\GF(2)n together with a bit b\GF(2) that was computed as
au+ , where u\GF(2)n is a {\em secret} vector, and \GF(2) is a {\em noise} bit
that is 1 with some probability p. Say p=13 . The goal is to recover u. This task is
conjectured to be intractable.
Here we introduce a slight (?) variation of the model: upon pressing a button, we receive (say) 10 random vectors
a1a2a10\GF(2)n, and corresponding bits b1b2b10, of which at most 3 are
noisy. The oracle may arbitrarily decide which of the 10 bits to make noisy.
We exhibit a polynomial-time algorithm to recover the secret vector u given such an oracle.
We discuss generalizations of our result, including learning with more general noise patterns.
We can also learn
low-depth decision trees in the above structured noise model. We also consider the {\em learning with errors} problem
over \GF(q) and give (a) a 2O(n) algorithm in our structured noise setting (b) a slightly subexponential algorithm when the gaussian noise is small.
关键词：Lattice-based cryptography, learning decision trees, learning parities with noise, learning with errors, linearization
