The term "cross certification" bears some discussion. Let's suppose
there are two distinct hierarchies, A and B, with PCA-A and PCA-B at
the repsective tops. One way for users within A and B to interact
with each other is to have PCA-A issue a certificate for PCA-B and
PCA-B issue a certificate for PCA-A. Let me call this "syntactic
cross certification" because it refers specifically to the creation of
a certificate signed by an entity that is not immediately above the
subject. Syntactic cross certification leaves open some questions.
Users -- or their implementations -- seeing these certificates would
then have to figure out what it meant and how to follow the graph.
Another way to proceed is to have a separate means to inform users
within, say, the A hierarchy what to do if they process a certificate
and its validation chain traces up to PCA-B. This separate means
could be something manual, it could be a separate protocol such as a
PEM message from PCA-A which sends out PCA-B's dname and key, or it
could be something else. Let me call this "semantic cross
certification."
These are not opposing alternatives. Syntactic cross certification
can be used in the implementation of semantic cross certification,
provided there is an understanding that certificates issued by the
issuing entity are to be treated as semantic cross certifications.
Without such an understanding, syntactic cross certificates don't have
any well defined meaning.
In the PGP world, syntactic cross certificates are augmented with
local trust rules to provide guidance on how to integrate the various
certificate chains. As you point out, there are issues related to
scaling, completeness and revocation that don't seem to have complete
solutions. Nonetheless, the bottom up nature of the system makes it
possible for large numbers of people to use the system without having
to establish a large and fully elaborated hierarchy.
Steve