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

*To*: spki@c2.net*Subject*: *-forms and "cleanliness"*From*: rivest@theory.lcs.mit.edu (Ron Rivest)*Date*: Fri, 04 Apr 97 22:39:27 EST*Cc*: blampson@microsoft.com*Sender*: owner-spki@c2.net

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

**Re: *-forms and "cleanliness"***From*: Carl Ellison <cme@cybercash.com>

- Prev by Date:
**Re: Bignums** - Next by Date:
***-forms** - Prev by thread:
**Re: Endian orders** - Next by thread:
**Re: *-forms and "cleanliness"** - Index(es):