I have been reading RFC1422 which describes the hierarchy of authorities (CA = Certificate Authorities) proposed for distributing public keys for PEM and such. One must trust the CA which is a leaf of this hierarchy. If higher elements of the hierarchy are corrupted there is also danger but perhaps it is less. One interesting thing that I learned is that RFC1422 specifically allows for "personas" as in pseudonyms. Their treatment of CRLs (Certificate Revocation List) is most of the complexity and hard to understand and implement. It is a hard problem. Here is a different scheme that involves such a hierarchy but does not require one to trust anyone in the hierarchy except concerning denial of service. The scheme allows one to check the hierarchy. I ignore the revocation problem in this note. The idea stems from an idea that came from Belcore I think. The Belcore idea posits a tree of nodes where each node holds the secure hash of each of its children. The secure hash of the root node is published in the Sunday New York Times and a few other places. There are weekly editions of the tree. If I may want to prove to you in the future that some certain piece of data exists this week, then I arrange to put a secure hash of that data in some leaf of next weeks edition of the tree. If I should ever need to present proof, I display the contents of each of the nodes between my leaf and the root. (I got that list a few days after I submitted my secure hash.) You can compute the hashes of each node and observe that they each occur in the superior node. You compare the secure hash of the root node with what is in the Times. The only plausible explanation is that someone had the data at the date of publication. My CA scheme is a variation of the above. A certificate is a (name -- public key) pair. The names are stored in a tree in alphabetical order. Each node in the tree holds a pair (first name in child node, secure hash of child node) for each of its children. (This is much like a B-tree.) The tree is available thru an untrusted CA. When you request the public key from the CA corresponding to some name, all nodes from the leaf with that name, thru the root are returned. You verify the secure hashes as in the Belcore scheme. You also verify that name stuff in the intermediate nodes is correct. The later is to prevent the CA from showing one public key to some requesters and another key to others. My secure mail agent queries the data base upon each new edition to ensure that my own public key is reported correctly. (Besides being published in the Times, the hash of the top node is transmitted once per minute in video blank time on NBC.) Since the data base can't tell different requesters different things, the agent can be sure that all requesters will be informed of my correct key. I would prefer to change my public key at most once per month and then only with a month's notice. This gives me time to verify that the CA is telling the truth about my PK and warn correspondents otherwise. This avoids the attack of the CA publishing a bogus public key to which it knows the private key in order to decipher mail intended for me. In all, changing public keys may be more dangerous than not! This system still has several flaws. There is a single point of failure. Failure is not immediately catastrophic as old keys can continue in use. If you mistrust the CA you must inform your correspondents quickly, (via a signed message). If there are several such hierarchies then each user with a public key must subscribe to each lest one of the hierarchies lie about his public key. I think that revocation is better solved (easier code and smaller data) by Blum filters but that is another story. The policy revocation problems are still difficult.