Dov Gordon, George Mason University

Abstract

We present a new 4-party protocol for secure computation that is secure against a single malicious corruption.  Our protocol requires sending just 1.5 ring elements per party, per gate, which in the special case of Boolean circuits, this amounts to sending 1.5 bits per party, per gate.  This is extremely useful in a setting where many users outsource their computation over large volumes of secret-shared data to a small number of servers. Technically, our key technique can be viewed as a variant of the “dual execution” approach, but, because we rely on four parties instead of two, we can avoid any leakage, achieving the standard notion of malicious security.

Video