Modeling Public Key Infrastructures in the Real World

  • John Marchesini
  • Sean Smith
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3545)


PKIs are complex distributed systems that are responsible for giving users enough information to make reasonable trust judgments about one another. Since the currencies of PKI are trust and certificates, users who make trust decisions (often called relying parties) must do so using only some initial trust beliefs about the PKI and some pile of certificates (and other assertions) they received from the PKI. Given a certificate, a relying party needs to conclude that the keyholder described by the certificate actually possesses the properties described by the certificate. In this paper, we present a calculus that allows relying parties to make such trust judgements. Our calculus extends Maurer’s deterministic model, and is focused on real world issues such as time, revocation, delegation, and heterogeneous certificate formats. We then demonstrate how our calculus can be used to reason about numerous situations that arise in practice.


Evaluation Time Trust Management Trust Management System Trust Transfer eXtensible Access Control Markup 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Blaze, M., Feigenbaum, J., Ioannidis, J., Keromytis, A.: The KeyNote Trust-Management System, version 2. IETF RFC 2704 (September 1999)Google Scholar
  2. 2.
    Blaze, M., Feigenbaum, J., Ioannidis, J., Keromytis, A.: The Role of Trust Management in Distributed Systems. In: Vitek, J. (ed.) Secure Internet Programming. LNCS, vol. 1603, pp. 185–210. Springer, Heidelberg (1999)CrossRefGoogle Scholar
  3. 3.
    Chadwick, D., Otenko, A., Ball, E.: Role-Based Access Control with X.509 Attribute Certificates. IEEE Internet Computing (March-April 2003)Google Scholar
  4. 4.
    Cooper, D.: A Model of Certificate Revocation. In: 15th Annual Computer Security Applications Conference (ACSAC 1999), Phoenix, Arizona, USA, December 1999, pp. 256–264. IEEE Computer Society, Los Alamitos (1999)CrossRefGoogle Scholar
  5. 5.
    Ellison, C.: The nature of a usable pki. Computer Networks, 823–830 (1999)Google Scholar
  6. 6.
    Ellison, C.: Improvements on Conventional PKI Wisdom. In: Proceedings of the 1st Annual PKI Research Workshop (April 2002)Google Scholar
  7. 7.
    Ellison, C., Frantz, B., Lampson, B., Rivest, R., Thomas, B., Ylonen, T.: SPKI Certificate Theory. IETF RFC 2693 (September 1999)Google Scholar
  8. 8.
    Farrell, S., Housley, R.: An Internet Attribute Certificate Profile for Authorization. IETF RFC 3281 (April 2002)Google Scholar
  9. 9.
    Goffee, N., Kim, S., Smith, S.W., Taylor, P., Zhao, M., Marchesini, J.: Greenpass: Decentralized, PKI-based Authorization for Wireless LANs. In: 3rd Annual PKI Research and Development Workshop. NIST (April 2004)Google Scholar
  10. 10.
    Housley, R., Polk, W., Ford, W., Solo, D.: Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile. IETF RFC 3280 (April 2002)Google Scholar
  11. 11.
    Howell, J., Kotz, D.: A formal semantics for SPKI. In: Cuppens, F., Deswarte, Y., Gollmann, D., Waidner, M. (eds.) ESORICS 2000. LNCS, vol. 1895, pp. 140–158. Springer, Heidelberg (2000)CrossRefGoogle Scholar
  12. 12.
    Kocher, P.: On Certificate Revocation and Validation. In: Hirschfeld, R. (ed.) FC 1998. LNCS, vol. 1465, pp. 172–177. Springer, Heidelberg (1998)CrossRefGoogle Scholar
  13. 13.
    Kohlas, R., Maurer, U.: Reasoning About Public-Key Certification: On Bindings Between Entities and Public Keys. Journal on Selected Areas in Communications, 551–560 (2000)Google Scholar
  14. 14.
    Li, N., Grosof, B., Feigenbaum, J.: Delegation logic: A logic-based approach to distributed authorization. ACM Transactions on Information and System Security (TISSEC) 6(1), 128–171 (2003)CrossRefGoogle Scholar
  15. 15.
    Li, N., Feigenbaum, J.: Nonmonotonicity, User Interfaces, and Risk Assessment in Certificate Revocation. In: Blaze, M. (ed.) FC 2002. LNCS, vol. 2357, pp. 166–177. Springer, Heidelberg (2003)Google Scholar
  16. 16.
    Li, N., Winsborough, W., Mitchell, J.: Beyond Proof-of-compliance: Safety and Availability Analysis in Trust Management. In: Proceedings of 2003 IEEE Symposium on Security and Privacy, pp. 123–139. IEEE Computer Society Press, Los Alamitos (2003)Google Scholar
  17. 17.
    Blaze, M., Feigenbaum, J., Lacy, J.: Decentralized trust management. In: Proceedings of the 1996 IEEE Symposium on Security and Privacy, pp. 164–173. IEEE Computer Society Press, Los Alamitos (1996)Google Scholar
  18. 18.
    Blaze, M., Feigenbaum, J., Strauss, M.J.: Compliance Checking in the PolicyMaker Trust Management System. In: Hirschfeld, R. (ed.) FC 1998. LNCS, vol. 1465, pp. 254–274. Springer, Heidelberg (1998)CrossRefGoogle Scholar
  19. 19.
    Malpani, A., Galperin, S., Mayers, M., Ankney, R., Adams, C.: X.509 Internet Public Key Infrastructure Online Certificate Status Protocol. RFC2560 (June 1999),
  20. 20.
    Maurer, U.: Modelling a Public-Key Infrastructure. In: Martella, G., Kurth, H., Montolivo, E., Bertino, E. (eds.) ESORICS 1996. LNCS, vol. 1146, Springer, Heidelberg (1996)Google Scholar
  21. 21.
    Naor, M., Nissim, K.: Certificate Revocation and Certificate Update. IEEE Journal on Selected Areas in Communications 18(4), 561–570 (2000)CrossRefGoogle Scholar
  22. 22.
    Novotny, J., Tueke, S., Welch, V.: An Online Credential Repository for the Grid: MyProxy. In: Proceedings of the Tenth International Symposium on High Performance Distributed Computing (HPDC-10), IEEE Press, Los Alamitos (2001)Google Scholar
  23. 23.
    Smith, S.W.: Outbound Authentication for Programmable Secure Coprocessors. International Journal on Information Security (2004)Google Scholar
  24. 24.
    Tuecke, S., Welch, V., Engert, D., Pearlman, L., Thompson, M.: Internet X.509 Public Key Infrastructure Proxy Certificate Profile (2003),
  25. 25.
    Weeks, S.: Understanding Trust Management Systems. In: Proceedings of 2001 IEEE Symposium on Security and Privacy, pp. 94–105. IEEE Computer Society Press, Los Alamitos (2001)Google Scholar
  26. 26.
    Welch, V., Foster, I., Kesselman, C., Mulmo, O., Pearlman, L., Tuecke, S., Gawor, J., Meder, S., Siebenlist, F.: X.509 Proxy Certificates for Dynamic Delegation. In: 3rd Annual PKI Research and Development Workshop (April 2004)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • John Marchesini
    • 1
  • Sean Smith
    • 1
  1. 1.BindView Corporation and Department of Computer ScienceDartmouth College 

Personalised recommendations