[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

new PolicyMaker paper available

It occurs to me that our recent paper on the formal notion of
"proof of compliance" in PolicyMaker may be quite relevent to the SPKI
effort.  In particular, we show that finding proofs of compliance with
a distributed policy (which is, in general, what PM and SPKI attempt
to do) is in general hard but has useful special cases (including the
PolicyMaker scheme) that are easy.

The paper was presented at FC'98; the pre-proceedings version can be
grabbed from:


I've attached the abstract below.


Compliance Checking in the PolicyMaker Trust Management System 

by Matt Blaze, Joan Feigenbaum, and Martin Strauss 


Emerging electronic commerce services that use public-key cryptography
on a mass-market scale require sophisticated mechanisms for managing
trust. For example, any service that receives a signed request for
action is forced to answer the central question ``Is the key used
to sign this request authorized to take this action?'' In some
services, this question reduces to ``Does this key belong to this
person?'' In others, the authorization question is more complicated,
and resolving it requires techniques for formulating security
policies and security credentials, determining whether particular
sets of credentials satisfy the relevant policies, and deferring
trust to third parties. Blaze, Feigenbaum, and Lacy [BFL] identified
this trust management problem as a distinct and important component
of network services and described a general tool for addressing
it, the PolicyMaker trust management system.

At the heart of a trust management system is an algorithm for
compliance checking. The inputs to the compliance checker are a
request, a policy, and a set of credentials. The compliance checker
returns yes or no, depending on whether the credentials constitute
a proof that the request complies with the policy. Thus a central
challenge in trust management is to find an appropriate notion of
``proof'' and an efficient algorithm for checking proofs of

In this paper, we present the notion of proof that is used in the
current version of the PolicyMaker trust-management system. We show
that this notion of proof leads to a compliance-checking problem
that is undecidable in its most general form and is NP-hard even
if restricted in several natural ways. We identify a special case
of the problem that is solvable in polynomial time and is widely
applicable. The algorithm that we give for this special case has
been implemented and is used in the current version of the PolicyMaker