CT-ISG: Cross-Leveraging Cryptography with Learning Theory

本研究涉及密码学和计算学习理论之间的联系的详细研究。 密码学是关于操纵信息以实现机密性，完整性，隐私等，而学习理论是关于从一些未知对象中有效地提取信息。 学习理论为机器学习的重要实践领域提供了严格的基础，而密码学在计算机安全的关键领域也扮演着类似的角色。 在这项研究中，研究人员根据计算学习理论中各种问题的假设难度来获得新的密码学结果，并通过密码学获得新的学习结果，从而扩展和深化了当前对这两个领域及其之间联系的理解。 该研究与一项计划相结合，通过在哥伦比亚大学开发一门关于密码学和学习理论之间联系的高级课程，并建议和指导不同群体的研究生作为研究人员和教育工作者的发展，通过教育实现更广泛的影响。更详细地说，研究涉及（i）构建和应用新的密码原语，如公钥密码系统和伪随机发生器具有非常低的电路复杂性，从学习问题，被广泛认为是困难的;（ii）继续正在进行的工作，探索平均情况下学习的各种研究的概念类，如决策树和DNF公式;（iii）使用密码学工具，应用学习的计算难度来建立各种布尔函数类的学习的计算难度;（v）通过表明具有多项式的学习问题，努力获得经过充分研究的学习模型对之间的计算分离一个模型中的时间算法是棘手的（在密码学假设下）在另一个模型中;（vi）探索什么是证明学习的计算硬度所需的最小假设的基础问题。

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.