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

*-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
    indications, and feels awkward to design into the specifications.
  
(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
           restrictions (forget about "cleanliness")
	-- forget about trying to index into each *-set (this is too
           awkward)
	-- instead, think about howw certificate chains are used.  Normally,
           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
	   but instead do
		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: