  Safeguarding online communications using public key cryptography is a
well-established practice today, but with the increasing reliance on
`faceless', solely online entities one of the core aspects of public key
cryptography is becoming a substantial problem in practice: Who can we trust to
introduce us to and vouch for some online party whose public key we see for the
first time? Most existing certification models lack flexibility and have come
under attack repeatedly in recent years, and finding practical improvements has
a high priority.
  We propose that the real-world concept of a notary or certifying witness can
be adapted to today's online environment quite easily, and that such a system
when combined with peer-to-peer technologies for defense in depth is a viable
alternative to monolithic trust infrastructures.
  Instead of trusting assurances from a single party, integrity certifications
(and data replication) can be provided among a group of independent parties in
a peer-to-peer fashion. As the likelihood of all such assurance providers being
subverted at the very same time is very much less than that of a single party,
overall robustness is improved.
  This paper presents the design and the implementation of our prototype online
notary system where independent computer notaries provide integrity
certification and highly-available replicated storage, and discusses how this
online notary system handles some common threat patterns.
