nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Building Regular Registers with Rational Malicious Servers and Anonymous Clients

verfasst von : Antonella Del Pozzo, Silvia Bonomi, Riccardo Lazzeretti, Roberto Baldoni

Erschienen in: Cyber Security Cryptography and Machine Learning

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

The paper addresses the problem of emulating a regular register in a synchronous distributed system where clients invoking \(\mathsf{read}()\) and \(\mathsf{write}()\) operations are anonymous while server processes maintaining the state of the register may be compromised by rational adversaries (i.e., a server might behave as rational malicious Byzantine process). We first model our problem as a Bayesian game between a client and a rational malicious server where the equilibrium depends on the decisions of the malicious server (behave correctly and not be detected by clients vs returning a wrong register value to clients with the risk of being detected and then excluded by the computation). We prove such equilibrium exists and finally we design a protocol implementing the regular register that forces the rational malicious server to behave correctly.

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

Vorheriges Kapitel Supervised Detection of Infected Machines Using Anti-virus Induced Labels

Nächstes Kapitel On the Optimality of the Exponential Mechanism

Alive servers may be both honest or malicious.

Let us recall that we are in a synchronous system and the mutual exclusion problem can be easily solved also in presence of failures.

Notice that the client ability to detect a server misbehaviors depends on the specific protocol.

Let us note that if two servers have different values for \(G_s\) and \(D_s\), the analysis shown in the following is simply repeated for each server.

Let us recall that a Nash Equilibrium exists when each player selects a strategy and none of the players increases its utility by changing strategy.

More precisely, \({\mathcal {P}}\) works when \(D_s > cG_s\) where c is the estimated number of clients in the system.

Abraham, I., Dolev, D., Halpern, J. Y. Distributed protocols for leader election: a game-theoretic perspective. In: DISC 2013, pp. 61–75 (2003)

Afek, Y., Ginzberg, Y., Feibish, S.L., Sulamy, M.: Distributed computing building blocks for rational agents. In: PODC 2014, pp. 406–415 (2014)

Aiyer, A.S., Alvisi, L., Clement, A., Dahlin, M., Martin, J.P., Porth, C.: BAR fault tolerance for cooperative services. In: ACM SIGOPS Operating Systems Review. ACM, pp. 45–58 (2005)

Attiya, H., Bar-Noy, A., Dolev, D.: Sharing memory robustly in message-passing systems. J. ACM 42(1), 124–142 (1995)CrossRefMATH

Bazzi, R.A.: Synchronous Byzantine Quorum systems. Distrib. Comput. 13(1), 45–52 (2000)CrossRef

Chaudhuri, S., Kosa, M.J., Welch, J.: One-write algorithms for multivalued regular and atomic registers. Acta Informatica 37, 161–192 (2000)MathSciNetCrossRefMATH

Clement, A., Li, H.C., Napper, J., Martin, J., Alvisi, L., Dahlin, M.: BAR primer. In: DSN, M. (ed.), pp. 287–296 (2008)

Clement, A., Napper, J., Li, H., Martin, J.P., Alvisi, L., Dahlin, M.: Theory of BAR games. In: PODC 2007, pp. 358–359 (2007)

Del Pozzo, A., Bonomi, S., Lazzeretti, R., Baldoni, R.: Building regular registers with rational malicious servers and anonymous clients – extended version (2017). Available online on arXiv

10.

Delporte-Gallet, C., Fauconnier, H., Tran-The, H.: Uniform consensus with homonyms and omission failures. In: ICDCN 2013, pp. 61–175 (2013)

11.

Fudenberg, D., Tirole, J.: Game Theory. Massachusetts, Cambridge (1991)MATH

12.

Haldar, S., Vidyasankar, K.: Constructing 1-writer multireader multivalued atomic variables from regular variables. JACM 42(1), 186–203 (1995)CrossRefMATH

13.

Ieong, S., Shoham, Y.: Bayesian coalitional games. In: AAAI 2008, pp. 95–100 (2008)

14.

Li, H.C., Clement, A., Wong, E.L., Napper, J., Roy, I., Alvisi, L., Dahlin, M.: BAR gossip. In: OSDI 2006, pp. 191–204 (2006)

15.

Lamport, L.: On interprocess communication, part 1: models, part 2: algorirhms. Distrib. Comput. 1(2), 77–101 (1986)MathSciNetCrossRef

16.

Mahajan, P., Setty, S., Lee, S., Clement, A., Alvisi, L., Dahlin, M., Walfish, M.: Depot : cloud storage with minimal trust. ACM TOCS 29(4), 12 (2011)CrossRef

17.

Malkhi, D., Reiter, M.K.: Byzantine Quorum systems. Distrib. Comput. 11(4), 203–213 (1998)CrossRefMATH

18.

Martin J., Alvisi L., Dahlin M.: Small Byzantine Quorum systems. In: DSN 2002, pp. 374–388 (2002)

19.

Martin J., Alvisi L., Dahlin M.: Minimal Byzantine storage. In: DISC (2002)

20.

Schneider, F.B.: Implementing fault-tolerant services using the state machine approach: a tutorial. ACM Comput. Surv. 22(4), 299–319 (1990)CrossRef

21.

Singh, A.K., Anderson, J.H., Gouda, M.: The Elusive atomic register. JACM 41(2), 331–334 (1994)CrossRefMATH

22.

Sousa, P., Bessani, A.N., Correia, M., Neves, N.F., Verissimo, P.: Highly available intrusion-tolerant services with proactive-reactive recovery. IEEE TPDS 21(4), 452–465 (2010)

23.

The Tor project. https://www.torproject.org

24.

Vidyasankar, K.: Converting Lamport’s regular register to atomic register. IPL 28(6), 287–290 (1988)MathSciNetCrossRefMATH

25.

Vityani, P., Awerbuch, B.: Atomic shared register access by asynchronous hardware. In: FOCS 1987, pp. 223–243 (1987)

26.

Ostrovsky, R., Yung, M.: How to withstand mobile virus attacks. In: PODC 1991, pp. 51–59 (1991)

27.

Shamir, A.: How to share a secret. Comm. ACM 22(11), 612–613 (1979)MathSciNetCrossRefMATH

28.

Dolev, S., ElDefrawy, K., Lampkins, J., Ostrovsky, R., Yung, M.: Proactive secret sharing with a dishonest majority. In: SCN 2016, pp. 529–548 (2016)

29.

Cramer, R., Damgard, I.B.: Secure Multiparty Computation. Cambridge University Press, New York (2015)CrossRef

Titel: Building Regular Registers with Rational Malicious Servers and Anonymous Clients
verfasst von: Antonella Del Pozzo
Silvia Bonomi
Riccardo Lazzeretti
Roberto Baldoni
Verlag: Springer International Publishing
Buch: Cyber Security Cryptography and Machine Learning
Print ISBN: 978-3-319-60079-6

Electronic ISBN: 978-3-319-60080-2

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-60080-2_4

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"

Premium Partner