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.