Doing business on the Internet poses new service relationships among parties. The infrastructure of doing business is changing: the conventional service-relationship among parties and the usual verification of legitimate business parties are changing. Among all parties on the Internet, the trust relationship is under threat from spoofing, eavesdropping, modification, masquerading and insecure transmission. The key to the trust relationship among business parties (or entities) is to be able to verify the true identity of each other. Authenticity is an important factor of trust on the Internet.

Trust has been a focus among professionals and their Internet communities. Governments and individuals (policy makers, cryptographers, economists and users) have pooled their resources to define and develop a safe environment on the Internet. Public Key Infrastructure (PKI) provides an authentication framework, ie. a way of authenticating parties to establish a trust relationship. It also includes managing public keys and registrations using digitally signed certificates. Digital signature certificates are becoming increasingly important technical mechanism for trust management on the Internet.

About 100 companies and organisations in the world (including Australia's government public key authority [3]) provide certification services and certification products based on various trust models. These different Public Key Infrastructure (PKI) trust models include the X.509 standard PKI trust model, Pretty Good Privacy (PGP), Simple Distributed Secure Infrastructure (SDSI) and Simple Public Key Infrastructure (SPKI).

The term certificate was proposed for the first time in 1978 by Loren M. Kohnfelder in his bachelor thesis at MIT [1]. Since then, the certificate has been used as a binding between a name and a public key. The binding is done by a digital signature after certifying the user's public key. This certificate must be signed by a certificate authority (CA) or a person in whom the certificate user has some degree of trust. The CA and the person are also known as the "trusted third party" (TTP). The certificate user verifies certificates by verifying TTP digital signatures (which can only have been created using the TTP's private key). If the signatures are "good", the certificate user has confidence that the public key of the entity in the certificate belongs to the entity who claims it, with the degree of confidence depends on how greatly the CA is trusted to have verified this relationship.

A certificate contains various bits of information:

There are different types of certificate, such as identity certificate, credential certificates and attribute certificate (ANSI draft standard X.9.45) [8]. A variety of applications [17] use certificates to protect personal email (eg. Personal ID), transacting gateways, web sites, securing connection (eg. server ID) and authenticity of publications on the Internet (eg. Developers ID). There are also different classes of certificates providing different assurance levels. Some examples of different certificates include personal certificates, server (or site) certificates and developer certificates [16].

 In general, the certificate provides a statement by a trusted third party (eg. Issuer Authority or Certificate Authority or a person) that the signed key is authentic and truly belongs to the subject (ie. person, organisation, site, server) who claims it.

 For example, if Alice wants to send a message to Bob using Communicator's messenger:

1) Alice subscribes a membership (class1) for a certificate from a CA by filling in a form including her email;

2) A key pair is generated as part of process of subscribing to the certificate (the private key can be protected by a password);

3) The CA verifies Alice's ID (ie. email) by sending a PIN using her email address;

4) After Alice receives the email with the PIN, she retrieves her certificate from the CA using the PIN. The certificate now is residing in Alice's Communicator and messanger applications and is ready for use;

 Meantime, Bob perfoms a similar process to get his certificate.

5) Alice signs her message with her certificate and sends it to Bob;

6) After Bob receives Alice's signed message, he can reply to her with a signed message with his certificate;

7) After exchange certificates, Bob and Alice can send signed and encrypted (S/MIME) emails to each other.

Alice and Bob have full confidence that their email is truly coming from the expected source. Their confidence has been vouched by the CA, where their certificates have been signed by.

From the above example, Alice and Bob subscribed their certificates from the same CA. What if they were using different CAs ? How would they verify each other's certificates?

Different trust models have demonstrated both conceptual and implementation commonalities and differences in the areas of authentication framework structure, transitivity of trust, certificate revocation lists (CRL), and certificate policy (including certificate practice statement). Different trust models have a different focus on the trust relationship, carry different information in a certificate, and provide different levels of trust. Their organisational and technical implementation also varies.

The following table summarises a number of differences in trust management among different trust models:

Cryptography provides secure communications over the Internet without prior exchange of encryption/decryption keys. Public key cryptography has been recommended for use with the ISO authentication framework. This framework, also known as the X.509 protocol, provides for authentication across networks.

