### Towards Characterizing Complete Fairness in Secure Two-Party Computation

Gilad Asharov

##### Abstract

The well known impossibility result of Cleve (STOC 1986) implies that in general it is impossible to securely compute a function with \emph{complete fairness} without an honest majority. Since then, the accepted belief has been that \emph{nothing} non-trivial can be computed with complete fairness in the two party setting. The surprising work of Gordon, Hazay, Katz and Lindell (STOC 2008) shows that this belief is false, and that there exist \emph{some} non-trivial (deterministic, finite-domain) boolean functions that can be computed fairly. This raises the fundamental question of characterizing complete fairness in secure two-party computation. In this work we show that not only that some or few functions can be computed fairly, but rather an \emph{enormous number} of functions can be computed fairly. In fact, \emph{almost all} boolean functions with distinct domain sizes can be computed with complete fairness (for instance, more than $99.999\%$ of the boolean functions with domain sizes $31 \times 30$). The class of functions that is shown to be possible includes also rather involved and highly non-trivial tasks, such as set-membership, evaluation of a private (boolean) function, private matchmaking and set-disjointness. In addition, we demonstrate that fairness is not restricted to the class of symmetric boolean functions where both parties get the same output, which is the only known feasibility result. Specifically, we show that fairness is also possible for asymmetric boolean functions where the output of the parties is not necessarily the same. Moreover, we consider the class of functions with \emph{non-binary} output, and show that fairness is possible \emph{for any finite range}. The constructions are based on the protocol of Gordon et.~al, and its analysis uses tools from convex geometry.

Note: Full version of the TCC 2014 paper.

##### Metadata
Available format(s)
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in TCC 2014
DOI
10.1007/978-3-642-54242-8_13
Keywords
Complete fairnesssecure two-party computationfoundationsmalicious adversaries.
Contact author(s)
asharog @ cs biu ac il
History
2014-02-14: received
Short URL
https://ia.cr/2014/098
License

CC BY

BibTeX

@misc{cryptoeprint:2014/098,
author = {Gilad Asharov},
title = {Towards Characterizing Complete Fairness in Secure Two-Party Computation},
howpublished = {Cryptology ePrint Archive, Paper 2014/098},
year = {2014},
doi = {10.1007/978-3-642-54242-8_13},
note = {\url{https://eprint.iacr.org/2014/098}},
url = {https://eprint.iacr.org/2014/098}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.