Top

Journal of Cryptology

Published in:

01-10-2016

Toward a Game Theoretic View of Secure Computation

Authors: Gilad Asharov, Ran Canetti, Carmit Hazay

Published in: Journal of Cryptology | Issue 4/2016

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

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

next article Cryptanalysis of Full RIPEMD-128

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

Available only for authorised users

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)

Title: Toward a Game Theoretic View of Secure Computation
Authors: Gilad Asharov
Ran Canetti
Carmit Hazay
Publication date: 01-10-2016
Publisher: Springer US
Published in: Journal of Cryptology / Issue 4/2016
Print ISSN: 0933-2790
Electronic ISSN: 1432-1378
DOI: https://doi.org/10.1007/s00145-015-9212-6

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 4/2016

Cryptanalysis of Full RIPEMD-128

The -curve Construction for Endomorphism-Accelerated Elliptic Curves

Bug Attacks

Unconditionally Anonymous Ring and Mesh Signatures

Key Recovery Attacks on Iterated Even–Mansour Encryption Schemes

New Second-Preimage Attacks on Hash Functions

Premium Partner