A Full Characterization of Functions that Imply Fair Coin Tossing and Ramifications to Fairness
A Full Characterization of Functions that Imply Fair Coin Tossing and Ramifications to Fairness
复制标题
隐含公平抛硬币的功能的完整表征及其对公平性的影响
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
T. Rabin
中科院分区：
文献类型：
--
作者：
Gilad Asharov;Yehuda Lindell;T. Rabin
众所周知，两方不可能公平地掷硬币（Cleve，STOC 1986）。这个结果意味着不可能安全地公平地计算任何可用于掷公平硬币的函数。在本文中，我们关注具有有限域的确定性布尔函数类，并询问在给定一个公平安全地计算函数的协议的情况下，此类中的哪些函数可以在信息理论上抛掷无偏硬币。我们提供了此类中函数的完整特征，这些特征暗示或不暗示公平抛硬币。这种特征扩展了我们对哪些函数不能安全、公平地计算的认识。此外，它还关注哪些函数可以潜在地公平地安全计算，因为不能用于公平抛硬币的函数不会被 Cleve 的不可能性结果排除（这是唯一已知的公平性不可能性结果）。除了上述内容之外，我们还得出了在两种可能的故障停止模型中实现公平性的可行性的推论。
It is well known that it is impossible for two parties to toss a coin fairly (Cleve, STOC 1986). This result implies that it is impossible to securely compute with fairness any function that can be used to toss a fair coin. In this paper, we focus on the class of deterministic Boolean functions with finite domain, and we ask for which functions in this class is it possible to information-theoretically toss an unbiased coin, given a protocol for securely computing the function with fairness. We provide a complete characterization of the functions in this class that imply and do not imply fair coin tossing. This characterization extends our knowledge of which functions cannot be securely computed with fairness. In addition, it provides a focus as to which functions may potentially be securely computed with fairness, since a function that cannot be used to fairly toss a coin is not ruled out by the impossibility result of Cleve (which is the only known impossibility result for fairness). In addition to the above, we draw corollaries to the feasibility of achieving fairness in two possible fail-stop models.