SaTC: CORE: Small: Nested Black-Box Constructions in Cryptography

安全计算是密码学中的一个广泛主题，涉及如何在分布式私有数据上计算函数。在最基本的级别上，此任务的安全性来自简单的低级加密原语。这个领域的一个中心问题是，是否需要低级原语的代码来安全地计算所需的函数。这个问题在很大程度上还没有被加密函数所探索。该项目的新颖之处是对经典加密原语的新增强，以及一种新的范例，可以安全地计算从它们实例化的任何函数，而不需要完整的代码。该项目的影响是发现新的通用工具，这些工具有可能改变黑盒安全计算领域。该项目重新审视了只依赖于其他加密原语的输入/输出行为而不依赖于其代码的函数的情况。安全计算这类函数的现有方法需要它们所依赖的原语的代码，即使函数本身不需要。这类函数被称为嵌套黑盒函数，它们恰好是导致安全计算效率低下的主要原因。有人认为，如果经典的加密原语（如单向函数）允许足够强大的安全计算协议，那么在计算从它们实例化的嵌套黑盒函数时，就有可能避免需要它们的代码。本项目探索了以黑盒方式从经典原语构建这些增强原语的方法，以及安全地计算从它们实例化的嵌套黑盒函数的通用方法。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Secure computation is a broad topic in cryptography that deals with how to compute functions over distributed private data. At the most basic level, the security of this task is derived from simple, low level, cryptographic primitives. A central question in this area is whether the code of the low level primitives is required to securely compute the desired function. This question has remained largely unexplored for the case of cryptographic functions. The project's novelties are new enhancements to classical cryptographic primitives, and a new paradigm to securely compute any function instantiated from them without requiring its full code. The project's impacts are discovery of new and general-purpose tools that have the potential to transform the area of black-box secure computation.The project takes a fresh look at the case of functions that depend only on input/output behavior of other cryptographic primitives and not their code. Existing methods to securely compute such functions require the code of the primitives they depend on even though the functions themselves do not. Such functions, referred to as nested black-box functions, happen to be a major source of inefficiency in secure computation. It is argued that if classical cryptographic primitives such as one-way functions admit sufficiently powerful secure computation protocols, it may be possible to avoid the need for their code when computing nested black-box functions instantiated from them. This project explores ways to construct these enhanced primitives from classical ones in a black-box manner, and general-purpose methods to securely compute nested black-box functions instantiated from them.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.