CT-ISG: Cross-Leveraging Cryptography with Learning Theory

Columbia University, New York NY

Investigators

Abstract

This research involves a detailed study of the connections between Cryptography and Computational Learning Theory. Cryptography is about manipulating information in order to achieve confidentiality, integrity, privacy, etc., while learning theory is about efficiently extracting information from some unknown object. Learning theory provides a rigorous basis for the practically important field of machine learning, and cryptography plays a similar role for the crucial area of computer security. In this research the investigators work to obtain new cryptographic results based on the presumed hardness of various problems in computational learning theory, and work to obtain new learning results via cryptography, thus extending and deepening the current understanding of both areas and the connections between them. The research is integrated with a plan to achieve broader impact through education by developing an advanced course on the connections between cryptography and learning theory at Columbia University and advising and guiding a diverse group of graduate students in their development as researchers and educators. In more detail, the research involves (i) constructing and applying new cryptographic primitives, such as public-key cryptosystems and pseudorandom generators with very low circuit complexity, from learning problems that are widely believed to be hard; (ii) continuing ongoing work on exploring the average-case learnability of various well-studied concept classes such as decision trees and DNF formulas; (iii) applying computational hardness of learning to establishing computational hardness of learning for various Boolean function classes, using tools from cryptography; (v) working to obtain computational separations between pairs of well-studied learning models by showing that learning problems that have polynomial-time algorithms in one model are intractable (under a cryptographic assumption) in the other model; and (vi) exploring the foundational issue of what are the minimal assumptions required to prove computational hardness of learning.