Designing Fully Secure Protocols for Secure Two-Party Computation of Constant-Domain Functions
In a sense, a two-party protocol achieves fairness if the output from the computation is obtained simultaneously by both parties. A seminal result by Cleve (STOC 1986) states that fairness is impossible, in general. Surprisingly, Gordon et al. (JACM 2011)
- PDF / 1,496,774 Bytes
- 31 Pages / 439.37 x 666.142 pts Page_size
- 41 Downloads / 195 Views
Universitat Pompeu Fabra, Barcelona, Spain [email protected] 2 Tel Aviv University, Tel Aviv, Israel [email protected]
Abstract. In a sense, a two-party protocol achieves fairness if the output from the computation is obtained simultaneously by both parties. A seminal result by Cleve (STOC 1986) states that fairness is impossible, in general. Surprisingly, Gordon et al. (JACM 2011) showed that there exist interesting functions that are computable with fairness. The two results give rise to a distinction between fair functions and unfair ones. The question of characterizing these functions has been studied in a sequence of works leading to the complete characterization of (symmetric) Boolean functions by Asharov et al. (TCC 2015). In this paper, we design new fully secure protocols for functions that were previously unknown to be fair. To this end, our main technical contribution is a generic construction of a fully secure (fair) protocol, starting with a constant-round protocol satisfying limited security requirements. Our construction introduces new conceptual tools for the analysis of fairness that apply to arbitrary (constant-domain) functions. While the characterization remains open, we believe that our results lay the foundation for a deeper understanding of fairness. Keywords: Fairness · Secure two-party computation adversaries · Cryptographic protocols
1
·
Malicious
Introduction
A popular definition of two-party computation is that it enables two mutually distrusting parties to compute a joint function of their inputs while only revealing what the output suggests. However, the popular definition does not capture all the security requirements one may expect from such a computation. Among these requirements is fairness, which states that either both parties receive output or none of them do. It is a natural security requirement for many real-world tasks. V. Daza—Research supported by Project TEC2015-66228-P (MINECO/FEDER, UE). N. Makriyannis—Research supported by ERC starting grant 638121. c International Association for Cryptologic Research 2017 Y. Kalai and L. Reyzin (Eds.): TCC 2017, Part I, LNCS 10677, pp. 581–611, 2017. https://doi.org/10.1007/978-3-319-70500-2_20
582
V. Daza and N. Makriyannis
For example, when two parties are signing a contract, the contents of which may be legally binding, it is imperative that one party signs the contract if and only if the second party signs as well. The study of two-party computation started with the work of Yao [14] in 1982. Secure computation was expanded to the multiparty case by Goldreich, Micali, and Wigderson [10] in 1987. Flagship results from the theory of secure computation state that, when an absolute majority of honest parties can be guaranteed, every task can be realized with full security, i.e. the relevant protocols provide correctness, privacy, independence of inputs, as well as fairness. However, when the honest parties are in the minority, as it happens in the important two-party case, classic protocols satisfy a weaker notion of s
Data Loading...
