Secure function evaluation (SFE) allows a set of mutually distrustful parties to
evaluate a function of their joint inputs without revealing their inputs
to each other.
SFE has been the focus of active research and recent work suggests that it can
be made practical. Unfortunately, current protocols and implementations have
inherent limitations that are hard to overcome using standard and practical
techniques. Among them are: (1) requiring participants to do work linear in
the size of the circuit representation of the function; (2) requiring all
parties to do the same amount of work; and (3) not being able to provide
A promising approach for overcoming these limitations is to augment the SFE
setting with a small set of untrusted servers that have no input to the
computation and that receive no output, but that make their computational
resources available to the parties. In this model, referred to as
server-aided SFE, the goal is to tradeoff the parties\' work at the
expense of the servers. Motivated by the emergence of public cloud services
such as Amazon EC2 and Microsoft Azure, recent work has explored the extent to
which server-aided SFE can be achieved with a single server.
In this work, we revisit the sever-aided setting from a practical perspective
and design single-server-aided SFE protocols that are considerably more
efficient than all previously-known protocols. We achieve this in part by
introducing several new techniques for garbled-circuit-based protocols,
including a new and efficient input-checking mechanism for cut-and-choose and a
new pipelining technique that works in the presence of malicious adversaries.
Furthermore, we extend the server-aided model to guarantee fairness which is an
important property to achieve in practice.
Finally, we implement and evaluate our constructions experimentally and show
that our protocols (regardless of the number of parties involved) yield implementations that are 4 and 6 times
faster than the most optimized two-party SFE implementation when the server is
assumed to be malicious and covert, respectively.