Title: Towards Concretely-Efficient Secure Computation: Fast Conditional Branching, Oblivious RAM, and Special-Purpose Protocols

Stanislav Peceny

Ph.D. Student

Georgia Institute of Technology

Date: Wednesday, Apr 26, 2023

Time: 10:00am - 11:00am (ET)

Location: Coda C0903 "Ansley"

Proposal Committee:

Dr. Vladimir Kolesnikov (Advisor, Georgia Institute of Technology)

Dr. David Heath (UIUC)

Dr. Mustaque Ahamad (Georgia Institute of Technology)

Dr. Alexandra Boldyreva (Georgia Institute of Technology)

Dr. Wenke Lee (Georgia Institute of Technology)

Abstract:

What is MPC and why do we need it

Parties such as companies and government agencies often want to compute on private data. If this data is sensitive, e.g., is legally protected or is commercially valuable, the parties may not be able to share it, thus precluding the computation itself. Secure Multi-Party Computation (MPC) is an area of cryptography that enables parties to compute on private data without revealing it to counterparties.  In these scenarios, MPC serves as the essential enabler of such computations.  Additionally, MPC enhances privacy in the settings where data is permitted to be shared generally or under certain conditions.

Generic and special-purpose MPC

MPC techniques can be classified into two categories:

• Generic MPC concerns techniques that are applicable to secure evaluation of arbitrary functions.   A function is compiled into a Boolean or arithmetic circuit and then sequentially evaluated under encryption gate by gate.  The trade-off is that current generic techniques are cost-prohibitive for many applications, in particular functions with large circuit representation. Techniques of interest here include any general primitives and protocols, such as oblivious RAM access and techniques that work for broad families of functions, such as zero knowledge. 
• Special-purpose MPC focuses on efficient evaluation of specific functions, for which generic MPC techniques are not sufficiently performant. Special-purpose MPC is highly optimized to specific use cases, such as machine learning.

What does this dissertation achieve

In this dissertation, I will present improvements in both categories:

In the Generic MPC setting:

• “MOTIF” and “Masked Triples” add efficient conditional branching to multi-party protocols.  Without this improvement, MPC evaluation of a program IF or SWITCH statements consumes communication proportional to the sum of the program branches.  Namely, for b branches, prior MPC evaluation uses O(b) communication. MOTIF (and its follow-up Masked Triples) introduce new techniques that show it suffices to use communication proportional to only the single longest program branch, i.e. O(1).
• “Garbling, Stacked and Staggered” is (similarly to MOTIF and Masked Triples) motivated by conditional branching in MPC. Unlike MOTIF and Masked Triples, this work improves computation while retaining communication improvements of state-of-the-art branching techniques. This work significantly improves 2-party evaluation of k-out-of-n conditional branches, whose indices are known (or eventually revealed) to one party. Namely, in our work, each party evaluates the total of O(n) branches, a significant improvement over the O(n · k) evaluations needed by prior techniques.
• “Shared-Output Client-Server ORAM (SOCS-ORAM)” observes that input-dependent array access in secure computation is still prohibitively expensive for applications with hard performance constraints. In this work we take a pragmatic approach, exploring how concretely cheap input-dependent access could be made if we are willing to allow one party to learn the access pattern. We present a one-round-per-access SOCS-ORAM protocol that takes essentially no overhead beyond network latency.

In the Special-Purpose MPC setting, we design an algorithm that is tailored to training a logistic regression model between two parties. The key challenge is to design an accurate approximation of a real-valued sigmoid function that is friendly to MPC. Our main contributions are accurately approximating the sigmoid function in only 4 communication rounds while communicating only 0.5KB across the parties and designing an end-to-end system to evaluate our contribution.* 

For the rest of my PhD, I intend to investigate the following directions and tasks:

• Improve write-up and reimplement the function secret sharing based section of my logistic regression paper to improve computational efficiency
• Complete project on deep learning (research complete but writeup and implementation missing)
• Extend SOCS-ORAM to guarantee stronger privacy without sacrificing efficiency
• Expand on the Special-Purpose MPC setting by designing efficient protocols for decision trees and sorting algorithms

*Note this work and a subsequent work (in preparation) were done jointly with another student (UIUC), where both authors are ‘first authors’. We will ensure that we don’t have overlapping claims in our theses.