CS 754 IAI Seminar

Design and Implementation of Trusted Services 

Fall 2001

Coordinators:

Lidong Zhou (ldzhou@cs.cornell.edu)

4107A Upson Hall

 

Fred B. Schneider (fbs@cs.cornell.edu)

4115C Upson Hall

Time and Location:

Wednesdays, 3:35--4:25pm, 218 Olin Hall.

Course Description:

Distribution of trust, where the responsibility of a trusted service is  implemented by an aggregation of servers, is one way to enhance the trustworthiness of a service. The service is compromised only if sufficient many of its component servers are. However, even with such aggregation, trust may erode over time if an adversary could  gradually compromise one server after another.  Proactive recovery, which involves periodic restoration or replacement of possibly compromised servers, prevents such trust erosion over time. How to achieve distribution of trust and proactive recovery in a distributed system is the focus of the seminar. In particular, we focus on quorum systems, secret sharing, and threshold cryptography. Class meetings will be centered around student presentation of key papers in these areas.

Paper List:

Quorum Systems:

Presenter: Vicky Weissman

  1. D. H. Gifford. Weighted voting for replicated data. In Proceedings of the 7th ACM Symposium on Operating Systems Principles. Pages 150--159, Asilomar Conference Grounds, Pacific Grove, CA USA, December 10--12, 1979. ACM.

  2. R. H. Thomas. A majority consensus approach to concurrency control for multiple copy databases. ACM Transactions on Database Systems, 4(2):180--209, June 1979.

  3. H. Garcia-Molina and D. Barbara. How to assign votes in a distributed system. Journal of the ACM, 32(4):841--860, October 1985.
  4. D. Agrawal and A. El Abbadi. An efficient and fault-tolerant solution for distributed mutual exclusion. ACM Transactions on Computer Systems, 9(1):1-20, February 1991.
  5. M. Herlihy. A quorum-consensus replication method for abstract data types. ACM Transactions on Computer Systems, 4(1):32-53, February 1986.

Byzantine Quorum Systems:

Presenters: Walter Bell and Martin Guerrero

  1. D. Malkhi and M. Reiter. Byzantine quorum systems. Distributed Computing, 11(4):203--213, 1998.
  2. L. Alvisi, D. Malkhi, L. Pierce, M. Reiter, and R. Wright. Dynamic Byzantine quorum systems. In Proceedings of the International Conference on Dependable Systems and Networks, June 2000.
  3. G. Chokler, D. Malkhi, and M. Reiter. Backoff protocols for distributed mutual exclusion and ordering. ICDCS 2001.
  4. D. Malkhi and M. Reiter. An architecture for survivable coordination in large distributed systems. IEEE Transactions on Knowledge and Data Engineering, 12(2):187--202, April 2000.
  5. D. Malkhi, M. K. Reiter, D. Tulone and E. Ziskind. Persistent objects in the Fleet system. In Proceedings of the 2nd DARPA Information Survivability Conference and Exposition (DISCEX II), June 2001.

Secret Sharing:

