IMPLICATIONS WITH IDENTITY IN PKI
Carl Ellison as edited by Jean Camp

Background

A Public Key Infrastructure (PKI) is the set of data structures, network protocols and human procedures that enables the creation, dissemination and revocation of both public keys and their empowerment, often through certificates. In full generality, there are three kinds of certificates or corresponding protected database entries.[1] A general definition of a certificate is "two or more facts represented in a machine-interpretable form that is digitally signed by a key belonging to some authority on the stated relationships among those facts".

However, PKI is generally taken only to refer to what are known as Identity (or ID) Certificates. From the name alone, one might assume that identity certificates bear a strong relation to matters of identity, identification and privacy. The proponents and opponents of ID certificates are often equally guilty of taking the name "identity certificate" too literally. The correlation is only casual.

This section gives an introduction to the concept of public keys and Public key infrastructures, a brief summary of PKI and then addresses matters of utility and privacy of various PKI visions.

Entity, Identity, Identifier and Name

The way we are using the terms, the world consists of entities. Each entity is a person or thing that has persistence. It is in one place at a time and can not clone itself. It might die or be destroyed and it was created or born at some time, but in between birth and death, there is just one entity.

The definitions used here can be found in the introduction and appendix. However, it is useful to add a couple of examples and reminders.

Recall that an identity is a set of facts about an entity. The particular collection depends on the person doing the collecting. For example, imagine a traveling salesman named John Smith, 6'2", blond, blue-eyed, 207 pounds, married to a woman named Jane and living in Cleveland. Then imagine a traveling salesman named John Smith, 6'2", blond, blue-eyed, 207 pounds, married to a woman named Mary and living in Buffalo. These could be two different men or one bigamist. From the point of view of the women, these are two different men. Only the men (man) know(s) for sure. In general, there is one identity for each pair of people: John's identity from Mary's point of view, John's identity from Jane's POV, John's identity from his own POV, John's identity from his employer's POV, etc. From this perspective each individual has his or her own namespace, in which people are defined relative to their relationship.

An identifier is some string of characters (or digits or bits) that is used to refer to an identity. Since an identity depends on the person whose eyes formed the identity, so does the identifier. For example, I use the name "Jim" to refer to my brother, but the name "Jim" spoken by you might refer to someone else entirely, assuming you even use that name alone to refer to someone. Any identifier is associated with at lease one specific namespace, but can be used across multiple namespaces.

A name is a string given to someone and used to address that person or to speak about that person. This can be a given name, typically created and assigned by the person's parents, or it can be a nickname, typically assigned through use. A name is a particular class of identifier, but not all identifiers are names. There is nothing special about a name, from a security point of view, except that people feel a special attachment to names, and names, used as identifiers, are subject to ambiguity and therefore introduce a security weakness.

An inescapable unique identifier is a permanent identifier that stays with a person for life, that is, unique over the whole population (past, present and future) and that some other party can establish without the cooperation of the identified party. A Social Security Number requires registration and can be changed. A fingerprint cannot be altered but must be entered into a reference database(in some form, perhaps with a one-way function) to be useful.

If John in the example above had an inescapable unique identifier, then one could know easily whether there were two John Smiths or one bigamist. One could also do voter registration, welfare monitoring, etc. Such an identifier has very desirable properties. However, it is difficult to achieve (e.g., might require a full genome map) and may constitute a violation of privacy all by itself.

It is important to keep these concepts straight in spite of the fact that there are many who confuse them. For example, an ID Certificate binds a name to a public key. That is, the Certificate Authority (CA) that generates the certificate and digitally signs it asserts that the name and the public key belong to the same person.

If Mary and Jane both issued public keys in their namespaces that John could identify himself uniquely in each namespace would not clarify the issue of the legality of the two marriages.

There are those who treat the name assigned to an ID Certificate as an inescapable unique identifier - not by actually considering it to be one but by assigning the properties of the inescapable identifier to the certified name. For example, they want people to use certified names so that they can't misbehave under one (key, name) association and get another name for a new key. This is a behavior of an inescapable name, not a normal CA-assigned name.

