Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. You can also get this service via
To receive your credentials via mail again, please click here.
You can also access the full news archive.
The algorithm performance information provided by this and the preceding paper is aimed at making practical comparisons possible. Comparisons that take both the cost of pre-computation and the efficiency of the online phase into account, at parameters that achieve a common success rate, can now be carried out with ease. Comparisons can be based on the expected execution complexities rather than the worst case complexities, and details such as the effects of false alarms and various storage optimization techniques need no longer be ignored.
A large portion of this paper is allocated to accurately analyzing the execution behavior of the perfect table distinguished point method. In particular, we obtain a closed-form formula for the average length of chains associated with a perfect distinguished point table.
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.