AF: Small: Minimalist cryptography

现代密码学为资源丰富的消费者提供了令人印象深刻的虚拟自助餐，拥有强大的工具，如完全同态加密(允许提供商使用加密值进行计算，同时保持客户端数据的安全)和通用混淆(允许隐藏给定计算的目的)。但对于头脑更谦虚的用户来说，这些服务相对微不足道，他们寻求使用更负担得起的计算资源或在更经得起时间考验的假设下执行不那么崇高的任务。许多基本和实际动机的问题仍然没有得到回答，例如包含基本密码原语的最低复杂性类(本质上，最弱的，因此也是最便宜的计算模型)是什么？信息论技术可以为交互协议提供多大程度的保护，使其免受敌意入侵？或者，在固定的效率约束下，可以达到哪些可证明的安全级别？这个项目将为极简主义者提出一个密码学理论：一种足够灵活的密码学，可以为保守的消费者提供有吸引力的价值主张。个人投资机构将集中调查三个主要主题。首先，PI将研究伪随机基元的复杂性(例如，电路复杂性的几个概念)，例如伪随机生成器、伪随机函数和弱伪随机函数。其次，个人信息系统将为对抗环境中的健壮性开发信息论技术，加深容错通信和计算之间的联系。最后，在过于严格的安全要求阻碍实用性的环境中，PI将通过研究逐渐放松的安全概念和它们所能提供的效率收益，来改善安全和效率之间的权衡。拟议的研究活动与一项针对K-12、本科生和研究生的教育和推广计划紧密结合在一起，重点是鼓励代表性不足的少数群体参与。PI参与了针对小学生和高中女孩的计算机科学课程，这两个项目都是由计算机科学系的本科生女性教授的，她们将由PI指导。教育计划还包括与本科生和研究生课程的整合，通过将研究纳入私人投资机构教授的密码学入门和高级课程，以及通过个人研究项目和指导。

Modern cryptography offers an impressive virtual buffet to a consumer who is wealthy in resources, with powerful tools like fully homomorphic encryption (which allows a provider to compute with encrypted values while keeping the client's data safe) and general purpose obfuscation (which allows one to hide the purpose of a given computation). But for more modestly minded users, who seek to perform less lofty tasks using more affordable computing resources or under more time-tested assumptions, the offerings are comparatively paltry. Many fundamental and practically motivated questions remain unanswered, such as what are the lowest complexity classes (essentially, the weakest, and thus cheapest, computing models) containing basic cryptographic primitives? How much protection against adversarial intrusions can information-theoretic techniques provide for interactive protocols? Or, what levels of provable security are achievable within fixed efficiency constraints? This project will advance a theory of cryptography for the minimalist: a cryptography that is nimble enough to offer attractive value propositions to conservative consumers.The PIs will focus investigation on three main themes. First, the PIs will study complexity (e.g., several notions of circuit complexity) of pseudrandom primitives such as pseudorandom generators, pseudorandom functions, and weak pseudorandom functions. Secondly, the PIs will develop Information-theoretic techniques for robustness in adversarial environments, deepening connections between error-resilient communication and computation. Finally, the PIs will improve tradeoffs between security and efficiency in settings where overly stringent security requirements obstruct practicality, by studying incrementally relaxed notions of security and the gains in efficiency that they afford. The proposed research activity is tightly weaved with an educational and outreach plan for K-12, undergraduate, and graduate students, with an emphasis on encouraging participation of under-represented minorities. The PIs are involved in computer science programs for elementary school children and for high school girls, both being taught by undergraduate women in the department of Computer Science, who will be mentored by the PIs. The educational plan additionally includes integration with the undergraduate and graduate curriculum, through incorporation of the research into the introductory and advanced cryptography classes taught by the PIs, and through individual research projects and mentoring.