AF: Small: Minimalist cryptography

AF：小：极简密码学

• 批准号: 1423306
• 负责人: Allison Bishop
• 金额: $ 40万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-08-01 至 2019-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1423306&HistoricalAwards=false
• 关键词: AF; Small; Minimalist; cryptography

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.

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