Abstract
In rational secret sharing, parties may prefer to mislead others in believing a wrong secret as the correct one over everybody obtaining the secret (i.e. a fair outcome). Prior rational secret reconstruction protocols for non-simultaneous channel only address the case where a fair outcome is preferred over misleading and hence are fair but not correct. Asharov and Lindell (2010) proposed the first and the only protocol that takes care of both the preferences. In this paper, we propose a new rational secret sharing protocol that addresses both the preferences and is fair and correct in the non-simultaneous channel model. Additionally, it is independent of the utility of misleading. Each rational party is given a list of sub-shares of shares of the actual secret and fake shares. In each round of the protocol each party sends the current element in its list to the other party and then reconstructs a share from the sub-shares obtained. The main idea is to use a checking share which is a share of the original secret as a protocol–induced membership auxiliary information to check whether the shares obtained till a certain round can be used to reconstruct the correct secret. We overcome the disadvantages of the presence of auxiliary information by using the time-delayed encryption scheme used by the protocol of Lysyanskaya and Segal (2010) that tolerates players with arbitrary side information. In our case, the side information used is not arbitrary but introduced by the mechanism/protocol designer to put all players on equal footing. We show that our protocol is in computational strict Nash equilibrium in the presence of protocol-induced auxiliary information.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abraham, I., Dolev, D., Gonen, R., Halpern, J.: Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation. In: PODC 2006 Proceedings of the Twenty-fifth Annual ACM Symposium on Principles of Distributed Computing, pp. 53–62. ACM, New York (2006)
Asharov, G., Lindell, Y.: Utility Dependence in Correct and Fair Rational Secret Sharing. Journal of Cryptology 24(1), 157–202 (2010)
Dodis, Y., Rabin, T.: Cryptography and Game Theory. In: Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V. (eds.) Algorithmic Game Theory, pp. 181–205. Cambridge University Press, New York (2007)
Goldreich, O.: Foundations of Cryptography Basic Applications, vol. II. Cambridge University Press, Cambridge (2004)
Gordon, S.D., Katz, J.: Rational Secret Sharing, Revisited. In: De Prisco, R., Yung, M. (eds.) SCN 2006. LNCS, vol. 4116, pp. 229–241. Springer, Heidelberg (2006)
Halpern, J., Teague, V.: Rational secret sharing and multiparty computation: extended abstract. In: STOC 2004 Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing, pp. 623–632. ACM, New York (2004)
Izmalkov, S., Micali, S., Lepinski, M.: Rational secure computation and ideal mechanism design. In: 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005, pp. 585–594 (2005)
Katz, J.: Bridging game theory and cryptography: Recent results and future directions. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 251–272. Springer, Heidelberg (2008)
Kol, G., Naor, M.: Games for exchanging information. In: STOC 2008 Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 423–432. ACM, New York (2008)
McGrew, R., Porter, R., Shoham, Y.: Towards a general theory of non-cooperative computation. In: TARK 2003 Proceedings of the 9th Conference on Theoretical Aspects of Rationality and Knowledge, pp. 59–71. ACM, New York (2003)
Shamir, A.: How to share a secret. Communications of the ACM 22(11), 612–613 (1979)
Shoham, Y., Tenneholtz, M.: Non-cooperative computation: Boolean functions with correctness and exclusivity. Theoretical Computer Science 343(1-2), 97–113 (2005)
Lysyanskaya, A., Triandopoulos, N.: Rationality and Adversarial Behavior in Multi-party Computation. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 180–197. Springer, Heidelberg (2006)
Mas-Collel, A., Whinston, M.D., Green, J.R.: Microeconomic Theory. Oxford University Press, New York (1995)
Fuchsbauer, G., Katz, J., Naccache, D.: Efficient Rational Secret Sharing in Standard Communication Networks. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 419–436. Springer, Heidelberg (2010)
Ong, S.J., Parkes, D.C., Rosen, A., Vadhan, S.: Fairness with an Honest Minority and a Rational Majority. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 36–53. Springer, Heidelberg (2009)
Kol, G., Naor, M.: Cryptography and Game Theory: Designing protocols for exchanging information. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 320–339. Springer, Heidelberg (2008)
Osborne, M., Rubinstein, A.: A Course in Game Theory. MIT Press, Cambridge (2004)
Groce, A., Katz, J.: Fair Computation with Rational Players. Cryptology ePrint Archive: Report 2011/396 (2011)
Gordon, S.D., Hazay, C., Katz, J., Lindell, Y.: Complete Fairness in Secure Two-Party Computation. Journal of the ACM 58(6), Article No. 24 (2011)
Lysyanskaya, A., Segal, A.: Rational Secret Sharing with Side Information in Point-to-Point Networks via Time Delayed Encryption. IACR Cryptology ePrint Archive: Report 2010/540. IACR (2010)
Dwork, C., Goldberg, A.V., Naor, M.: On Memory-bound Functions for Fighting Spam. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 426–444. Springer, Heidelberg (2003)
Rabin, M.O.: How to Exchange Secrets with Oblivious Transfer. Technical Report TR-8, Aiken Computation Lab, Harvard University (1981), http://eprint.iacr.org/2005/187
Gordon, S.D.: On Fairness in Secure Computation. Ph. D. Thesis. University of Maryland, College Park, USA (2010)
Rivest, R.L., Shamir, A., Wagner, D.A.: Time-lock puzzles and timed-release crypto. Technical report. Cambridge, MA, USA (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer International Publishing Switzerland
About this paper
Cite this paper
De, S.J., Pal, A.K. (2013). Achieving Correctness in Fair Rational Secret Sharing. In: Abdalla, M., Nita-Rotaru, C., Dahab, R. (eds) Cryptology and Network Security. CANS 2013. Lecture Notes in Computer Science, vol 8257. Springer, Cham. https://doi.org/10.1007/978-3-319-02937-5_8
Download citation
DOI: https://doi.org/10.1007/978-3-319-02937-5_8
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-02936-8
Online ISBN: 978-3-319-02937-5
eBook Packages: Computer ScienceComputer Science (R0)