There are those who speak of a certificate "binding a public key to a person,  that is, to an entity, not even an identity, when what it binds a key to is a name and therefore an identifier. Any system design using PKI should be examined for consistency with these definitions. Systems designed by metaphor are particularly prone to logical conceptual errors that can doom the entire project.

The Participants in a PKI

The participants in a PKI have been given generally accepted names.

The end entity is the entity that is referred to by a given ID certificate. This entity is also called the keyholder, because he, she or it controls a private key corresponding to the public key in the certificate. The keyholder uses that private key to sign a message, either the individual message of interest or a message that is part of opening a secured channel.

The certificate authority is a person or corporate entity that issues a certificate binding an ID to a public key (or, more generally, binding any combination of things together).

The relying party is the person or program that examines the certificate, verifies its signature, extracts the ID and tries to make sense of it.

A certificate authority creates its own namespace. The relying party chooses to enter that space by verifying themselves and sending certificates to be verified.

There might also be an authorization database or central directory where the relying party can go to learn the kind of information that could be carried in a certificate.

Conflicting Concepts of the Purpose of PKI

There are two basic views of the purpose of PKI. One view offers to enable the distribution of public keys as an end of itself. Before the creation of public key, secure key distribution was a critical problem in cryptography. If a key is compromised the entire system is compromised; therefore the requirement that shared keys be transmitted before the communication was a chronic problem.

The other view of public key infrastructures put the focus on infrastructure as opposed to keys. In that view, the PKI is a tool that enables entities to assert an certain claim: membership in a club or willingness to pay.

The original paper by Diffie and Hellman (see "A Brief History" below) focused on the concepts of keys rather than infrastructures. They wanted to make sure that everyone in the world would have access to the public keys of everyone else in the world. All authorization decisions are left to the user and are not part of the PKI. With this kind of PKI, one can encrypt e-mail or telephone conversations to anyone in the world. This helps frustrate eavesdroppers, especially national intelligence services.

This configuration does not prevent what is called the Man In The Middle (MITM) attack. A MITM attack is implemented by the relying party connecting to the wrong entity with an encrypted channel or message and that entity then relays the channel or message on to the correct entity re-encrypted for that entity, while first having read the channel or message. 

An MITM attack works like this:  A nefarious party situates himself between two parties, Bob and Alice, that might attempt to communicate.  The MITM pretends to be Bob and forwards messages to Alice, and pretends to be Alice in communicating with Bob. Both parties believe they are engaging in a bona fide discussion.  The linking of the key to the identity is subverted while the encryption itself remains strong. The ability of a PKI to thwart a MITM attack depends on the quality of the information included in the certificate or database entry that makes up the PKI and on the relying party's ability and desire to use it.

HTTPS using SSL in web browsers employs a PKI built according to this vision. If a web page is displayed with a closed padlock, then one knows that the page was served from a machine possessing a private key whose public key was associated with the domain name from which that page was served. This does not mean that the page was served from the company the user imagines it came from or that the company behind the web page can be trusted for any particular business purpose. However, users have been trained to make their security decision based on the closed padlock rather than on an investigation of the certificate that enabled the closed padlock or any other information. Thus, users perceive PKI as performing the infrastructure operation of binding while in fact it is performing the key distribution operation. This mismatch of expectations and functions is a chronic problem in Internet commerce. This led to a comment by the respected cryptographer Matt Blaze in January of 2000, that "a commercial CA will protect you from anyone whose money it refuses to take."

Matt's comment reflects the second view of a PKI - that it should communicate authorization information and be very selective. Any given security decision should find that only the few correctly authorized entities are certified by the PKI. In this view, there are as many different PKIs (different, independent Certificate Authorities (CAs)) as there are different resources to protect. This is the approach taken by more modern PKI efforts (see "PKI Efforts for the Second Goal" below).

If your goal is security enforcement, systems designed simply to provide universal key access are unacceptable by definition, and need to be augmented. If your goal is to disseminate keys nationally or globally via a single PKI, then systems designed to meet the second goal are unacceptable as they will exclude those about whom there is limited authorization information. Definition of organizational goals must be aligned with the PKI for the system to be effective.

