DESIGNING SECURE COMMUNICATION PROTOCOLS FROM TRUST SPECIFICATIONS

In a very large distributed system, entities may trust and mistrust ot hers with respect to communication security in arbitrarily complex way s. We formulate the problem of designing a secure communication protoc ol, given a network interconnection and a ternary relation which captu res trust between the entities. We didentify several important ways of synthesizing secure channels, and study the algorithmic problem of de signing a secure communication protocol connecting the entities, given the connectivity of the network and the trust relationship between th e nodes. We show that whether secure communication is possible can be decided easily in polynomial time. If we also require that channel syn thesis proceed along unambiguous paths (in which case the protocol is defined on a spanning tree of the network), we show that the design pr oblem is NP-complete, and we give a linear-time algorithm for an inter esting special case of the problem.