The most important part of X.509 is its structure for public-key certificates, which is an identity-based certificate. The user's public key is bound with the user's distinguished name (ie. global unique name space). This certificate must be signed and issued to a particular entity by a certificate authority (CA or Issuing Authority) under provision of its certificate policies and Certificate Practice Statement (CPS).

In X.509 version 1 and 2, the X.509 PKI model was primarily a hierarchical structure. The X.509 version3 introduced some extensions allowing the management of policies and trust relationships in a web or networked structure [9]. An X.509 trust model has formal and complex organisational structure. It usually consists of the policy approving authority (PAA), the policy certificate authority (PCA), the certificate authority (CA), the organisational registration authorities (ORA) and the trusted third party (TTP).

A PKI functional structure consists of certificate issuance, certification archiving, certificate revocation and policy approval. A number of security servers and agents, which include the certified delivery server, the digital notary server, ticket granting agent and TTP. They perform tasks such as confidentiality key exchange, key pair generation, key management, digital signature verification, digital signature generation to provide authentication, integrity and non-repudiation [10].

The trust in the X.509 compliant PKI hierarchical-trusted model is transferred along a set of certificates that provides a chain of trust. The chain of certificates can be of arbitrary length [5]. To establish a trust between two entities, the verifier carries out the process of verifying the signatures on a chain of certificates until reaching the certificate which the verifier trusts.

A list of certificates needed to allow a particular user to obtain the public key of another, is known as a "certification path". Each CA has a list of certificates. Some of the certificates are named as "forward certificates" which are issued by other CAs (eg. a superior CA in the hierarchy). Some of the certificates are named as "reverse certificates" which are issued by the CA itself. This list of certificates enable two users to mutually authenticate by constructing a certification path which forms an unbroken chain of trusted nodes in a hierarchy structure.

(Figure 2 [5])

"A<X>,X<W>" means W signed the certificate of X, and X signed the certificate of A, where W, X, A are certificate authorities. It is important to know that the level of trust provided by certificates "A<X>,X<W>" is the same as "A<X>". In other words, possession of "A<X>,X<W>" provides the same capability as "A<W>" (ie. A<X>,X<W> =A<W>), namely the ability to find out the public key of W (ie. a CA) given the public key of A (ie. a CA).

The certification path (chains of certificates) can be constructed either in a hierarchical or a network way.

In a hierarchical certification path, a "root" CA issues certificates to its subordinate CAs and these CAs issues certificates to their subordinate CAs and so on. The "root" CA is regarded as the most trustworthy CA in the hierarchical certification path and every user must know the root CA's public key. Any user's certificate may be verified by following the certification path till the verifier reaches to the root CA (eg. a common trusted CA or the CA who issued the user's certificate).

The X.509 compliant PKI hierarchical-trust model has some advantages and disadvantages.

In a network certification path, CAs use CrossCertificates to cross-certify each other. In other words, each CA issues the other a certificate and combines the two certificates in its directory.

(Figure 3)

The CrossCertificate supports chains of trust in both directions (unlike a hierarchical certification path which is unidirectional). To verify the other users' certificates, the user verifies a certification path of certificates that leads back to its own trusted CA, where the user knows its own CA's public key.

Back to the early question: "If Alice and Bob subscribed their certificates from different CAs, how do they verify each other's certificates?":

1) According to the X.509 PKI trust model, Alice (where A is) only needs to obtain X<Z>, Z<B> to form the certification path, and Z<X> to form the return certification path. Bob (where B is) only needs to obtain Z<X>, X<A> to form the certification path, and X<Z> to form the return certification path (refer Figure 2).

2) If A is Alice and C is Bob, both know X's public key, so Alice (where A is) directly acquires the certificate of Bob (where C is). Alice only needs X<C> to form the certification path and X<A> to form the return certification path. Bob (where C is) directly acquires the certificate of Alice (where A is) and obtains X<A> to form the certification path and X<C> to form the return certification path.

