Distributed credential chain discovery in trust management: extended abstract

ABSTRACT

We give goal-oriented algorithms for discovering credential chains in RTo, a role-based trust-management language introduced in this paper. The algorithms search credential graphs, a representation of RTo credentials. We prove that evaluation based on reachability in credential graphs is sound and complete with respect to the set-theoretic semantics of RTo . RTo is more expressive than SDSI 2.0, so our algorithms can perform chain discovery in SDSI 2.0, for which existing algorithms in the literature either are not goal-oriented or require using specialized logic-programming inferencing engines. Being goal-oriented enables our algorithms to be used when credential storage is distributed. We introduce a type system for credential storage that guarantees well-typed, distributed credential chains can be discovered.

REFERENCES

• 1: Tuomas Aura, Fast Access Control Decisions from Delegation Certificate Databases, Proceedings of the Third Australasian Conference on Information Security and Privacy, p.284-295, July 01, 1998
• 2: Matt Blaze,Joan Feigenbaum,John Ioannidis,and Angelos D.Keromytis.The KeyNote Trust-Management System,Version 2.IETF RFC 2704,September 1999.
• 3: Matt Blaze , Joan Feigenbaum , Jack Lacy, Decentralized Trust Management, Proceedings of the 1996 IEEE Symposium on Security and Privacy, p.164, May 06-08, 1996
• 4: Matt Blaze , Joan Feigenbaum , Martin Strauss, Compliance Checking in the PolicyMaker Trust Management System, Proceedings of the Second International Conference on Financial Cryptography, p.254-274, February 23-25, 1998
• 5: Sharon Boeyen,Tim Howes,and Patrick Richard. Internet X.509 Public Key Infrastructure LDAPc2 Schema.IETF RFC 2587,June 1999.
• 6: Piero Bonatti , Pierangela Samarati, Regulating service access and information release on the Web, Proceedings of the 7th ACM conference on Computer and communications security, p.134-143, November 01-04, 2000, Athens, Greece [doi>10.1145/352600.352620]
• 7: Tim Bray,Dave Hollander,and Andrew Layman. Namespaces in XML.W3C Recommendation,January 1999.http://www.w3.org/TR/REC-xml-names/.
• 8: Dwaine Clarke , Jean-Emile Elien , Carl Ellison , Matt Fredette , Alexander Morcos , Ronald L. Rivest, Certificate chain discovery in SPKI?SDSI, Journal of Computer Security, v.9 n.4, p.285-322, January 2001
• 9: Yassir Elley,Anne Anderson,Steve Hanna,Sean Mullan,Radia Perlman,and Seth Proctor.Building Certificate Paths:Forward vs.Reverse.In Proceedings of the 2001 Network and Distributed System Security Symposium (NDSS '01),pages 153 -160.Internet Society,2001.
• 10: Carl Ellison,Bill Frantz,Butler Lampson,Ron Rivest, Brian Thomas,and Tatu Ylonen.SPKI Certificate Theory.IETF RFC 2693,September 1999.
• 11: Carl Ellison,Bill Frantz,Butler Lampson,Ron Rivest, Brian Thomas,and Tatu Ylonen.Simple Public Key Certificates.Internet Draft (Work in Progress),July 1999.http://world.std.com/~cme/spki.txt.
• 12: Carl A. Gunter , Trevor Jim, Policy-directed certificate retrieval, Software—Practice & Experience, v.30 n.15, p.1609-1640, Dec. 2000 [doi>10.1002/1097-024X(200012)30:15<1609::AID-SPE334>3.0.CO;2-5]
• 13: Trevor Jim, SD3: A Trust Management System with Certified Evaluation, Proceedings of the 2001 IEEE Symposium on Security and Privacy, p.106, May 14-16, 2001
• 14: Ninghui Li, Local Names in SPKI/SDSI, Proceedings of the 13th IEEE Computer Security Foundations Workshop (CSFW'00), p.2, July 03-05, 2000
• 15: Ninghui Li , Benjamin Grosof , Joan Feigenbaum, A Practically Implementable and Tractable Delegation Logic, Proceedings of the 2000 IEEE Symposium on Security and Privacy, p.27, May 14-17, 2000
• 16: Ravi S. Sandhu , Edward J. Coyne , Hal L. Feinstein , Charles E. Youman, Role-Based Access Control Models, Computer, v.29 n.2, p.38-47, February 1996 [doi>10.1109/2.485845]
• 17: David S.Warren and et al .The XSB Programming System (Version 2.2),April 2000. http://www.cs.sunysb.edu/~sbprolog/xsb-page.html.
• 18: William H.Winsborough,Kent E.Seamons,and Vicki E.Jones.Automated Trust Negotiation.In DARPA Information Survivability Conference and Exposition .IEEE Press,January 2000.
• 19: Ting Yu , Marianne Winslett , Kent E. Seamons, Interoperable strategies in automated trust negotiation, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.502004]

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce
          Subjects: Security

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Inference engines

General Terms:
Algorithms, Performance, Security