This paper proves that learning certain classes of Boolean functions, such as Boolean formulae, deterministic finite automata, and constant-depth threshold circuits, is intractable in the distribution-free model of learning. These results are representation-independent, meaning they hold regardless of how the learner represents its hypotheses. The authors show that a polynomial-time learning algorithm for these classes would have significant implications for cryptography, including the ability to break RSA, factor Blum integers, and detect quadratic residues. The results hold even if the learning algorithm only slightly outperforms random guessing. The paper also applies these findings to show that approximating a generalization of graph coloring is intractable. The key insight is the duality between learning and cryptography, where cryptographic functions are difficult to learn, and learning these functions would imply the ability to solve hard cryptographic problems. The paper defines various representation classes and discusses their learnability, using cryptographic assumptions to establish hardness results. It also provides a framework for proving hardness results based on trapdoor functions and applies these results to show the difficulty of learning various representation classes under cryptographic assumptions.This paper proves that learning certain classes of Boolean functions, such as Boolean formulae, deterministic finite automata, and constant-depth threshold circuits, is intractable in the distribution-free model of learning. These results are representation-independent, meaning they hold regardless of how the learner represents its hypotheses. The authors show that a polynomial-time learning algorithm for these classes would have significant implications for cryptography, including the ability to break RSA, factor Blum integers, and detect quadratic residues. The results hold even if the learning algorithm only slightly outperforms random guessing. The paper also applies these findings to show that approximating a generalization of graph coloring is intractable. The key insight is the duality between learning and cryptography, where cryptographic functions are difficult to learn, and learning these functions would imply the ability to solve hard cryptographic problems. The paper defines various representation classes and discusses their learnability, using cryptographic assumptions to establish hardness results. It also provides a framework for proving hardness results based on trapdoor functions and applies these results to show the difficulty of learning various representation classes under cryptographic assumptions.