Presenters: Ke Wang and Sunny Gleason

  1. A. Shamir. How to share a secret. Communications of the ACM, 22(11):612--613, November 1979.
  2. M. P. Herlihy and J. D. Tygar. How to make replicated data secure. In C.Pomerance, editor, Advances in Cryptology---Crypto'87, A Conference on the Theory and Applications of Cryptographic Techniques, Santa Barbara, California, USA, August 16--20, 1987. Proceedings, volume 293 of Lecture Notes in Computer Science, pages 120--127. Springer, 1988.
  3. Michael O. Rabin. Efficient dispersal of information for security, load balancing, and fault tolerance. Journal of the ACM, 36(2):335-348, April 1989.
  4. Hugo Krawczyk. Secret Sharing Made Short. In Douglas R. Stinson, editor, Advances in Cryptology---Crypto'93, 13th Annual International Cryptology Conference, Santa Barbara, California, USA, August 22-26, 1993. Proceedings, pages 136--146, volume 773 of Lecture Notes in Computer Science. Springer, 1994.
  5. M. Ito, A. Saito, and T. Nishizeki. Secret sharing scheme realizing general access structure. In  Proceedings of the IEEE Global Communication Conference (GLOBALCOM'87): 99--102, Tokyo, Japan, November 1987.
  6. Josh Cohen Benaloh.  Secret Sharing Homomorphisms: Keeping Shares of A Secret Sharing. In Andrew M. Odlyzko, editor, Advances in Cryptology--CRYPTO '86, Santa Barbara, California, USA, 1986. Proceedings, pages 251--260, volume 263 of Lecture Notes in Computer Science. Springer, 1987.
  7. Josh Cohen Benaloh and Jerry Leichter. Generalized Secret Sharing and Monotone Functions. In Shafi Goldwasser, editor, Advances in Cryptology--CRYPTO '88, Santa Barbara, California, USA, 1988. Proceedings, pages 27--35, volume 403 of Lecture Notes in Computer Science. Springer, 1990.

Secure Multiparty Computation:

Presenter: Mike Marsh

  1. D. Chaum, C. Crepeau, and I. Damgard. Multi-party unconditionally secure protocols. In Proc. 20th ACM Symp. on Theory of Computing, pages 11--19, Chicago, 1988. ACM.
  2. M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In Proc. 20th Ann. ACM Symp. on Theory of Computing, pages 1--10, 1988.
  3. A.C. Yao. Protocols for secure computations, Proc. of FOCS 82, pp. 160-164. IEEE

Threshold Cryptography:

Presenters: Lantian Zheng and Nate Nystrom

  1. Y. Desmedt and Y. Frankel. Threshold cryptosystems. In G. Brassard, editor, Advances in Cryptology---Crypto'89, the 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20--24, 1989, Proceedings, volume 435 of Lecture Notes in Computer Science, pages 307--315. Springer, 1990.
  2. Y. Frankel and Y. Desmedt. Parallel reliable threshold multisignature. Tech. Report TR-92-04-02, Dept. of EE & CS, Univ. of Wisconsin-Milwaukee, April 1992.
  3. Y. Desmedt. Some recent research aspect of threshold cryptography. In Eiji Okamoto, George Davida, and Masahiro Mambo, editors, Information Security, The 1st International Workshop, ISW'97, Tatsunokuchi, Ishikawa Japan, September 17--19, 1997, Proceedings, volume 1396 of Lecture Notes in Computer Science, pages 158--173. Springer February 1998.
  4. T. Rabin. A simplified approach to threshold and proactive RSA. In H. Krawczyk, editor, Advances in Cryptology---Crypto'98, the18th Annual International Cryptology Conference, Santa Barbara, CA USA, August 23--27, 1998, volume 1462 of Lecture Notes in Computer
    Science    , pages 89--104. Springer, 1998.

Verifiable Secret Sharing and Proactive Secret Sharing:

Presenters: Stephan Zdancewic and Sunny Gleason

  1. P. Feldman. A practical scheme for non-interactive verifiable secret sharing. Proceedings of the 28th Annual Symposium on the Foundations of Computer Science:427--437. IEEE, October 12--14, 1987.
  2. T. Pedersen. Non-interactive and information-theoretic secure verifiable secret sharing. In J. Feigenbaum, editor, Advances in Cryptology---Crypto'91, the 11th Annual International Cryptology Conference, Santa Barbara, CA USA, August 11--15, 1991, Proceedings, volume 576 of Lecture Notes in Computer Science, pages 129--140. Springer, 1992.
  3. S. Jarecki. Proactive secret sharing and public key cryptosystems. Master's thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA USA, September 1995.
  4. A. Herzberg, S. Jarecki, H. Krawczyk, and M. Yung. Proactive secret sharing or: How to cope with perpetual leakage. In D. Coppersmith, editor, Advances in Cryptology---Crypto'95, the 15th Annual International Cryptology Conference, Santa Barbara, CA USA, August 27--31, 1995, Proceedings, volume 963 of Lecture Notes in Computer Science, pages 457--469. Springer, 1995.
  5. R. Canetti, R. Gennaro, A. Herzberg, and D. Naor. Proactive security: Long-term protection against break-ins. CryptoBytes (The technical newsletter of RSA Laboratories, a division of RSA Data Security Inc.), 3(1):1--8, Spring 1997.

Systems:

  1. Miguel Castro and Barbara Liskov. Practical Byzantine Fault Tolerance. In Proceedings of the Third Symposium on Operating Systems Design and Implementation (OSDI '99), New Orleans, USA, February 1999.
  2. Miguel Castro and Barbara Liskov. Proactive Recovery in a Byzantine-Fault-Tolerant System. In Proceedings of the Fourth Symposium on Operating Systems Design and Implementation (OSDI '00), San Diego, USA, October 2000.

Last Updated on October 23, 2001. Please send you comments to Lidong Zhou.