Paper 2009/373
Utility Dependence in Correct and Fair Rational Secret Sharing
Gilad Asharov and Yehuda Lindell
Abstract
The problem of carrying out cryptographic computations when the participating parties are \emph{rational} in a game-theoretic sense has recently gained much attention. One problem that has been studied considerably is that of rational secret sharing. In this setting, the aim is to construct a mechanism (protocol) so that parties behaving rationally have incentive to cooperate and provide their shares in the reconstruction phase, even if each party prefers to be the only one to learn the secret. Although this question was only recently asked by Halpern and Teague (STOC 2004), a number of works with beautiful ideas have been presented to solve this problem. However, they all have the property that the protocols constructed need to know the actual utility values of the parties (or at least a bound on them). This assumption is very problematic because the utilities of parties are not public knowledge. We ask whether this \emph{dependence on the actual utility values} is really necessary and prove that in the case of two parties, rational secret sharing cannot be achieved without it. On the positive side, we show that in the multiparty case it is possible to construct a single mechanism that works for all (polynomial) utility functions. Our protocol has an expected number of rounds that is constant, and is optimally resilient to coalitions. In addition to the above, we observe that the known protocols for rational secret sharing that do not assume simultaneous channels all suffer from the problem that one of the parties can cause the others to output an incorrect value. (This problem arises when a party gains higher utility by having another output an incorrect value than by learning the secret itself; we argue that such a scenario needs to be considered.) We show that this problem is inherent in the non-simultaneous channels model, unless the actual values of the parties' utilities from this attack is known, in which case it is possible to prevent this from happening.
Note: This paper contains many additional results that do not appear at all in the CRYPTO conference version. In addition, full proofs are given for all results.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. A preliminary version of this paper appeared in CRYPTO 2009; this is the full version.
- Keywords
- rational secret sharinggame theory and cryptography
- Contact author(s)
- lindell @ cs biu ac il
- History
- 2010-03-05: last of 4 revisions
- 2009-08-03: received
- See all versions
- Short URL
- https://ia.cr/2009/373
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2009/373,
author = {Gilad Asharov and Yehuda Lindell},
title = {Utility Dependence in Correct and Fair Rational Secret Sharing},
howpublished = {Cryptology {ePrint} Archive, Paper 2009/373},
year = {2009},
url = {https://eprint.iacr.org/2009/373}
}