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

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

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.