Abstract
Modern cryptography has had considerable impact on the development of computational learning theory. Virtually every intractability result in Valiant’s model [13] (which is representation-independent in the sense that it does not rely on an artificial syntactic restriction on the learning algorithm’s hypotheses) has at its heart a cryptographic construction [4, 9, 1, 10]. In this paper, we give results in the reverse direction by showing how to construct several cryptographic primitives based on certain assumptions on the difficulty of learning. In doing so, we develop further a line of thought introduced by Impagliazzo and Levin [6].
Supported in part by an NSF Postdoctoral Fellowship.
Supported in part by NSF grant CCR-9119319.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Dana Angluin and Michael Kharitonov. When won’t membership queries help? In Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, pages 444–454, May 1991.
E. Berlekamp, R. McEliece, and H. van Tilborg. On the inherent intractability of certain coding problems. IEEE Transactions on Information Theory, 24, 1978.
O. Goldreich, H. Krawczyk, and M. Luby. On the existence of pseudorandom generators. In 29th Annual Symposium on Foundations of Computer Science, pages 12–21, October 1988.
Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions. Journal of the ACM, 33(4):792–807, October 1986.
Shafi Goldwasser and Silvio Micali. Probabilistic encryption. JCSS, 28(2):270–299, April 1984.
R. Impagliazzo and L. Levin. No better ways to generate hard NP instances than picking uniformly at random. In 31st Annual Symposium on Foundations of Computer Science, October 1990.
R. Impagliazzo, L. Levin, and M. Luby. Pseudorandom generation from one-way functions. In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, May 1989.
Michael Kearns. Efficient noise-tolerant learning from statistical queries. In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, May 1993.
Michael Kearns and Leslie G. Valiant. Cryptographic limitations on learning Boolean formulae and finite automata. In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 433–444, May 1989. To appear, Journal of the Association for Computing Machinery.
M. Kharitonov. Cryptographic hardness of distribution-specific learning. In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, May 1993.
R. J. McEliece. A Public-Key System Based on Algebraic Coding Theory, pages 114–116. Jet Propulsion Lab, 1978. DSN Progress Report 44.
N. Nisan and A. Wigderson. Hardness vs. randomness. In 29th Annual Symposium on Foundations of Computer Science, pages 2–12, October 1988.
L. G. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134–1142, November 1984.
Andrew C. Yao. Theory and applications of trapdoor functions. In 23rd Annual Symposium on Foundations of Computer Science, pages 80–91, 1982.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Blum, A., Furst, M., Kearns, M., Lipton, R.J. (1994). Cryptographic Primitives Based on Hard Learning Problems. In: Stinson, D.R. (eds) Advances in Cryptology — CRYPTO’ 93. CRYPTO 1993. Lecture Notes in Computer Science, vol 773. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48329-2_24
Download citation
DOI: https://doi.org/10.1007/3-540-48329-2_24
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57766-9
Online ISBN: 978-3-540-48329-8
eBook Packages: Springer Book Archive