Tech Report CS-06-07

Flexible, Secure and Private Point-based Trust Management

Danfeng Yao, Keith B. Frikken, Mikhail J. Atallah, Roberto Tamassia

April 2006


There has been much recent work on privacy-preserving access control negotiations, i.e., carrying out the negotiation in a manner that minimizes the disclosure of credentials and of access policies. This paper introduces the notion of point-based policies for access control and gives protocols for implementing them in a disclosure-minimizing fashion. Specifically, Bob values each credential with a certain number of points and requires a minimum total threshold of points before granting access to a resource to Alice. In turn, Alice values each of her credentials with a privacy score that indicates her reluctance to reveal that credential. She is interested in achieving the required threshold for accessing the resource while minimizing the sum of the privacy scores of her used credentials. Bob's valuation of credentials is private and should not be revealed, as is his threshold. Alice's privacy-valuation of her credentials is also private and should not be revealed. What Alice uses is a subset of her credentials that achieves Bob's required threshold for access, yet is of as small a value to her as possible.

We give a protocol for computing such a subset of Alice's credentials without revealing any of the two parties' above-mentioned sensitive valuation functions and threshold numbers. The main advantages of our scheme are that $ it prevents pre-mature information leakage when the trust establishment is unsuccessful; $ it efficiently supports cumulative privacy, which we define as the sensitivity of a combination of credentials being additive; and $ it mitigates the danger to both parties from probing attacks by their counterpart. Note that, in the proposed point-based scheme, two individuals with identical credentials have the flexibility of satisfying the access threshold in very different ways, depending on their own individual privacy criteria.

A contribution of this paper that goes beyond the specific problem considered is a general method for recovering an optimal solution from any value-computing dynamic programming computation, while detecting cheating by the participants. Specifically, our traceback technique relies on the subset sum problem to force consistency.

(complete text in pdf or gzipped postscript)