Computational complexity of delegation

[Erik Rissanen <mirty@sics.se>]

All,

As I mentioned earlier, Olav Bandman has shown that delegation with
IndirectDelegatesCondition is NP-complete since it reduces to 3-SAT.
Here is my promised explanation of his proof. It is not very formal or
rigorously written.

In 3-SAT we ask whether a logical expression of the form

(x11 OR x12 OR x13) AND
(x21 OR x22 OR x23) AND
(x31 OR x32 OR x33) AND ...

where xij is a variable or a negation of a variable, can be made true
by at least one assignment of the variables. See
http://en.wikipedia.org/wiki/3-SAT for more on 3-SAT and some
examples.

Given an instance of the 3-SAT problem, we generate policies as
follows:

Let there be an access situation A. (The details do not matter.)

For each variable in the problem instance, Vk, define two attribute
identifiers TVk and FVk, of arbitrary type and value. (These will be
used to constrain delegation based on variable assignment in the 3-SAT
instance.)

Let there be 3*N issuers, Iij, where N is the number of disjunctive
clauses, in the problem instance. Define a unique issuer id attribute,
UIij, for each of them.

The attributes of issuer Iij are:

UIij, and all of TVk and FVk, except FVk, if Vk is present in xij in
non-negated form, and TVk if Vk is present in xij in negated form.

(When performing reduction, the presence of Iij on the path
corresponds to a variable assignment which makes xij true. The
attributes TVk and FVk corresponds to the assignments which do not
conflict with the assignment corresponding to this issuer. For
instance, if a given issuer corresponds to the assignment V3=true, then
we do not include attribute FV3, since assigning V3 to false would be
in conflict with this assigment.)

For the first disjunctive clause, (x11 OR x12 OR x13), write three
access policies with issuers I11, I12, and I13, where each policy
grants access to A.

For each additional clause, (xi1 OR xi2 OR xi3), write three
delegation policies with issuers Ii1, Ii2, and Ii3, where each policy
delegates the situation A, and issuers I(i-1)1, I(i-1)2, or I(i-1)3 as
delegates, based on their unique ids. (That is, the policy grants
delegation rights to all three of these issuers' unique id
attributes.)

Also, each delegation policy contains an
IndirectDelegatesCondition. If Vk is in xij non-negated, then there is
an IndirectDelegationsCondition on attribute TVk and if Vk is in xij
in negated form, then there is an IndirectDelegatesCondition on
attribute FVk. This condition in the indirect delegates condition is
also present in the conditions on the direct delegate.

(The indirect delegates condition requires that all issuers on the
reduction path correspond to assignments which do not conflict with
the assignment made by this policy.)

Finally, there is a single trusted policy, which grants delegation
rights for situation A to the issuers IN1, IN2, and IN3.

All policies contain a single rule with an open target and a Permit
effect. All policies are collected into a single policy set with a
permit overrides policy combining algorithm.

Now, request access to A. If the access is granted with a Permit, then
this is equivalent with that there is at least one way to satisfy the
3-SAT instance.

"Proof":

First part: Access is granted -> 3-SAT instance can be satisfied.

Since the access is permitted, there is a reduction path to the
trusted policy. Because of the way the policies are constructed, a
path to the trusted policy will go through one of the issuers Ii1, Ii2
or Ii3, for each i in 1...N. Each such reduction step corresponds to a
variable assignment in which xi1, xi2 or xi3 is made true.

The issuer attributes TVk and FVk define which assignments are not in
conflict with the assignment that a given issuer corresponds to. The
conditions on delegates and indirect delegates in a given policy makes
sure that no conflicting assignment has been made on the reduction
path. If during redution we reach a policy which corresponds to an
assignment which conflicts to a previous assignment made on the path,
the indirect delegates condition will stop the path. If we reach the
trusted policy, we have found assignments which satisfy each clause,
without conflicts.

Second part: 3-SAT instance can be satisfied -> Access is granted

Since the 3-SAT instance can be satisified, we can find a reduction
path to the trusted policy if we in each clause choose to reduce
through an xij which is true. If the path would not be valid, it would
mean that there is an condition on delegates which conflicts with one
of the issuers on the path. Due to the nature of the policies, this
would imply that for some Vk, both Vk and ~Vk would be true, which is
contrary to the assumption that the 3-SAT instance can be satisfied.

Q.E.D.

Example:

3-SAT instance:

(B OR C OR D) AND (~B OR ~C OR E)

The policies become (in shorthand):

P11:
  Issuer: UI11, TB, TC, FC, TD, FD, TE, FE
  Access situation:  A

P12:
  Issuer: UI12, TB, FB, TC, TD, FD, TE, FE
  Access situation:  A

P13:
  Issuer: UI13, TB, FB, TC, FC, TD, TE, FE
  Access situation:  A

P21:
  Issuer: UI21, FB, TC, FC, TD, FD, TE, FE
  Delegates:
      UI11, FB
      UI12, FB
      UI13, FB
  IndirectDelegates: FB
  Access situation:  A

P22:
  Issuer: UI22, TB, FB, FC, TD, FD, TE, FE
  Delegates:
      UI11, FC
      UI12, FC
      UI13, FC
  IndirectDelegates: FC
  Access situation:  A

P23:
  Issuer: UI23, TB, FB, TC, FC, TD, FD, TE
  Delegates:
      UI11, TE
      UI12, TE
      UI13, TE
  IndirectDelegates: TE
  Access situation:  A

PTrusted:
  Delegates:
      UI21
      UI22
      UI23
  Access situation:  A

We can find for instance path P11, P23 to the trusted policy. P23
supports P11 since the attributes U11 and TB are present in the issuer
of P11. The trusted policy supports P23 since UI23 is present in the
issuer of P23.