Formal definitions and complexity results for trust relations and trust domains fit for TTPs, the web of trust, PKIs, and ID-based cryptography

We propose computational, declarative definitions of the concepts of weak and strong trust relations between interacting agents, and trust domains of trust-related agents in distributed systems. Our definitions yield computational complexity results for deciding potential and actual trust relationships and membership in trust domains. We instantiate our trust concepts in four major applications of trust, namely: Trusted Third Parties (TTPs), the Web of Trust, Public-Key Infrastructures (PKIs), and Identity-Based Cryptography. Finally, we point out computational means for building trust, and by that, building up trust relations and trust domains. Our defining principle for weak and strong trust is (common) belief in and knowledge of agent correctness, respectively