Security Decisions: Authorization

There is a model of security decision established in the 1960's with multi-user time sharing systems that goes by the name of IAA: Identification, Authentication and Authorization.n a time-sharing computer system, one would perform these steps as follows: 

1. Identification: On approach to the time sharing terminal, the user would be prompted for a Username. The name supplied is the user's identification. 

2. Authentication: Identification is just a claim. Authentication is a proof that the person at the keyboard is allowed to use that identification. In time sharing systems, this was done by the user's typing a secret password known only to the user and the computer system.

3. Authorization: The user's authenticated ID was carried by the time sharing system in protected system storage, from then on. Whenever the user wanted to do some operation that required specific authorization, the user's authenticated ID was used to check against a list of permissions, usually in the form of an Access Control List (ACL). The ACL would be associated with a given resource (such as a disk file or directory) and would list users and what they were allowed to do (e.g., an entry in a file ACL might be [cme, read] meaning that user 'cme' is allowed to read this file but not modify it, delete it, etc.).

When a system is distributed, with components connected by network, each message that asks for some access to a protected resource needs a security decision and therefore its own IAA. In a distributed system, there may be a user logged in on one component, but not on all components. In very large distributed systems it is practically impossible for a user to log onto all components simultaneously.

An access control list is, in fact, a list that gives privileges that correspond to the authorization. For example, it may be as simple as this: Name Authorization Access Resource Access Right Joe Smith project: strategy1 M: strategy read, write Maria Gonzalez project: finance M: finance read, write Wei Zeng travel coordinator M: finance/accounts read.

As public keys enable more complex forms of interactions with respect to access, more features, such as delegation of access rights, are made possible.

For a component without a user, IAA takes a slightly different form: 

1. Identification: The incoming message (or connection setup) is digitally signed and that signature includes a public key by which the message signature is verified. That key identifies the private key that signed the message.

2. Authentication: The signature on the incoming message (or connection setup) verifies that it has not been tampered with since the private key signed it. 

