×

Efficient rational secret sharing in standard communication networks. (English) Zbl 1274.94137

Micciancio, Daniele (ed.), Theory of cryptography. 7th theory of cryptography conference, TCC 2010, Zurich, Switzerland, February 9–11, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-11798-5/pbk). Lecture Notes in Computer Science 5978, 419-436 (2010).
Summary: We propose a new methodology for rational secret sharing leading to various instantiations (in both the two-party and multi-party settings) that are simple and efficient in terms of computation, share size, and round complexity. Our protocols do not require physical assumptions or simultaneous channels, and can even be run over asynchronous, point-to-point networks.
We also propose new equilibrium notions (namely, computational versions of strict Nash equilibrium and stability with respect to trembles) and prove that our protocols satisfy them. These notions guarantee, roughly speaking, that at each point in the protocol there is a unique legal message a party can send. This, in turn, ensures that protocol messages cannot be used as subliminal channels, something achieved in prior work only by making strong assumptions on the communication network.
For the entire collection see [Zbl 1181.94004].

MSC:

94A62 Authentication, digital signatures and secret sharing
68M12 Network protocols
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abraham, I., Dolev, D., Gonen, R., Halpern, J.: Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation. In: 25th ACM Symposium Annual on Principles of Distributed Computing, pp. 53–62. ACM Press, New York (2006) · Zbl 1314.68051
[2] Alwen, J., Katz, J., Lindell, Y., Persiano, G., Shelat, A., Visconti, I.: Collusion-free multiparty computation in the mediated model. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 524–540. Springer, Heidelberg (2009) · Zbl 1252.94042
[3] Alwen, J., Shelat, A., Visconti, I.: Collusion-free protocols in the mediated model. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 497–514. Springer, Heidelberg (2008) · Zbl 1183.68079
[4] Asharov, G., Lindell, Y.: Utility dependence in correct and fair rational secret sharing. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 559–576. Springer, Heidelberg (2009), A full version, containing additional results: http://eprint.iacr.org/209/373 · Zbl 1252.94105
[5] Blakley, G.: Safeguarding cryptographic keys. In: Proc. AFIPS National Computer Conference, vol. 48, pp. 313–317 (1979)
[6] Dodis, Y.: Efficient construction of (distributed) verifiable random functions. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 1–17. Springer, Heidelberg (2002) · Zbl 1033.94521
[7] Dodis, Y., Rabin, T.: Cryptography and game theory. In: Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V. (eds.) Algorithmic Game Theory, pp. 181–207. Cambridge University Press, Cambridge (2007)
[8] Dodis, Y., Yampolskiy, A.: A verifiable random function with short proofs and keys. In: Vaudenay, S. (ed.) PKC 2005. LNCS, vol. 3386, pp. 416–431. Springer, Heidelberg (2005) · Zbl 1081.94521
[9] Fuchsbauer, G., Katz, J., Naccache, D.: Efficient rational secret sharing in standard communication networks, http://eprint.iacr.org/2008/488 · Zbl 1274.94137
[10] Gordon, S.D., Hazay, C., Katz, J., Lindell, Y.: Complete fairness in secure two-party computation. In: 40th Annual ACM Symposium on Theory of Computing (STOC), pp. 413–422. ACM Press, New York (2008) · Zbl 1231.94062
[11] 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) · Zbl 1152.94450
[12] Gordon, S.D., Katz, J.: Partial fairness in secure two-party computation (2008), http://eprint.iacr.org/2008/206 · Zbl 1272.94032
[13] Halpern, J., Teague, V.: Rational secret sharing and multiparty computation: Extended abstract. In: 36th Annual ACM Symposium on Theory of Computing (STOC), pp. 623–632. ACM Press, New York (2004) · Zbl 1192.94119
[14] Izmalkov, S., Lepinski, M., Micali, S.: Verifiably secure devices. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 273–301. Springer, Heidelberg (2008) · Zbl 1162.94370
[15] Izmalkov, S., Micali, S., Lepinski, M.: Rational secure computation and ideal mechanism design. In: 46th Annual Symposium on Foundations of Computer Science (FOCS), pp. 585–595. IEEE, Los Alamitos (2005)
[16] 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) · Zbl 1162.94373
[17] Katz, J.: Ruminations on defining rational MPC. Talk given at SSoRC, Bertinoro, Italy (2008), http://www.daimi.au.dk/ jbn/SSoRC2008/program
[18] 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) · Zbl 1162.94378
[19] Kol, G., Naor, M.: Games for exchanging information. In: 40th Annual ACM Symposium on Theory of Computing (STOC), pp. 423–432. ACM Press, New York (2008) · Zbl 1231.94051
[20] Lepinski, M., Micali, S., Peikert, C., Shelat, A.: Completely fair SFE and coalition-safe cheap talk. In: 23rd ACM Symposium Annual on Principles of Dis- tributed Computing, pp. 1–10. ACM Press, New York (2004) · Zbl 1321.94072
[21] Lepinski, M., Micali, S., Shelat, A.: Collusion-free protocols. In: 37th Annual ACM Symposium on Theory of Computing (STOC), pp. 543–552. ACM Press, New York (2005) · Zbl 1192.94122
[22] Lepinski, M., Micali, S., Shelat, A.: Fair-zero knowledge. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 245–263. Springer, Heidelberg (2005) · Zbl 1079.94558
[23] Lysyanskaya, A.: Unique signatures and verifiable random functions from the DH-DDH separation. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 597–612. Springer, Heidelberg (2002) · Zbl 1028.94511
[24] 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) · Zbl 1161.94417
[25] Micali, S., Rabin, M.O., Vadhan, S.P.: Verifiable random functions. In: 40th Annual Symposium on Foundations of Computer Science (FOCS), pp. 120–130. IEEE, Los Alamitos (1999)
[26] Miclai, S., Shelat, A.: Truly rational secret sharing. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 54–71. Springer, Heidelberg (2009) · Zbl 1213.94159
[27] Ong, S.J., Parkes, D., 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) · Zbl 1213.94160
[28] Shamir, A.: How to share a secret. Communications of the ACM 22(11), 612–613 (1979) · Zbl 0414.94021
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.