Secure computation of constant-depth circuits with applications to database search problems

摘要: Motivated by database search problems such as partial match or nearest neighbor, we present secure multiparty computation protocols for constant-depth circuits. Specifically, a circuit C of size s with an m-bit input x, obtain the following types protocols. – In setting where k≥polylog(s) servers hold and client holds protocol in which privately learns C(x) communicating O(m) bits each server. – x is arbitrarily distributed between parties who all know C, evaluating using O(m ·poly(k)) communication. Both tolerate t=k/polylog(s) dishonest their computational complexity nearly linear s. particular, are optimal “up to polylog factors” respect communication, local computation, minimal number participating parties. We then apply above results sublinear-communication natural problems. For instance, problem on n points {0,1}m get $k \approx \frac{1}{2} log n$ servers, server computation. Applying previous this would either require Ω(nm) Ω(m) super-polynomial