Cryptology ePrint Archive: Report 2011/235

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

Simon Kramer and Rajeev Goré and Eiji Okamoto

Abstract: 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.

Category / Keywords: foundations / cryptographic-key management; TTP; Web of Trust; PKI

Publication Info: J Logic Computation (2012) doi: 10.1093/logcom/exs013

Date: received 12 May 2011, last revised 31 May 2012

Contact author: simon kramer at a3 epfl ch

Available format(s): PDF | BibTeX Citation

Note: added two bibliographic references

Version: 20120531:155321 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]