New Techniques for Public-Key Cryptography

该提案的目的是加强公钥密码学（PKC）的基础，通过调查的基本目标，最大限度地减少假设的复杂性和提高效率的密码结构，并开发技术和工具，使设计更有效和更强大的安全计算协议。近年来，在PKC的基本问题的进展（其中一些是在我的工作）已经导致了突破性的结果，如公钥加密（PKE）方案抵抗主动攻击（CCA）的新结构，和多方计算（MPC）问题的新技术，如私人信息检索（PIR），私人集合交集，和非交互式零知识（NIZK）。例如，我从计算Diffie-Hellman（CDH）假设中首次构建陷门函数（TDFs）的工作导致了后续的进步，例如从TDFs中首次构建CCA安全的PKE，从Diffie-Hellman假设中首次构建PIR，以及引入一个称为陷门哈希的新概念，这反过来又导致了非交互式零知识的新可行性结果。我提出的研究将进一步形式化这种关系，并将解决公钥密码学中的相关问题。这项研究将把公钥密码学放在一个更坚实的基础上，将引入一些技术，这些技术将导致各种具有增强安全性/功能的MPC协议，并将提高我们对密码技术的能力和局限性的理解。 该项目将侧重于解决上述问题的三个主要方面。首先，我将从最小的假设和更高的效率实现核心PKC原语及其家族。这种原语的示例包括陷门函数/置换、陷门散列方案和具有最小通信的不经意传输协议。其次，我将应用这些技术来设计MPC问题，提高效率和增强功能。最后，我将确定并正式确定可能存在的障碍，对上述目标。这将通过证明上述目标的假设复杂性和构造效率的下限来进行。公钥密码学在互联网安全协议的设计中起着不可或缺的作用。除了推进科学知识，我提议的研究还将开发有可能部署在各种隐私增强技术中的工具。这些工具具有社会效益，可以在敏感数据上进行计算，同时保持数据的私密性。例如，我提出的MPC问题（如私有集合交集和私有信息检索）的目标将为许多重要的现实世界应用程序（如隐私保护数据分析，安全联系人跟踪等）带来有效的协议。

The aim of this proposal is to strengthen the foundations of public-key cryptography (PKC), by investigating the fundamental goals of minimizing assumption complexity and improving the efficiency of cryptographic constructions, and to develop techniques and tools that will enable the design of more efficient and robust secure-computation protocols. In recent years advances in basic problems in PKC (some of which were made in my work) have led to breakthrough results, such as new constructions of public-key encryption (PKE) schemes resisting active attacks (CCA), and new techniques for multi-party computation (MPC) problems such as private-information retrieval (PIR), private-set intersection, and non-interactive zero knowledge (NIZK). For example, my work on the first construction of trapdoor functions (TDFs) from the Computational Diffie-Hellman (CDH) Assumption led to subsequent advancements, such as the first construction of CCA-secure PKE from TDFs, the first construction of PIR from the Diffie-Hellman assumption, and the introduction of a new notion called trapdoor hash, which in turn led to new feasibility results on non-interactive zero knowledge. My proposed research will formalize this relationship further and will tackle associated problems in public-key cryptography. The investigation will put public-key cryptography on a firmer foundation, will introduce techniques that will lead to various MPC protocols with enhanced security/functionality, and will improve out understanding of capabilities and limits of cryptographic techniques. The project will focus on three main thrusts to address the above problems. First, I will realize core PKC primitives, and their families, from minimal assumptions and with improved efficiency. Examples of such primitives include trapdoor functions/permutations, trapdoor hash schemes and oblivious transfer protocols with minimal communication. Second, I will apply these techniques to design MPC problems with improved efficiency and enhanced functionality. Finally, I will identify and formalize barriers that may exist against the above goals. This will be carried out by proving lower bounds on the assumption complexity and efficiency of constructions for the above goals. Public-key cryptography plays an integral role in the design of secure protocols for the internet. In addition to advancing scientific knowledge, my proposed research will develop tools that have the potential of being deployed in various privacy-enhancing technologies. Such tools have societal benefits, enabling computation on sensitive data while keeping the data private. For example, my proposed goals for MPC problems (such as private-set intersection and private-information retrieval) will lead to efficient protocols for many important real-world applications such as privacy-preserving data analytics, secure contact tracing, etc.