Cryptographic primitives based on hard learning problems. (English) Zbl 0870.94021

Stinson, Douglas R. (ed.), Advances in cryptology - CRYPTO ’93. 13th annual international cryptology conference, Santa Barbara, CA, USA, August 22 - 26, 1993. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 773, 278-291 (1994).
Modern cryptography has had considerable impact on the development of computational learning theory. Virtually every intractability result in L. G. Valiant’s model [Commun. ACM 27, 1134-1142 (1984; Zbl 0587.68077)] (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. 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.
For the entire collection see [Zbl 0856.00053].


94A60 Cryptography


Zbl 0587.68077