Paper 2011/235

Computer-Aided Decision-Making with Trust Relations and Trust Domains (Cryptographic Applications)

Simon Kramer, Rajeev Goré, and Eiji Okamoto


We propose generic declarative definitions of individual and collective trust relations between interacting agents and agent collections, and trust domains of trust-related agents in distributed systems. Our definitions yield (1) (in)compatibility, implicational, and transitivity results for trust relationships, including a Datalog-implementability result for their logical structure; (2) computational complexity results for deciding potential and actual trust relationships and membership in trust domains; (3) a positive (negative) compositionality result for strong (weak) trust domains; (4) a computational design pattern for building up strong trust domains; and (5) a negative scalability result for trust domains in general. We instantiate our generic trust concepts in five major cryptographic applications of trust, namely: Access Control, Trusted Third Parties, the Web of Trust, Public-Key Infrastructures, and Identity-Based Cryptography. We also show that accountability induces trust. Our defining principle for weak and strong trust (domains) is (common) belief in and (common) knowledge of agent correctness, respectively.

Note: added two bibliographic references

Available format(s)
Publication info
Published elsewhere. J Logic Computation (2012) doi: 10.1093/logcom/exs013
cryptographic-key managementTTPWeb of TrustPKI
Contact author(s)
simon kramer @ a3 epfl ch
2012-05-31: last of 2 revisions
2011-05-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Simon Kramer and Rajeev Goré and Eiji Okamoto},
      title = {Computer-Aided Decision-Making with Trust Relations and Trust Domains (Cryptographic Applications)},
      howpublished = {Cryptology ePrint Archive, Paper 2011/235},
      year = {2011},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.