Trust is an edge, not vertex, property
I've been too passive for a very long time. It's time for me to come out of my self-imposed hibernation and talk about things I really love talking about. Earlier this year, I moved out of Nokia Research Center, and joined a wonderful startup called Lookout Mobile Security, where I work as a software engineer. (Lookout is probably one of the few security companies that has got usability and security right.) Although, I'm no longer doing active research, I do try to keep up with the research community as best as I can (old habits die hard as you know 
).
To kick things off, let's talk about the issue of trust. DigiNotar, a dutch Certification Authority, was recently hacked into issuing as many as 200 fraudulent SSL and EV-SSL (OV) Certificates, including fake certificates for Gmail, Yahoo, Mozilla, and Tor. Every time an incident like this occurs, the Internet gets abuzz with proposals and counter proposals on how to replace CAs with either a web-of-trust model, or with new perspectives
on how to make PKI more "distributed," (i.e., a SSH style leap-of-faith authentication, augmented with distributed SSL Observatories). Lost in this mechanism debate, however, is the real conceptual issue of what trust is, and what does it mean for end-host authentication.
The traditional view of trust is that it's a property of a vertex. That is, in the interconnection graph between humans, machines, organizations, etc., (please see figure on right; renders properly in Safari!), trust is inherently a property of the vertex itself. We assume that a person, a certificate, or an organization is inherently trustworthy—in isolation! It's this notion of trust that's the foundation of PKI, that relies on granting certificates to named entities, as opposed to interaction between entities.
In reality, trust is really an accumulated measure of expectation fulfillment between vertices. That is, a user is trustworthy because of the way she interacts with others and never—a categorical never—an inherent property of the vertex (person) itself. Therefore, IMHO, the first step towards solving the PKI problem is to find ways to make inferences about vertices based on the information present in the edges. In fact, many systems outside the realm of cryptographic security, explicitly make use of edge-properties to make inferences about the trustworthiness of a vertex. A good example is the PageRank algorithm which, in contrast to TFIDF—a vertex only algorithm—uses link-structure to find relevant (i.e., trustworthy) web-sites.
You could argue that the web-of-trust model already takes edge interactions into account, and therefore already does what I'm suggesting. After all, in PGP, don't individuals accept or reject keys on the basis of their own interaction with others? (Personally, I have not met one single PGP/GPG user who has ever rejected a key! But that could be because I don't interact with too many people )
Granted, the web-of-trust model does a better job than PKI in deciding who to trust, yet it still relies on an ad-hoc selection of vertices called "trusted introducers" to make trust decisions. In my personal opinion, what is needed is an independent algorithmic means to make inferences about all vertices based on edge properties (similar to computing the first dominant EigenVector of the entire Web Graph derived adjacency matrix in PageRank). In other words, you don't (and shouldn't) get to pick who is trustworthy or not; you only get to interact with others—and the system computes the trustworthiness of each vertex on the basis of these edge interactions. Fair enough?
The second issue is that trust is never static. PKI (X509, to be precise) addresses the dynamic nature of trust by its "Not Before" and "Not After" fields and by issuing Certificate Revocation Lists. Both these approaches are too coarse grained, and do not capture the moment to moment varying nature of trust. A good authentication system will dynamically update its trust measure as interaction between vertices evolve, and will not depend on a handful of entities in the system.
Finally, trust and identity should not be separated from one other. In X509, what you verify is the signature(s) and what you trust is the private key, by association. The identity in the certificate, however, is really just a blob of data added on as an afterthought. If we look at the physical world, however, trust and identity are inextricably interlinked. For example, regardless of what name a person assumes, the legal system still treats a "natural person" on the basis of her behavior, not just her name. Treating identity separate from trust inherently opens doors for numerous forms of attacks. In fact, this is one of the reasons why Identity Based Encryption algorithms are quite interesting, even though they are currently not practical on a global scale (current IBE systems require a global namespace and a global KDC, which are not practical at the Internet scale).
Although it's a lot of fun analyzing new ways of augmenting PKI, I also believe that PKI and X509 are here to stay! The complexities of overhauling it are immense and the ROI too little.