Thesis Defense: New Tools for On-the-Fly Secure Computation

Abstract: The natural generalization of the Diffie–Hellman key exchange to secure two-party computation is a protocol where two parties non-interactively (i.e., "on-the-fly") compute secret shares of a function over their private inputs.

Unfortunately, the only known way to realize such a protocol is by using spooky encryption of Dodis et al. which requires assuming either learning with errors (LWE) or indistinguishability obfuscation. In the context of secure computation, these assumptions appear to be unnecessarily "supernatural" given that oblivious transfer is often sufficient. Haunted by this state of affairs, we ask the following question:

Can we realize "on-the-fly" secure computation without spooky encryption?

In positively resolving this question, we obtain a series of new results that span from basic building blocks with concretely efficient instantiations to new theoretical tools. Applications of our results include new techniques for efficient multi-party computation, attribute-based non-interactive key exchange, generic compilers for correlation-intractable hashing and rate-1 FHE from LWE, and an alternative way of constructing output-succinct secure computation as studied by Hubáček and Wichs.