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.
