DFANS: A highly efficient strategy for automated trust negotiation

Automated trust negotiation (ATN) is an approach establishing mutual trust between strangers wishing to share resources or conduct business by gradually requesting and disclosing digitally signed credentials. The digital credentials themselves are usually sensitive, so they have corresponding access control policies to control their disclosure. Therefore, an ATN strategy must be adopted to determine the search for a successful negotiation based on the access control policies. Previously proposed negotiation strategies are either not complete, disclosing irrelevant credentials, or not efficient enough. In this paper, we propose a novel ATN strategy, that is, Deterministic Finite Automaton Negotiation Strategy (DFANS). DFANS is complete and ensures that no irrelevant credentials are disclosed during the negotiation. Furthermore, DFANS is highly efficient. In the worst case, its communication complexity is O(n), where n is the total number of credentials requested, and its computational complexity is O(m) when not involving the cyclic dependencies, where m is the total size of the both sides' policies looked up during the negotiation. When cyclic dependencies exist, a reasonable additional cost of running OSBE protocol that is a provably secure and quite efficient scheme will be added to the computational cost of DFANS to guarantee the negotiation success whenever possible.