nach oben

Journal of Cryptology

Erschienen in:

01.10.2016

Toward a Game Theoretic View of Secure Computation

verfasst von: Gilad Asharov, Ran Canetti, Carmit Hazay

Erschienen in: Journal of Cryptology | Ausgabe 4/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We demonstrate how Game Theoretic concepts and formalism can be used to capture cryptographic notions of security. In the restricted but indicative case of two-party protocols in the face of malicious fail-stop faults, we first show how the traditional notions of secrecy and correctness of protocols can be captured as properties of Nash equilibria in games for rational players. Next, we concentrate on fairness. Here we demonstrate a Game Theoretic notion and two different cryptographic notions that turn out to all be equivalent. In addition, we provide a simulation-based notion that implies the previous three. All four notions are weaker than existing cryptographic notions of fairness. In particular, we show that they can be met in some natural setting where existing notions of fairness are provably impossible to achieve.

Vorheriger Artikel Constant-Size Structure-Preserving Signatures: Generic Constructions and Simple Assumptions

Nächster Artikel Cryptanalysis of Full RIPEMD-128

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

An alternative and more general formalism might measure the runtime of a strategy as a function of the length of its inputs. However, the present formalism is considerably simpler.

At first glance, it might look as if the utilities from Definition 4.2 do not incentivize the parties to participate in the interaction to begin with. However, this concern can be dealt with by giving each party some fixed high payoff in case it participates.

I. Abraham, D. Dolev, R. Gonen, J.Y. Halpern, Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation, in PODC (2006), pp. 53–62

S. Agrawal, M. Prabhakaran, On fair exchange, fair coins and fair sampling, in CRYPTO’13 (2013), pp. 259–276

G. Asharov, Y. Lindell. Utility dependence in correct and fair rational secret sharing. J. Cryptol. 24(1), 157–202 (2011)

D. Beaver, S. Goldwasser, Multiparty computation with faulty majority, in 30th FOCS (1989), pp. 468–473

M. Blum. How to exchange (secret) keys. ACM Trans. Comput. Syst. 1(2), 175–193 (1983)

R. Cleve, Limits on the security of coin flips when half the processors are faulty, in 18th STOC (1986), pp. 364–369

R. Cleve, Controlled gradual disclosure schemes for random bits and their applications, in CRYPTO’89 (1989), pp. 573–588

Y. Dodis, S. Halevi, T. Rabin, A cryptographic solution to a game theoretic problem, in CRYPTO’00. LNCS, vol. 1880 (Springer, 2000), pp. 112–130

Y. Dodis, T. Rabin, Cryptography and game theory, in Algorithmic Game Theory, edited by N. Nisan, T. Roughgarden, E. Tardos, V.V. Vazirani (Cambridge University Press, Cambridge, 2007). http://www.cambridge.org/us/academic/subjects/computer-science/algorithmics-complexity-computeralgebra-and-computational-g/algorithmic-game-theory?format=HB

10.

G. Fuchsbauer, J. Katz, D. Naccache, Efficient rational secret sharing in standard communication networks, in 7th TCC. LNCS, vol. 5978 (Springer, 2010), pp. 419–436

11.

J.A. Garay, P.D. MacKenzie, M. Prabhakaran, K. Yang, Resource fairness and composability of cryptographic protocols, in 3rd Theory of Cryptography Conference TCC 2006. LNCS, vol. 3876 (Springer, 2006), pp. 404–428

12.

O. Goldreich, Foundations of Cryptography: Volume 2—Basic Applications. Cambridge University Press, Cambridge (2004)

13.

S. Goldwasser, L.A. Levin, Fair computation of general functions in presence of immoral majority, in CRYPTO 1990. LCNS, vol. 537 (Springer, 1991), pp. 77–93

14.

S. Goldwasser, S. Micali, Probabilistic encryption and how to play mental poker keeping secret all partial information. J. Comput. Syst. Sci. 28(2), 270–299 (1984)

15.

S. Goldwasser, S. Micali, C. Rachoff, The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186–208 (1989)

16.

S.D. Gordon, C. Hazay, J. Katz, Y. Lindell, Complete fairness in secure two-party computation. J. SIGACT News 43(1), 21–23 (2012)

17.

S.D. Gordon, J. Katz, Rational secret sharing, in Security and cryptography for networks (SCN). LNCS, vol. 4116 (Springer, 2006), pp. 229–241

18.

S.D. Gordon, J. Katz, Partial fairness in secure two-party computation. J. Cryptol. 25(1), 14–40 (2012)

19.

R. Gradwohl, N. Livne, A. Rosen, Sequential rationality in cryptographic protocols, in FOCS (2010), pp. 623–632

20.

A. Groce, J. Katz, Fair computation with rational players, in Eurocrypt (2012), pp. 81–98

21.

J. Halpern, V. Teague, Efficient rational secret sharing in standard communication networks, in 36th STOC (2004), pp. 623–632

22.

J. Halpern, R. Pass, Game theory with costly computation, in ICS (2010), pp. 120-142

23.

S. Izmalkov, M. Lepinski, S. Micali, Verifiably secure devices, in 5th TCC. LNCS, vol. 4948 (Springer, 2008), pp. 273–301

24.

S. Izmalkov, S. Micali, M. Lepinski, Rational secure computation and ideal mechanism design, in 46th FOCS (2005), pp. 585–595

25.

J. Katz, Bridging game theory and cryptography: recent results and future directions, in 5th TCC. LNCS, vol. 4948 (Springer, 2008), pp. 251–272

26.

G. Kol, M. Naor, Games for exchanging information, in 40th STOC (2008), pp. 423–432

27.

G. Kol, M. Naor, Cryptography and game theory: designing protocols for exchanging information, in 5th TCC. LNCS, vol. 4948 (Springer, 2008), pp. 320–339

28.

A. Lysyanskaya, N. Triandopoulos, Rationality and adversarial behavior in multi-party computation, in CRYPTO’06. LNCS, vol. 4117 (Springer, 2006), pp. 180–197

29.

S. Micali, Certified email with invisible post offices, 1997. Technical report; an invited presentation at the RSA 1997 conference

30.

S.J. Ong, D.C. Parkes, A. Rosen, S.P. Vadhan, Fairness with an honest minority and a rational majority, in 6th TCC. LNCS, vol. 5444 (Springer, 2009), pp. 36–53

31.

R. Pass, A. Shelat, Renegotiation-safe protocols, in Innovations in Computer Science (ICS, 2011)

Titel: Toward a Game Theoretic View of Secure Computation
verfasst von: Gilad Asharov
Ran Canetti
Carmit Hazay
Publikationsdatum: 01.10.2016
Verlag: Springer US
Erschienen in: Journal of Cryptology / Ausgabe 4/2016
Print ISSN: 0933-2790
Elektronische ISSN: 1432-1378
DOI: https://doi.org/10.1007/s00145-015-9212-6

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 4/2016

Constant-Size Structure-Preserving Signatures: Generic Constructions and Simple Assumptions

Bug Attacks

The -curve Construction for Endomorphism-Accelerated Elliptic Curves

New Second-Preimage Attacks on Hash Functions

Unconditionally Anonymous Ring and Mesh Signatures

Cryptanalysis of Full RIPEMD-128