Ultimately, only the user of a public key can decide whether to trust its authenticity. Whether that trust is possible in a particular circumstance depends on the history of the key, the use to which it is about to be put and the skepticism or gullibility of the user. We will concentrate on only the first of these, though we note in passing that the user should probably take greater care to verify the authenticity of a key which is about to be used to encrypt a confidential report than the one used to check a signature on a Usenet posting to talk.bizarre.
As with the early Internet, currently the majority of PGP users are hackers (in the old sense!), many of them downloading and building their own PGP binaries. Most understand the workings of PGP, generate their own keys and have them signed by other users of PGP. An anarchic but apparently effective web of trust is built up.
Some groups of PGP users have a slightly more organized approach. For example, many representatives of security incident response teams use PGP for their private communications. At meetings between representatives (the FIRST workshops held each year are particularly good examples) a ``key-signing party'' is held. Each holder of a key proclaims the authenticity of that key and the other representatives decide whether to trust the assertion. If they are satisfied that the key's ownership has been verified, they will sign that key (usually after returning from the meeting) with their own private key. The keys of most teams and their members are now cross-verified in a tightly-knitted web of trust.
These approaches to key certification may be adequate for the enthusiastic users of PGP and may be tolerable for those who deal with especially sensitive information. They are not appropriate for the great majority of JANET users.
To make PGP easy to use by the majority of JANET users, at least four things are required. First, the users' keys must be easy to generate in the first place. Second, it must be easy for a key to acquire at least one trustworthy signature. Third, there must be a simple but adequately secure way to recover access to the private key should the protective passphrase be forgotten. Fourth, it must be easy to revoke the key, should it be compromised.