Secure two-party computation in sublinear (amortized) time

• DOI: 10.1145/2382196.2382251
• Publication Date: 2012-10-15T17:13:12Z
• Authors: S. Dov Gordon; Jonathan Katz; Vladimir Kolesnikov; Fernando Krell; Tal Malkin; Mariana Raykova; Yevgeniy Vahlis
• Keywords: Secure two-party computation; Sublinear function

Traditional approaches to generic secure computation begin by representing the function f being computed as a circuit. If depends on each of its input bits, this implies protocol with complexity at least linear in size. In fact, running time is inherent for non-trivial functions since party must "touch" every bit their lest information about other party's be leaked. This seems rule out many applications (e.g., database search) scenarios where inputs are huge.