3. Authorization: Each signed message or each message arriving over a channel whose setup was signed came from a given key, but you need to make a security decision. Instead of asking if some user is allowed to do the requested action, one needs to ask if the key (that is, the keyholder) is allowed to do the requested action. As with the user on a time-sharing system, this requires an ACL. In this case, that ACL is sometimes called a list of root keys (or, in the browsers, a list of root certificates). [Note: when root keys are contained in certificates, the certificate adds no value except as a vehicle for carrying the public key. The security of the root key store depends on how that storage is protected on the relying party's computer.] 

4. Delegation: With public keys as the authorized identifier in an ACL, you have the opportunity to delegate that authorization via certificate. For example, in SSL for encrypted web browsing, the ACL contains the keys of a certificate issuer but the web pages that are allowed to display the closed padlock icon do not belong to those issuers. Rather, they belong to keyholders who are certified by those issuers. For another example, UPnP Security allows home users to delegate access (e.g., from a parent to a teen child and from there to the child's friends).

A Brief History of PKI

The concept of binding information to a public key is over 25 years old. In spite of the age of this concept, the idea has not found general use, as is discussed above. This section deals only with the history of the development of the ideas involved in PKI.

Diffie and Hellman

In 1976, Diffie and Hellman published their seminal paper on public key cryptography 3. In that paper, they introduced the concept of the Public File. This was a directory meant to be available to all relying parties, either by distribution of printed copies (like a telephone book) or as an online database. It was intended to solve the problem of key distribution. That is, if you are encrypting a message intended for my eyes only, you need to use a key that you share with me and me alone. If you have received a message claiming to be from me, then you need to verify that it was authenticated by a key that only I possess.

"Given a system of this kind, the problem of key distribution is vastly simplified. Each user generates a pair of inverse transformations, E and D, at his terminal. The deciphering transformation, D, must be kept secret but need never be communicated on any channel. The enciphering key, E, can be made public by placing it in a public directory along with the user's name and address. Anyone can then encrypt messages and send them to the user, but no one else can decipher messages intended for him." 3  

The implied process in the last sentence of that quote is that anyone can find the intended recipient in that public directory, get that person's public key, and encipher a message for that person's eyes only.

In our terminology, this directory kept an association between a public key and a portion of the keyholder's identity (name and address). As we note below, this idea suffers from confusion between identity and entity. The identity information (name and address) is associated with some entity, but is not the same as the entity. There can be two entities with the same name and address (father and son, for example, or two students in a large college dorm). There can be one entity with more than one name and address. But the most serious problem is that the selection of identity information given in the Public File might not be part of the identity information that the relying party knows about the entity. More specifically, the intersection of the information known about the keyholder by the relying party and the information in the directory needs to be enough to specify that entity uniquely. A possible solution to this last problem is to add more information to the directory entry, until that intersection is large enough. As we discuss further, this would turn that directory entry into a privacy violation.

Kohnfelder

The Public File was an interesting concept for the reader, to help put across the power and novelty of public-key cryptography, but it had problems. Loren Kohnfelder addressed some of those in his 1978 Bachelor's thesis from MIT 4.

One of the first problems, assuming this directory is global and online, is one of performance, especially in the face of network partitions. With everyone in the world going to the same directory to look up associations between names and public keys, that directory would suffer massive network congestion and the resulting poor performance. This problem would be much worse during those times when the Public File was in a portion of the network that you could not reach at the moment (a different network partition).

Kohnfelder's solution was to use public key authentication. Each line item in the Public File could be digitally signed by the private key of the publisher of that Public File. That would make that one entry invulnerable to tampering and immediately verifiable, without requiring it to be specially protected. It is protected by its digital signature. Therefore, this signed line item could be held by the person who cares the most about it: the one whose key is being referred to.

This person could then submit this signed line item to his or her communication partner to allow that other party to know with whom it was dealing. This could happen even if the Public File was unavailable. In fact, the central directory would not need to exist as such, given these signed line items in the hands of those who cared about them.

Kohnfelder needed a name for this new construct. He chose the word 'certificate'.

X.500 and X.509

The concept of a global directory of people (and other communicating things) was a natural for the CCITT. The International Telegraph and Telephone Consultative Committee (CCITT) [now called the ITU Telecommunication Standardization Sector (ITU-T)] is a technical study body chartered by the United Nations. The International Organization for Standardization (ISO) is the corresponding standards body, also chartered by the UN. ITU-T/ISO created the X.500 standard in the 1980's. X.500 was to be a global directory of everything that could have a telecommunications connection (phone number or network address). This included computers, computer peripherals and, of course, people. X.500 included the specification of a so-called Distinguished Name (DN) that could be used to specify someone or something uniquely. The DN is a hierarchical name that could be assigned by some central global naming authority. This naming authority could be distributed to subordinate entities, with the bulk of the work of name assignment being done by organizations to which the central authority delegated responsibility for a sub-tree of the DN space.

X.509 was a subordinate standard to X.500 and it specified digital certificates to bind the DN of a person (or device) to its public key.

The first attempt to use X.509 certificates in a widespread set of products was the Privacy Enhanced Mail (PEM) project of the Internet Engineering Task Force (IETF), circa 1990. PEM was an e-mail encryption and signing tool that used public key methods for both confidentiality and authentication and relied on X.509 certificates for binding public keys to individuals (via their DNs). PEM failed, primarily because of the choice of using X.509. In 1990, there was no source for X.509 certificates.

Perhaps more serious was the association between X.509 and legal liability that was being discussed even in 1990. For example, one company (Stratus Computer) refused to choose a Distinguished Name for itself and thereby join the X.509 hierarchy because the claim was being made that a digital signature by key bound to the company might make the company liable. This issue, now called non-repudiation, is still a danger associated with X.509, retarding the adoption of X.509 certificates 5.

Certification Practice Statements

For those who want to believe that a certificate binds a key to a person, via the DN in the certificate, a certificate issuer must publish a Certification Practices Statement (CPS). This statement often describes the process by which the Certificate Authority (CA) attempts to establish that the keyholder really is the named person. This statement often becomes a legal disclaimer. The CPS rarely if ever addresses the fact that having one identifier for a person is inappropriate, as noted in the previous section.

Bridge CAs

Since there are individual, independent CAs, rather than a global CA hierarchy as envisioned by some early theorists (as in PEM), there is a need to form a bridge between these independent CAs. This presumes that the purpose of a PKI is to give certificates to everyone on the earth such that everyone else on earth can verify them.

PGP

In the early 1990's, while PEM was failing, an independent effort, not tied to X.509 certificates, was developed to provide for e-mail and file encryption. This was called Pretty Good Privacy or PGP for short. PGP used what was called the Web of Trust to certify keys 6. The resulting certificates differed from X.509 in two fundamental ways: 

1. They used a keyholder's common name plus e-mail DNS name instead of an X.500 DN as the identifier. 

2. They were signed by multiple independent parties instead of one especially hardened Certificate Authority. Each independent party was a normal user, but an attacker would have to subvert (or steal the keys of) a large number of such signers in order to falsify a certificate.

PGP suffered from the same problem as X.509, however, in that it used a single identifier to represent a person. This identifier was chosen by the keyholder rather than some third party and also included a unique name (the e-mail address) that the relying parties were likely to know, so it offered a security advantage over X.509. Nevertheless, the use of a single name for an entity falls into the trap of assuming that identity and identifiers are associated with the end entity rather than the pair (end entity, relying party).

PKI Efforts for the Second Goal

All of the PKI efforts described above are based on the first goal of PKI: that keys are to be distributed to all entities in the world. All other entities would then be able to verify an ID of any other key. This assumes that the identifier is adequate to allow the relying party to make a security decision.

The PKI efforts following the second goal address the problem of making security decisions. These efforts capture authorization information, not just an ID (and often not an ID at all).

In all of these cases except the attribute certificate, key management must be done by some non-PKI process. However, the authorization management is being performed at the same time. Therefore, the work to do key management for those PKIs not using an ID PKI is the same amount of work as the authorization management would have been, and the former is often more accurate (because there is no name confusion inherent in indirecting through a name). In the case of attribute certificates, there is extra work.

X9 Attribute Certificate

The ANSI X9 committee (dealing with banking) first defined an attribute certificate to attempt to address the problem discussed in section on authorization, that knowing some keyholder's identifier does not allow you to make a security decision (authorization decision). Other information is needed. The attribute certificate was designed to bind this additional information to an X.509 DN and therefore indirectly to the public key of the keyholder. This attribute certificate was to give the information needed for the security decision.

As discussed in more detail elsewhere1, this opens up a security problem. In cases where the issuer of the attribute certificate has authority to bind that attribute to the keyholder but the issuer of the ID certificate does not, this gives that authority indirectly to the issuer of the ID certificate.

SSH and X9.59

SSH and X9.59 avoided the pitfalls of X.509 by keeping public keys in the relying party's protected storage 7. In SSH, this is the file .ssh/authorized_keys. In X9.59, it is a bank's account records. These keys are authorized to perform specific actions. In the case of SSH, the keyholder is allowed to log into that account or transfer files in and out via the SCP command. In the case of X9.59, the keyholder is allowed to manipulate that one bank account. 

SDSI

SDSI (Simple Distributed Security Infrastructure) addressed the problem of identity and identifiers belonging to the pair (end entity, relying party) rather than just to the end entity. At this time, it is the only ID PKI design that recognizes this fact and accommodates it 8.

SDSI is used to define groups of precisely those entities that should have a particular kind of access. In this sense, although SDSI is an ID PKI, it provides for authorization information.

SPKI, PolicyMaker and KeyNote

Starting in 1995, two independent efforts addressed the problem that an ID PKI fails to communicate the information necessary for a security decision by defining certificates that bound that information directly to a public key. This simplified the system using these certificates and improved on the security of the resulting system, since the issuer of the ID certificate was not used and therefore was no longer in a position to circumvent the authorization grant. These efforts were SPKI and PolicyMaker (which has since spun off KeyNote ) 9, 10, 11. These differ primarily in how authorization information is expressed. SPKI uses a restricted language expressed in canonical S-expression  form, and defines an intersection of authorizations expressed in that language 12. PolicyMaker uses an executable language for expressing authorization decisions and carries the actual decision code (yielding a "yes" or "no" answer) in the body of the certificate. KeyNote uses what looks like an executable conditional expression to express authorization. For more details, consult their respective web sites 2.

Usefulness of a PKI

There are a number of companies that have purchased and deployed a PKI, only to discover that it cost a great deal of money, involved considerable time and effort and yet gave them no advantage. Part of this problem can be traced to a confusion of terms, as defined and elaborated previously. Part of it is the result of the fact that a PKI is only part of the solution and worthless by itself, as described above. In general they are likely discovering that to have a security effect, one needs a PKI meeting the second goal, whereas they had bought a PKI meeting the original goal.

Even when an ID PKI is augmented by some auxiliary authorization data, there are security problems.

Too much power for the ID CA

The use of an ID PKI gives the ID CA the power to get any authorization that any ID has been granted and give that authorization to any other keyholder, by issuing a certificate to that second (improper) keyholder under the ID of someone who has been authorized. This is too much power for an ID CA, in many cases. 

The John Wilson Problem

This is one name for the general problem that results when one ignores the definitions in the first section. A man named John Wilson known to a number of us keeps getting corporate mail intended for other employees named John Wilson, because the company he works for has 8 men named John Wilson.

Sometimes this mail is nonsense, but sometimes it is very sensitive. At one time, he received the renewed passport of one of the other John Wilsons. At another time, he was in one of his doctor's examining rooms waiting a long time for the doctor, who had gone to the wrong examining room and was discussing our friend's medical history with another John Wilson. At another time, he was about to board an airplane with the wrong boarding pass, because his boarding pass had been given to another John Wilson on the same flight.

A large PKI exacerbates this problem. SDSI defines names that are much more useful than names from a large PKI, but even those names can cause trouble 8. SDSI names would not have prevented the misuse of names by John's doctor, for example.

The fundamental problem here is that people have a habit of using names as if they were unique identifiers correlated 1:1 with entities. A well designed system will avoid using names to identify people. Of course, we can't buy such systems today, but there are some in development.

PKI versus Privacy

There are those who worry about an ID PKI because it binds a person's name (worse, Distinguished Name, in some cases) to a public key. This appears to be a violation of privacy. There are possible violations of privacy with any PKI, but the name in an ID certificate is not the worst problem.

Distinguished Name versus Key

If our friend John Wilson gets an ID certificate binding his name to his public key, and if the relying party validates this certificate and keeps a record of the name while throwing away the key, John's privacy might be damaged but it would be damaged more if the relying party were to keep the public key and throw away the name.

A public key, besides being a cryptographic quantity that is useful in computations, is a string of bytes. It is also globally unique. It is also provably associated with the person who sent the signed transaction message or opened the authenticated channel over which the transaction in question was delivered. This makes the public key an ideal identifier for someone who is building a dossier of activities of the keyholder.

The name "John Wilson", on the other hand, is quite ambiguous.

A Distinguished Name is supposed to be unique. Under the original X.500 thinking, there would be one (distributed, hierarchical) name service in the world so that everyone would have a unique name. However, since the global X.500 has never come about and is unlikely ever to, there are instead independent CAs, each assigning independent DNs to end entities. Therefore, it is possible (perhaps even likely) for two different entities to have the same DN. This isn't anonymity, but it is less invasive (after the model of the U.S. Census Bureau) than guaranteed global uniqueness of ID.

X.509 was designed to treat the DN as a unique quantity. Therefore, it is likely to be stored as a stand-alone unit in some relying party's transaction log. This is a privacy advantage over storage of the public key because it restores some ambiguity.

A public key is large. One can use the cryptographic hash of the public key as another globally unique ID for the keyholder. Either the key or its hash is more of a privacy violation than the DN.

However, this suggests that all use of public key technology threatens privacy. In fact, any authentication at all threatens privacy, if the same authentication key (or name and password or biometric, etc.) is used for more than one transaction. The alternative is authentication and authorization by zero-knowledge proof methods, but that is a topic for a different technical report.

X.500 Directory

A Distinguished Name in X.509 is an index (path name) into an X.500 directory. At the indicated directory entry, one will find information about the keyholder. Recall that for a relying party to know who a given keyholder is, that relying party must intersect what he or she knows about the keyholder with the X.500 directory entry (or the contents of the ID certificate) and that intersection must be enough to specify that individual uniquely 13. It is best if the intersection is much more than enough, in order to provide added security (e.g., if you are just about to e-mail a very sensitive document to someone for his or her eyes only).

It is possible to make a directory entry that is rather small, if each relying party builds and uses his or her own directory, after the manner of SDSI. However, if one wants to have a single directory (or single certificate with all directory information contained inside) that will be usable by every possible relying party, then that directory entry needs to contain the union of all information any relying party would need to see to verify the identity of the keyholder. This union of that information would probably be a complete dossier on the keyholder and almost certainly a violation of privacy.

Commercial Certificates

Commercial certificate authorities are often optimized for use within a single organization. The assumption is that this organization has complete knowledge and authority to have this knowledge over employees. In contrast the government and citizen relationship is different in a way that has technical design implications.

As noted previously, if one uses a public key in a non-zero-knowledge protocol, that key becomes an ID that allows a party bent on violating the keyholder's privacy to link together the keyholder's actions. Therefore, for maximum privacy, a keyholder needs a large number of public keys.

The very assumption that may be optimal in digital government runs against the normal mode of operation of commercial certificates for many reasons. First, these certificates often cost money. A user will be disinclined to purchase a new certificate for each different transaction (in the extreme limit). Second, the commercial CA will doubtless attempt to keep enough identity information with each certificate issued to allow it to link together the various public keys of the keyholder, thus allowing it to violate that user's privacy. Third, commercial CAs often have the policy of one certificate per user. Finally, commercial certificates are all (at present) of the ID form and that ID alone would link all these certificates together to some extent. There is interesting work on a PKI that preserves anonymity, but this has not been deployed yet.

In summary, PKI is a powerful and potent tool. PKIs can be used to arbitrarily implement a binding between a key holder and an attribute. The implications of a PKI as used in digital government are not now completely understood.

REFERENCES

1 Ellison, "Improvements on Conventional PKI Wisdom ", 1st Annual PKI Research Workshop, April 2002. http://www.cs.dartmouth.edu/~pki02/Ellison/

2 Ellison, C. M., "Home Network Security." Intel Technology Journal. http://developer.intel.com/technology/itj/2002/volume06issue04/ (November 2002).

3 Whitfield Diffie and Martin Hellman, "New Directions in Cryptography", IEEE Transactions on Information Theory, November 1976, pp. 644-654.

4 Kohnfelder, Loren M., "Towards a Practical Public-key Cryptosystem", MIT S.B. Thesis, May. 1978.

5 Cem Kaner, "The Insecurity fo the Digital Signature", 1997, http://www.badsoftware.com/digsig.htm

6 Ellison, "SPKI/SDSI and the Web of Trust", http://world.std.com/~cme/html/web.html

7 Secure Shell: http://www.ietf.org/html.charters/secsh-charter.html and http://www.ssh.com/

8 SDSI home page: http://theory.lcs.mit.edu/~cis/sdsi.html

9 SPKI home page: http://theworld.com/~cme/html/spki.html

10 Blaze, Feigenbaum and Lacy, "Decentralized Trust Management", IEEE Symposium on Security and Privacy, Oakland, CA. May 1996. http://crypto.com/papers/policymaker.pdf

11 Matt Blaze, "Using the KeyNote Trust Management System", http://crypto.com/trustmgt/kn.html

12 Ron Rivest, "SEXP - (S-expressions)", http://theory.lcs.mit.edu/~rivest/sexp.html

13 Dohrmann and Ellison, "Public-key Support for Collaborative Groups", http://www.cs.dartmouth.edu/~pki02/Dohrmann/

14 Stefan Brands, Rethinking Public Key Infrastructures and Digital Certificates; Building in Privacy, The MIT Press, August 2000, ISBN 0-262-02491-8.