A Complete and Efficient Strategy Based on Petri Net in Automated Trust Negotiation

Traditional security model, where the identity of all possible requesting subjects must be pre-registered in advance, is not suitable for the distributed applications with strong real-time requirements, especially recently popular P2P networks and Grid computing. A promising approach is represented by automated trust negotiation, which establishes trust between strangers through the exchange of digital credentials and the use of access control policies. An automated trust negotiation strategy needs to be adopted to establish trust between two parties based on their disclosure policies. Previously proposed negotiation strategies may fail when in fact success is possible, disclose irrelevant credentials, or have high communication or computational complexity. In this paper, we model the policies participating trust negotiation as Negotiation Petri Net and propose a trust negotiation Strategy based on Negotiation Petri Net (SNPN) by combining the characteristics of Negotiation Petri Net architecture with the behaviors of auto trust negotiation. We prove that SNPN is efficient with O(n) communication complexity and O(nm) computational complexity including Negotiation Petri Net building process and the negotiation process in the worst case, where n is the number of credentials and m is the size of the credential disclosure policies. Meanwhile SNPN is complete and makes sure that no irrelevant credentials will be disclosed during negotiations.