Access Restriction

Author Gordon, S Dov ♦ Hazay, Carmit ♦ Katz, Jonathan ♦ Lindell, Yehuda
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2011
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Cryptography ♦ Fairness ♦ Secure computation
Abstract In the setting of secure two-party computation, two mutually distrusting parties wish to compute some function of their inputs while preserving, to the extent possible, various security properties such as privacy, correctness, and more. One desirable property is $\textit{fairness}$ which guarantees, informally, that if one party receives its output, then the other party does too. Cleve [1986] showed that complete fairness cannot be achieved in general without an honest majority. Since then, the accepted folklore has been that $\textit{nothing}$ non-trivial can be computed with complete fairness in the two-party setting. We demonstrate that this folklore belief is $\textit{false}$ by showing completely fair protocols for various nontrivial functions in the two-party setting based on standard cryptographic assumptions. We first show feasibility of obtaining complete fairness when computing any function over polynomial-size domains that does not contain an “embedded XOR”; this class of functions includes boolean AND/OR as well as Yao’s “millionaires’ problem”. We also demonstrate feasibility for certain functions that do contain an embedded XOR, though we prove a lower bound showing that any completely fair protocol for such functions must have round complexity super-logarithmic in the security parameter. Our results demonstrate that the question of completely fair secure computation without an honest majority is far from closed.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2011-12-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 58
Issue Number 6
Page Count 37
Starting Page 1
Ending Page 37

Open content in new tab

   Open content in new tab
Source: ACM Digital Library