# *-forms and "cleanliness"

```
There is a bit of a conflict between expressive tag-lists (or *-sets), and
efficient intersection.  Let me begin with an example.  If we have tags

T1 = (* set (f a (*)) (f b (*)) (f c (*)) (f d (*)))

T2 = (* set (f (*) w) (f (*) x) (f (*) y) (f (*) z))

Then their intersection is the cross-product, since every element of T1's
*-set matches with every one of T2's, yielding:

intersect(T1,T2) = (* set (f a w) (f a x) (f a y) (f a z)
(f b w) (f b x) (f b y) (f b z)
(f c w) (f c x) (f c y) (f c z)
(f d w) (f d x) (f d y) (f d z) )

It is easy to construct examples where the intersection of n *-sets has
size exponential in n.  (Also, while the above intersection can also
be represented as

(* set (f (* set a b c d) (* set w x y z)))

you can't always get it to factor so nicely.  For example, if you double-up
with each argument

T1 = (* set (f a a (*) (*))
(f b b (*) (*))
(f c c (*) (*))
(f d d (*) (*)))

and similarly for T2.

Having exponential blow-ups when computing the reduction of a certificate
chain is, in my opinion, a bad thing.  I think we have the following choices:

(1) Just accept it, and let the chips fall where they may.  It probably
won't happen too much anyway.  But you will need some policy on what
to do when it happens.

(2) Restrict the *-forms so this can't happen.  For example, it is not
hard to make a restriction so that you don't get the cross-product
behavior.

Define a *-set to be "clean" if it contains no repeated objects of
the same type.  Intersecting two "clean" *-sets is then easy, since
an object in one *-set can match with at most one object in the
other *-set when you form the intersection.

The drawback with "cleanliness" is that it limits expressiveness,
especially if you want to use *-set for general lists of tags, as
in
(*-set (access door-1 weekdays)
(access door-2 weekends))
This feels natural, but is not "clean".  So maybe some other
construction ("tag-lists") can be used for non-clean lists of
tags...

(3) The third approach is to require that a certificate chain that contains
a *-set must indicate, for each such *-set, what element of that
*-set is intended.  This requires additional mechanism for such

(4) Same as approach (3), but only require such indications for non-clean
*-sets.

(5) Same as approach (1), but offer the user an option to give such
indications as needed to keep the computation within reasonable bounds

(6) Tony Bartoletti's construction, which seems complex to me, and seems
to require that you can only grant authority AFTER you have received
some (possibly larger) authority.  I need to study his idea a bit
more, but I am concerned by its complexity.

(7) Here is what I think is the right approach:
-- allow *-sets and other *-forms to be written without any
-- forget about trying to index into each *-set (this is too
awkward)
a user presents such a chain to a server to justify some
request.  The request takes the form of a tag that matches
the intersection of the tags in the chain.  The request itself
is normally *-free.
-- the key idea is to have the request available when working
with the chain.  That is, do NOT do
(1) compute the intersection of the chain
(2) see if the intersection supports the request
use the request to prune the intersection possibilities
as you go along.
Note that this happens naturally if the request is already
an element of the chain, which is how SPKI normally thinks
of it.  In the above example, if the request is
(f a z)
then intersecting it with each element of the certificate
chain in turn gives (f a z) as the intersection.  And in
general, this sort of thing holds up:
if the request is *-free (as you would expect), then
processing a certificate chain with respect to (or
including) a request is very easy to do.

The only thing that gets expensive is trying to compute the
meaning (intersection) of a chain in the absence of any specific
request.  But computing such meanings ahead of time is only
undertaken for efficiency reasons anyway, and so if it is not
efficient, don't do it (just keep the chain itself around as
its meaning).

Summary: let's allow arbitrary *-forms, and only compute the
intersection of certificate chains when either
(a) at least one element of the chain is *-free, or
(b) the result is otherwise seen to be manageable in size.

Ron Rivest

```

Follow-Ups: