Usando Criptografia de Limiar para Tolerar Clientes Maliciosos em Memória Compartilhada Dinâmica

• Eduardo Adilio Pelinson Alchieri UnB
• Alysson Neves Bessani Universidade de Lisboa
• Joni da Silva Fraga UFSC

DOI: https://doi.org/10.5753/sbseg.2012.20545

Abstract

Byzantine quorum systems are an useful tool to implement consistent and available data storage systems in the presence of arbitrary faults. Several protocols were proposed to implement these systems in static environments and, more recent, proposals have also appeared for dynamic environments. One of the challenges to implement these systems in dynamic environments is the reconfiguration of the servers set due to joins and leaves. In this work we go one step further and propose protocols that tolerate malicious clients in dynamic Byzantine quorum systems, by using a threshold cryptography scheme that provides flexibility necessary to operate in these environments. This scheme is used to control actions that malicious clients can execute against the system. Moreover, all proposed protocols are for asynchronous systems.

References

Aguilera, M. (2004). A pleasant stroll through the land of infinitely many creatures. SIGACT News, 35(2):36–59.

Aguilera, M. K., Keidar, I., Malkhi, D., and Shraer, A. (2011). Dynamic atomic storage without consensus. JACM, 58:7:1–7:32.

Alchieri, E. A., Bessani, A. N., Silva Fraga, J., and Greve, F. (2012). Memória compartilhada em sistemas bizantinos dinâmicos. In Anais do XIII Workshop de Teste e Tolerância a Falhas-WTF 2012.

Alchieri, E. A. P., Bessani, A. N., Pereira, F., and da Silva Fraga, J. (2009). Sistemas de quóruns bizantinos pró-ativos. Revista Brasileira de Redes de Computadores e Sistemas Distribuídos, 2:21–34.

Bazzi, R. A. and Ding, Y. (2004). Non-skipping timestamps for Byzantine data storage systems. In Proc. of 18th Int. Symposium on Distributed Computing, DISC 2004, volume 3274 of LNCS, pages 405–419.

Bellare, M. and Rogaway, P. (1993). Random oracles are practical: A paradigm for designing efficient protocols. In Proc. of the 1st ACM Conference on Computer and Communications Security, pages 62–73.

Desmedt, Y. and Frankel, Y. (1990). Threshold criptosystems. In Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology CRYPTO’89, pages 307–315. Springer-Verlag.

Gifford, D. (1979). Weighted voting for replicated data. In Proc. of the 7th ACM Symposium on Operating Systems Principles, pages 150–162.

Lamport, L., Shostak, R., and Pease, M. (1982). The Byzantine generals problem. ACM Transactions on Programing Languages and Systems, 4(3):382–401.

Lamport, L. (1978). Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7):558–565.

Liskov, B. and Rodrigues, R. S. M. (2006). Tolerating byzantine faulty clients in a quorum system. In The 26th IEEE International Conference on Distributed Computing Systems ICDCS 2006.

Lynch, N. and Shvartsman, A. A. (2002). Rambo: A reconfigurable atomic memory service for dynamic networks.

In 16th International Symposium on Distributed Computing DISC, pages 173–190.

Malkhi, D. and Reiter, M. (1998). Byzantine quorum systems. Distributed Computing, 11(4):203–213.

Martin, J.-P. and Alvisi, L. (2004). A framework for dynamic Byzantine storage. In Proceedings of the International Conference on Dependable Systems and Networks. IEEE Computer Society.

Rivest, R. L., Shamir, A., and Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120–126.

Rodrigues, R. and Liskov, B. (2004). Rosebud: A scalable Byzantine-fault-tolerant storage architecture. MITLCS-TR 932, MIT Laboratory for Computer Science.

Shoup, V. (2000). Practical threshold signatures. In Advances in Cryptology: EUROCRYPT 2000, Lecture Notes in Computer Science, volume 1807, pages 207–222. Springer-Verlag.

Wong, T. M., Wang, C., and Wing, J. M. (2002). Verifiable secret redistribution for archive systems. In Proceedings of the 1th International IEEE Security in Storage Workshop.