Albert Levi
Abstract
Certification is a common mechanism for authentic public key distribution. In order to obtain a public key, verifiers need to extract a certificate path from a network of certificates, which is called public key infrastructure (PKI), and verify the certificates on this path recursively. This is classical methodology. Nested certification is a novel methodology for efficient certificate path verification. Basic idea is to issue special certificates (called nested certificates) for other certificates. Nested certificates can be used together with classical certificates in PKIs. Such a PKI, which is called nested certificate-based PKI (NPKI), is proposed in this paper as an alternative to classical PKI. The concept of "certificates for other certificates" results in nested certificate paths in which the first certificate is verified cryptographically while others are verified by just fast hash computations. Thus, we can employ efficiently verifiable nested certificate paths instead of classical certificate paths. NPKI is a dynamic system and involves several authorities in order to add a new user to the system. This uses the authorities' idle time to the benefit of the verifiers. We formulate the trade-off between the nested certification overhead and the time improvement on certificate path verification. This trade-off is numerically analyzed for a 4-level 20-ary balanced tree-shaped PKI and it has been shown that the extra cost of nested certification is in acceptable limits in order to generate quickly verifiable certificate paths for certain applications. Moreover, PKI-to-NPKI transition preserves the existing hierarchy and trust relationships in the PKI, so that it can be used for PKIs with fixed topology. Although there are many certificates in NPKI, certificate revocation is no more of a problem than with classical PKIs. NPKI even has an advantage on the number of certificate revocation controls: at most two certificate revocation controls are sufficient independent of the path length. Nested certificates can be easily adopted into X.509 standard certificate structure. Both verification efficiency and revocation advantage of NPKI and nested certificates make them suitable for hierarchical PKIs of wireless applications where wireless end users have limited processing power.
- Adams, C. and Farrell, S. 1999. Internet X.509 Public Key Infrastructure Certificate Management Protocols, RFC 2510.]] Google Scholar
- Adams, C. and S. Lloyd, S. 1999. Understanding Public Key Infrastructures. New Riders Publishing.]] Google Scholar
- Chadwick, D. W., Young, A. J., and Cicovic, N. K. 1997. Merging and extending the PGP and PEM trust models---The ICE-TEL trust model. IEEE Network 11, 3 (May/June), 16--24.]]Google Scholar
- Chokhani, S. 1994. Towards a national public key infrastructure. IEEE Communications Magazine 32, 9 (Sept.), 70--74.]]Google Scholar
- Eastlake, D. 1999. Domain Name System Security Extensions, RFC 2535.]] Google Scholar
- Ellison, C., Frantz, B., Lampson, B., Rivest, R., Thomas, B., and Ylonen, T. 1999. SPKI Certificate Theory, RFC 2693.]] Google Scholar
- Ford, W., Hallam-Baker, P., Fox, B., Dillaway, B., Lamacchia, B., Epstein, J., and Lapp, J. 2001. XML Key Management Specification (XKMS). Available at http://www.w3.org/TR/xkms/.]]Google Scholar
- Gassko, I., Gemmell, P. S., and Mackenzie, P. 2000. Efficient and fresh certification. In Proceedings of Public Key Cryptography (PKC) 2000 (Melbourne, Australia, January 2000). Lecture Notes in Computer Science, vol. 1751. Springer-Verlag, Berlin, 342--353.]] Google Scholar
- Housley, R., Polk, W., Ford, W., and Solo, D. 2002. Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile, RFC 3280.]] Google Scholar
- Itu-T. 1997. Recommendation X.509, ISO/IEC 9594--8. Information Technology---Open Systems Interconnection---The Directory: Authentication Framework, 3rd ed.]]Google Scholar
- Itu-T. 2000. Recommendation X.509, ISO/IEC 9594-8. Information Technology---Open Systems Interconnection---The Directory: Public-key and Attribute Certificate Frameworks, 4th ed.]]Google Scholar
- Itu-T. 2001a. Recommendation X.500, ISO/IEC 9594-1. Information Technology---Open Systems Interconnection---The Directory: Overview of Concepts, Models and Services.]]Google Scholar
- Itu-T. 2001b. Recommendation X.501, ISO/IEC 9594-2. Information Technology---Open System Interconnection---The Directory: Models.]]Google Scholar
- Kent, S. T. 1993. Internet privacy enhanced mail. Communications of the ACM 36, 8 (Aug.), 48--60.]] Google Scholar
- Kocher, P. 1998. On certificate revocation and validation. In Proceedings of Financial Cryptography 98 (Anguilla, BWI, Feb. 1998). Lecture Notes in Computer Science, vol. 1465. Springer-Verlag, Berlin, 172--177.]] Google Scholar
- Levi, A. 1999. Design and Performance Evaluation of the Nested Certification Scheme and its Applications in Public Key Infrastructures, Ph.D. Thesis, Department of Computer Engineering, Bogazici University.]]Google Scholar
- Levi, A. and Caglayan, M. U. 1998. NPKI: Nested certificate based public key infrastructure. In Advances in Computer and Information Sciences'98---Proceedings of the Thirteenth International Symposium on Computer and Information Sciences (ISCIS XIII) (Antalya, Turkey, Oct. 1998). Concurrent Systems Engineering Series, vol. 53. IOS Press, 397--404.]]Google Scholar
- Levi, A. and Caglayan, M. U. 1999a. Integrity control in nested certificates. In Proceedings of BAS'99, The Fourth Symposium on Computer Networks (Istanbul, Turkey, May 1999), 149--157.]]Google Scholar
- Levi, A. and Caglayan, M. U. 1999b. Verification of classical certificates via nested certificates and nested certificate paths. In Proceedings of ICCCN99---Eighth International Conference on Computer Communications and Networks (Boston, MA, Oct. 1999), 242---247.]]Google Scholar
- Levi, A. and Caglayan, M. U. 1999c. Analytical performance evaluation of nested certificates. Performance Evaluation 36--37, 213--232.]]Google Scholar
- Mastercard Inc. 1997. SET Secure Electronic Transaction Specification Book 1: Business Description.]]Google Scholar
- Menezes, A. 1993. Elliptic Curve Public Key Cryptosystems, Kluwer Academic Publishers. Boston, MA.]] Google Scholar
- Micali, S. 1996. Efficient Certificate Revocation, MIT Laboratory for Computer Science, Technical Memo 542b.]] Google Scholar
- Myers, M. 1998. Revocation: Options and challenges. In Proceedings of Financial Cryptography'98 (Anguilla, BWI, Feb. 1998). Lecture Notes in Computer Science, vol. 1465. Springer-Verlag, Berlin, 165--171.]] Google Scholar
- Myers, M., Ankney, R., Malpani, A., Galperin, S., and Adams, C. 1999. X.509 Internet Public Key Infrastructure On-line Certificate Status Protocol (OCSP), RFC 2560.]] Google Scholar
- Naor, M. and Nissim, K. 2000. Certificate revocation and certificate update. IEEE Journal on Selected Areas in Communications 18, 4 (Apr.), 561--570.]]Google Scholar
- National Institute of Standards and Technology (NIST). 1994. Digital Signature Standard (DSS). Federal Information Processing Standard (FIPS) PUB 186, U.S. Department of Commerce, Washington, DC.]]Google Scholar
- National Institute of Standards and Technology (NIST). 1995. Secure Hash Standard (SHS). Federal Information Processing Standard (FIPS) PUB 180-1, U.S. Department of Commerce, Washington, DC.]]Google Scholar
- Ramsdell, B. 1999. S/MIME Version 3 Certificate Handling, RFC 2632.]] Google Scholar
- Rivest, R. 1992. The MD5 Message Digest Algorithm, RFC 1321.]] Google Scholar
- Rivest, R. 1998. Can we eliminate certificate revocation lists? In Proceedings of Financial Cryptography'98 (Anguilla, BWI, Feb. 1998). Lecture Notes in Computer Science, vol. 1465. Springer-Verlag, Berlin, 178--183.]] Google Scholar
- Rivest, R. and Lampson, B. 1996. SDSI---A Simple Distributed Security Infrastructure. Available at http://theory.lcs.mit.edu/∼cis/sdsi.html.]]Google Scholar
- Rivest, R., Shamir, A., and Adleman, L. 1978. A method for obtaining digital signatures and public key cryptosystems. Communications of the ACM 21, 2 (Feb.), 120--126.]] Google Scholar
- Stallings, W. 2003. Cryptography and Network Security Principles and Practice, 3rd ed. Prentice-Hall, Englewood Cliffs, NJ (Chapter 15).]] Google Scholar
- United States Postal Service. 1998. Performance Criteria for Information-based Indicia and Security Architecture for IBI Postage Metering Systems. Available at http://www.usps.gov/ibip/documents/specs/pc0819.pdf.]]Google Scholar
- Wap Forum. 2001a. Wireless Application Protocol Architecture Specification, WAP-210-WAPArch-20010712. Available at http://www.openmobilealliance.org/tech/affiliates/wap/wapindex.html.]]Google Scholar
- Wap Forum. 2001b. Wireless Transport Layer Security Specification, WAP-261-WTLS-20010406-a. Available at http://www.openmobilealliance.org/tech/affiliates/wap/wapindex.html.]]Google Scholar
- Wap Forum. 2001c. Wireless Application Protocol Public Key Infrastructure Definition, WAP-217-WPKI-20010424-a. Available at http://www.openmobilealliance.org/tech/affiliates/wap/wapindex.html.]]Google Scholar
Index Terms
- Use of nested certificates for efficient, dynamic, and trust preserving public key infrastructure
Recommendations
An Efficient, Dynamic and Trust Preserving Public Key Infrastructure
SP '00: Proceedings of the 2000 IEEE Symposium on Security and PrivacyNested certification is a methodology for efficient certificate path verification. Nested certificates can be used together with classical certificates in the Public Key Infrastructures (PKIs). Such a PKI, which is called Nested certificate based PKI (...
Reducing certificate revocation cost using NPKI
Sec '01: Proceedings of the 16th international conference on Information security: Trusted information: the new decade challengeProblems with certificate revocation status control limit the deployment of Public Key Infrastructure (PKI). Classical certificate paths require revocation control of all certificates on the path. In this paper, we show how the recently proposed NPKI (...
RIKE: using revocable identities to support key escrow in PKIs
ACNS'12: Proceedings of the 10th international conference on Applied Cryptography and Network SecurityPublic key infrastructures (PKIs) are proposed to provide various security services. Some security services such as confidentiality, require key escrow in certain scenarios; while some others such as non-repudiation, prohibit key escrow. Moreover, these ...
Reviews
Adrian Constantin Atanasiu
Certification is a common mechanism for authentic public key distribution. In order to obtain a public key, verifiers usually need to extract a certificate path from a network of certificates (called public key infrastructure (PKI)), and verify the certificates on this path recursively. In this paper, the authors propose nested certification (NPKI), which is an improved methodology for efficient certificate path verification. The basic idea of NPKI is to issue special certificates (called nested certificates) for other certificates. NPKI is a dynamic system, and involves several authorities in order to add a new user to the system. NPKI can be seen as a system that provides an opportunity to manipulate the tradeoff between the load on the end users (verifiers), and the load on the servers (certification authorities (CAs)). NPKI enables systems to reduce the burden on end users, by increasing the load on the servers. Section 1 of the paper is an introduction, and, at the same time, a general presentation of the topic. An overview of nested certification and nested certificate paths is found in section 2. A nested certificate is defined as a certificate for another certificate. It certifies another certificate by assuring the legitimacy of the signature over it. A nested certificate must fulfill two requirements: first, certification that the subject certificate content has been signed by the claimed CA or nested certification authority (NCA), and second, certification that the subject certificate content has not been maliciously modified. In section 3, the construction of NPKI via transition from an existing PKI approach is detailed. The goal is to have quickly verifiable nested certificate paths. The main subsection is 3.2, where various characteristics of NPKI and the nested certificate propagation method are detailed. It is important to know that PKI-to-NPKI transition preserves the existing hierarchy and trust relationships in the PKI, so that it can be used for PKIs with fixed topology. Certificate revocation characteristics, rules, and advantages of nested certificates and NPKI are described in section 4. Although there are many certificates in NPKI, certificate revocation is easier than with classical PKIs. NPKI even has an advantage in the number of certificate revocation controls: at most, two certificate revocation controls are sufficient, independent of the path length. A performance evaluation of the proposed method is presented in section 5. The nested certification overhead is analyzed as well, and the tradeoff between this overhead and improvements in efficiency is interpreted. X.509 compatibility issues are discussed in section 6. Nested certificates can easily be adopted into the X.509 standard certificate structure. Both the verification efficiency and the revocation advantage of NPKI and nested certificates make them suitable for the hierarchical PKIs of wireless applications, where wireless end users have limited processing power. Nested certificates and other signed certificate validation mechanisms (online certificate status protocol (OCSP), Extensible Markup Language key management specification (XKMS), simple distributed security infrastructure (SDSI), and simple public key infrastructure (SPKI)) are briefly compared in section 7. The use of nested certificates in wireless application protocol (WAP) security is the subject of section 8. Section 9 presents conclusions. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments