PRUNES: An efficient and complete strategy for automated trust negotiation over the Internet

The Internet provides an environment where two parties, who are virtually strangers to each other, can make connections and do business together. Before any actual business starts, a certain level of trust should be established. Each party should make sure that the other one is qualified and can be trusted for the ongoing business. Property-based digital credentials [1] make it possible to prove that a party satisfies certain requirements imposed by the ongoing business. The problem is that digital credentials themselves also contain valuable information which a party does not want to show to just any strangers. Therefore, for each credential there is usually a disclosure policy associated with it, indicating under what circumstances this credential can be disclosed. 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 either fail when in fact success is possible, disclose irrelevant credentials, or have a high communication complexity. In this paper, we present a trust negotiation strategy, Prudent Negotiation Strategy (PRUNES), that guarantees that trust is established, if allowed by the credential disclosure policies. Meanwhile PRUNES makes sure that no irrelevant credentials are disclosed during trust negotiations. We also prove that PRUNES is efficient: in the worst case, the communication complexity is O(n²) and the computational complexity is O(nm), where n is the number of credentials and m is the size of the credential disclosure policies in disjunctive normal form.