A CRL(certificate revocation list) is a list of revoked certificates and must be signed by a valid CA. When a private key is compromised, or the person who holds the certificate leaves the issuing organisation, it is time to revoke his/her certificate. A CRL has records of the time when the CRL was issued, the time the next CRL will be issued, and serial numbers of revoked certificates which are unique for the CRL issuer. So CA verifiers periodically retrieve CRLs from repositories. Users can check CRLs against a certificate for its validity. In X.509 version3, some extensions have been proposed to improve the effectiveness of CRLs (eg. time to live)[5].

In summary, the X.509 (early versions and version3) compliant trust model has wide acceptance from industries and many products are currently on the market [19]. Compared to other trust models, it has a well documented PKI both in organisational and functional aspects, which is important for inter-operability among certification products; although some may argue that the model is trying to formalise too many things.

Pretty Good Privacy (PGP) use the web of trust model. The web of trust model, permits each user to certify a binding between the particular public key and the particular user-ID. The user-ID in PGP consists of a name and email address. The email address provides a global name space, which is similar to a Distinguished Name in X.509.

The PGP's key certificates contains : the public key; one or more user IDs for the key's creator; the date that the key was created; and the list of digital signatures on the key (optionally provided by people who attest to the key's veracity) [13].

In PGP, the trust is transferred through each person's own belief of whether the other person is trustworthy or not.

In PGP, a web of trust is constructed by establishing a list of validated public keys on its keyring. Each key certificate on a PGP public key ring has validity and trust parameters. The validity is an indication of whether you believe the key belongs to the person (eg. complete). The trust is a measure of how much you believe the person who created the key (eg. marginal, complete). If you trust the person more, then you may trust him/her to certify other people's keys (refer to the table1).

Example, if Alice knows Carl via Bob's signature, then how much trust Alice can place on Carl?

Alice can make her own decisions about the level trust on Carl at the time in the range of "undefined, untrusted, marginal and complete" depending on the trust in Bob at the time.

In PGP, there is no central repository of certification revocation lists (CRL). Every PGP user can revoke its own public key and others' public keys, which is unlike the X.509 compliant PKI's revocation mechanism. When a person wants to notify others that his/her public key has been compromised, the key's owner can issue a key revocation certificate (PGP -kd myself) and extract it from the public key ring and send to his/her correspondents.

This autonomy notification process of CRL may not be suitable in a larger circuit and domain given time delays in propagating. However it may work very well in a small circuit. When a user is suspicious of someone's public key, the user can disable it on his/her own public key ring (PGP -kd someone) at any time. The PGP allows users to change the level of trust to a public key at their own finger tip.

In summary, PGP may not be as convenient as a centralised registry of public keys, such as the X.509 PKI trust model. However the key verification process can be distributed among peers. This web trust structure allows multiple signatures to vote a binding into validity, which may be more difficult to subvert [7], thus it provides some degree of trust.

In 1996, Ronald L. Rivest and Butler Lampson proposed the Simple Distributed Security Infrastructure (SDSI) [12]. Later, the Simple Public-Key Infrastructure (SPKI) (refer section 6) work group joined force with the SDSI group forming a joint effort to simplify the "excessively complex" X.509-based global certificate hierarchies. SDSI defines a certificate structure and operating procedures for trust management. It supports both web and hierarchical trust models. It believes that simple and clear data structures can enhance the security requirements of a system. Its focus is on how to define a flexible data structure to perform trust management tasks in a flexible way. It claims that SDSI data structure makes it easier to define and implement access control list (ACL) and security policies, which is an authorisation function of security services.

In SDSI, there are three type of certificates: membership certificates, identity certificates and name/value certificates. Certificates are defined as signed objects (eg. a principal, a group, a quote). It gives flexibility to allow the user to define any objects in its data structure, eg. "Signed messages are a special case of certificates" [12]. Identity-based certificates bind the public key and the individual (ie. person, principal). Group-membership certificates assert that a principal or principals are a member of its group. Name/value certificates use a local name (or a symbol), which is free-form text information about the person.

SDSI introduced concepts of objects, such as principal, groups (ie. a set of principals forms a group, a group can be within a group), group-membership certificates, local name spaces. A notion of a group is used to specify authorisation by its principals. Each group has a name and a set of members. The name is local to the principal, who is the owner of the group.

 Principals have various "special status" which give them different authorities to perform certain tasks. Each principal can sign statements and requests on the same basis as any other principal. Each principal (ie. a public key, a digital signature verification key) is a "certification authority". S/He can issue and sign a certificate based on his/her own judgement or policies. The principal can also be the "value" of some name and can create its own local names (eg. nicknames, email addresses, account numbers, or any information) with which he/she can refer to other principals. The owner (ie. the principal) can change the group definition. The definition explicitly lists the group's members, or defines the group in terms of other groups. Groups can be defined within a group (ie. nested expressions). A group has no a public key associated with. A member of the group (eg. a principal) can use its membership certificate to make a request for his/her (or its) group.

SDSI is a web of trust (egalitarian). The trust in SDSI can be passed using principals as the "delegate authority". Delegate authority uses groups and a delegation certificate. A delegation certificate gives the delegatee the authority to sign certain types statements on behalf of the delegator. It can also be used to authorise a group. A group with "delegation certificate" will be able to sign on behalf of the signing principal. The delegation certificates may be used as credentials by the group to show that their signatures are authorised by the principal. Several signers can co-sign SDSI objects (similar to PGP key signatures).

SDSI does not have certificate revocation lists (CRLs). Instead, the "reconfirmation required" on signatures is used. Reconfirmation of the specified signature must be done by either the original signer (eg. principal), or by the reconfirmation principal. The requirement of periodic reconfirmation may also be stated on the certificate. The signer (eg. principal) can specify the reconfirmation period (eg. hourly or yearly) for a signature. Signatures contain a set of relevant certificates and have expiration dates.

In 1996, the Simple Public-Key Infrastructure Work Groups set up clear objectives for more flexible certificate structure and operating procedures for trust management, which has similar objectives with the SDSI group. The SPKI Work Group stated: " the main purpose of an SPKI certificate is to authorise some action, give permission, grant a capability, etc". In other words, it tries to define credential-based certificates rather then identity-based certificates, like certificates in the X.509 PKI trust model. SPKI work now combines with SDSI data structures aiming to support a range of trust models.

Although the SPKI is in the state of "work in progress", its objectives have been clearly stated in the form of an Internet Draft [1]. Certificates used in SPKI should bind a meaningful attribute to a public key, eg. an SPKI certificate must be able to bind a key to a local name (ie. a person's nickname). The attribute does not have to be a recognisable name. In other words, all certificates should be anonymous wherever possible. An SPKI certificate should be designed to discourage keyholders from sharing their private keys, and a certificate holder should be able to delegate permissions s/he acquires through the certificate (SDSI data structure). An SPKI certificate should be simple and useable in very constrained environments (eg. smartcards). An SPKI certificate should have a validity period, and support both positive and negative on-line validations via CRL.

SPKI is intended to be a web-trusted model. It believes that people must be allowed to choose whom they should trust and reliable. It may also support hierarchical-trust model as stated in their objectives. Combining with SDSI model, the transitivity of trust may also use "delegate certificates" and "groups" concepts.

In SPKI, a periodic revalidation will be required for certificates and public keys. The information of CRLs and Key Revocation Lists (KRL) can be generated periodically and broadcast or made available on request and given a limited Time-to-Live (TTL). Each certificate of SPKI has activity dates and conditions which indicate the certificate must be tested on-line or through other signed instruments. And any revalidation instrument of CRL and KRL must also have their own lifetime.

The ability to establish a trust relationship on the Internet will determine the rate of growth of Electronic Commerce. The digital signature certificate can be seen as a critical factor in trust management+ , which can provide scalable trust on the Internet. Trust management provides the infrastructure to achieve certain levels of confidence of trust* in a relationship(s). Scalable trust allows a constant level of trust to travel to a large number of nodes (or entities) and still be able to maintain its level of trust during its transitivity in a specific time frame. Different trust models focus on different aspects of trust relationship, such as parties, scales of trust relationships and trust infrastructures. They all have their place in the market of electronic commerce. The following table shows the various strengths and limitations of different trust models.

(Table 2)

As the development of trust management in different trust models is continuing to progress, it is very difficult to predict which trust models will merge and what new trust models will be proposed. However, one thing that is certain is that there is a need for PKI trust models and certification services to protect the authenticity of legitimate businesses and intellectual property.

Trust is a critical component in making business decisions on the Internet. A simple trust concept involves cryptographers, economists, policy makers and markets participating in the development of a trust relationship on the Internet. Different trust models take different approaches to establishing a trust relationship among business parties. The different models provide different structure of trust relationship, ie. hierarchical or web trust relationship. To choose the right tool for the right job is to know your own or your organisation's needs, and the different capabilities and strengths of the various trust models.

A CA also has different classes of certificates to provide different levels of trust. There is no 100 per cent guarantee in a trust relationship, so there is a need to examine a CA's Certification Practice Statement carefully, which requires a certain knowledge of CA's policies and X.509 Public Key Infrastructure. These will require resources to educate your own users and staff and should be seen as a future investment for a company.

[1] Carl M. Ellison, "SPKI Requirements" Internet - Draft, 11 March 1998, ftp://ftp.ietf.org/internet-draft/draft-ietf-spki-cert-req-01.txt (Current version 18 July 1998).

[2] Certification Authorities, http://www.qmw.ac.uk/~tl6345/ca.htm (Current version May 12 1998).

[3] Government Public Key Authority, at http://www.gpka.gov.au (Current version July 25 1998).

[4] Ian Taylar MBE MP, Minister for Science & Technology. "Licensing of Trusted Third Parties for the Provision of Encryption Services", http://jya.com/ukttp.htm (Current version 18 July 1998).

[5] ITU-T Recommendation X.509, "Information Technology - Open Systems Interconnection - the Directory : Authentication Framework". International Telecommunication Union, 1993.

[6] ITU-T Recommendation X.509, "Information Technology - Open Systems Interconnection - the Directory : Authentication Framework". International Telecommunication Union, 1996.

[7] Joseph M. Reagle Jr., "Trust in electronic Markets : the convergence of Cryptographers and Economists", http://rpcp.mit.edu/~reagle/commerce/commerce.htm (Current version 1996).

[8] Marc Branchaud, "A Survey of Public-Key Infrastructures", http://www.xcert.com/~marcnarc/PKI/thesis/ (Current version July 1998).

[9] PKI Technical Working Group (PKI-TWG), http://csrc.ncsl.gov/pki/twg/twgindex.html (current version February 14 1998).

[10] Public Key Infrastructure Study Final Report. Produced by the MITRE Corporation for NIST. April 1994, http://www.xcert.com/~marcnarc/PKI/#Xstandards (Current version August 1998).

[11] PKIX Working Group, "Internet X.509 Public Key Infrastructure : Certificate Policy and Certification Practices Framework", April 25, 1998.

[12] Ronald L. Rivest and Butler Lampson, "SDSI - A Simple Distributed Security Infrastructure", http://theory.lcs.mit.edu/~rivest/sdsi10.html.

[13] Simson Garfinkel, "PGP : Pretty Good Privacy", O'Reilly & Associates, Inc. First Edition, January 1995.

[14] Stephen Frede, "Certificates - Who's There ?", Systems, p68, February 1998.

[15] "Strategies for the Implementation of a Public Key Authentication Framework (PKAF) in Australia", http://www.acs.org.au/president/1996/epubs/pkaf.htm (Current version 26 March 1998).

[16] VeriSign, "Digital IDs Introduction", http://digitalid.verisign.com/id_intro.htm#ID_use (current version March 12 1998).

[17] Warwick Ford and Michael S. Baum, "Secure Electronic Commerce," Prentice-Hall, 1997.

[18] W. E. Burr (Editor), "Federal Public Key Infrastructure (PKI) Technical Specifications (Version 1) Part C: Concept of Operations", Part of the US NIST PKI program, http://csrc.ncsl.nist.gov/pki/pkicon13.ps (Current version 18 July 1998).

[19] Yinan Yang, " Security Mechanisms in Electronic Commerce",

http://www.cs.adfa.edu.au/~yany97/secure-payment.html (Current version 2 December 1997).

Acknowledgements 

We would like to thank Ed Lewis, Bob McKay and Warwick Ford for their generous contribution to the work. This paper would not have been possible without their help and encouragement.