New Techniques for Public-Key Cryptography

这项提议的目的是通过研究将假设复杂性降至最低和提高密码构造的效率这一根本目标来加强公钥密码学(PKC)的基础，并开发能够设计更高效和更健壮的安全计算协议的新技术、新工具。近年来，在PKC的基本问题方面取得了突破性的进展(其中一些是我的工作)，如构造了新的公钥加密(PKE)抵抗主动攻击(CCA)的方案，以及用于多方计算(MPC)问题的新技术，如私人信息检索(PIR)、私人集交集和非交互零知识(NIZK)。例如，我根据计算Diffie-Hellman(CDH)假设第一次构造陷门函数(TDF)的工作导致了随后的进步，例如第一次从TDF构造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.