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

*-forms in tags

After some discussion with Carl Ellison, we have converged on a model
for *-forms in tags that seems to capture the variability one wants
for intersection of tags. Jump to the end of this note to see an

Here is the development:

(1) When composing certificate chains, the tag fields will be 
    automatically intersected by a standard intersection algorithm.
    The user will not have to specify a new intersection algorithm, but
    he will have to write his tags in such a way that the standard  
    algorithm will give the desired behavior.

(2) The tags may contain *-forms: lists of type * , as in (* ... )
    An S-expression that does not contain any *-forms (at any level) will
    be called a "constant" S-expression.  S-expressions that contain (or are)
    *-forms (at any level) are called "variable" S-expressions.

(3) The standard intersection algorithm matches constant S-expressions with
    an equality test.  That is, if T1 and T2 are two constant S-exressions,
    then their intersection is T1 if T1 = T2.  If T1 is not equal to T2, then
    the intersection is not defined.

(4) A variable S-expression is understood to represent a SET of constant
    If s is an S-expression, we might denote the set of constant S-expressions
    it denotes as val(s).
    If s is a constant S-expression, than val(s) = { s }.  Just the singleton
    set containing s.

(5) The standard intersection algorithm takes two S-expressions 
    s1 and s2, and produces, if possible, an S-expression s3 such that
	val(s3) = set-intersection(val(s1),val(s2))
    Note that this is consistent with our definition for constant 
    S-expressions.  If it is impossible to compute a suitable variable
    S-expression s3, then the intersection fails and is undefined.  This
    may happen because the *-forms aren't expressive enough to represent
    the resulting set of S-expressions, even though that result is (always) 
(6) If s is a list (s1 s2 s3 ... sk) that is not a *-form, then
	val(s) = cross-product(val(s1),val(s2),...,val(sk))
    That is, the set of lists obtained by taking a constant S-expression
    from val(s1), followed by a constant S-expression from val(s2), and
    so on.  This means that the standard intersection operator can
    work recursively.  

(7) (Elaboration) Let A(s,s') denote the S-expression (if any)
    resulting from taking the intersection of S-expressions s and s'
    by the standard algorithm.  
	If s  = (s1, s2, ...,sk )
        and s'= (s1',s2',...,sk')
    are two S-expressions that are not *-forms, then
	A(s,s') = (A(s1,s1'),A(s2,s2'),...,A(sk,sk'))

(8) [* set form]  Here is the first (of several) *-forms
	s = (* set s1 s2 ... sk )
    We now define
	val(s) = set-union(val(s1),val(s2),...,val(sk))
    Also a singleton set has the same val as the string itself:
	val( (* set 45) ) = val( 45 ) = { 45 }

(9) [example]
    We might have a tag of the form
	T1 = (tag (spend-from 45123))
    Here 45123 is intended to denote an account number at the bank.
    As written, this can only be matched with an exact copy.  

    Consider now the variable S-exression of the form
	T2 = (tag (spend-from (* set 45123 11112)))
    This is intended to denote an authorization to spend from either 
    account 45123 or account 11112.

    Note that Alice can delegate to Bob the authority to spend from
    either account using tag T2, and Bob can delegate to Charles the ability 
    to spend from account 45123 only using tag T1, and this will work
    properly automatically, since
	A(T1,T2) = T1
	A(tag,tag) = tag
	A(spend-from,spend-from) = spend-from
	A(45123,(* set 45123 11112)) = 45123

(10) [Matching two *-forms]
     If Alice delegates to Bob with
	T2 = (tag (spend-from (* set 45123 11112)))
     and Bob delegates to Charles with
	T2 = (tag (spend-from (* set 11112 66632)))
     then Charles may spend from 11112, since
	A(T1,T2) = (tag (spend-from 11112))

(11) Basically, you can use the (* set ...) form to represent some variability
     in the authorization that can be refined by other issuers in the
     certificate chain.

(12) There are other *-forms for representing other kinds of variability.
     Each such *-form always represents a set of S-expressions, and there
     a special rule for determining what that set is.  The format of 
     a *-form is always 
	( * <star-type> <arguments>)
     The rule for specifying what set of S-expressions this represents
     implies how to intersect the *-form with another S-expression
     (including another *-form).

(13) Here are two simple *-forms representing sets of byte strings:

     (* prefix "string")        -- represents the set of byte strings 
	                           having "string" as its prefix.
	Example of use:
		T1 = (tag (http (* prefix "http://abc.com/")))
        This can be automatically intersected with    
		T2 = (tag (http (* prefix "http://abc.com/accounting")))
        to yield
		T2 = (tag (http (* prefix "http://abc.com/accounting")))

     (* range <order> <lower-limit>? <upper-limit>? )
	where <order> is one of "alpha" or "numeric" 
	and <lower-limit> ::= (<ge-or-geq> <byte-string>)
            <ge-or-geq> ::= ">" | ">="
            <upper-limit> ::= (<le-or-leq> <byte-string>)
            <le-or-leq> ::= "<" | "<="
	Example of use:
		T1 = (tag (spend-amount (* range numeric (< 5000))))
                to authorize someone to spend up to 5000 dollars.

        	T2 = (tag (login-permission
			    (* range alpha (<= 1996-01-01)(<= 1997-12-31)))))
                (using the fact that dates compare nicely as alpha strings).

(14) Here are four forms for representing sets of lists:

     ( * append s )	-- represents all S-expressions that can be obtained
	                   by appending additional elements to the end of 
                           list s.  This is like "prefix", except for lists.
	T1 =  ( tag ( * append ( ftp "abc.com" )))
  	allows there to be additional elements in the ftp list.

     ( * reorder s )
     ( * reorder-insert s )
     ( * reorder-delete s )
	These represent the set of S-expressions you can get from s by
        re-ordering the elements of s (other than the first) and possibily
        inserting new elements, or deleting some elements (other than the

	For example, (* reorder (rsa (n &44)(e &33))) allows the n and e
        fields to be given in either order. 

	Or, (* reorder-insert (a (b 4)(c 5))) will match with 
		(a d (c 5) e f (g 23) (b 4))

        The reorder capability is good when the elements of the list are
        indexed by keywords or list type, rather than by position.

        For these two options, the list s must have no *-forms at its top
        level, and any top-level sublists of s must have a byte-string as
        its first element.  Also, there must be no repeated byte-strings
        at the top level, and no repeated top-level sublists having the
        same name (first element).  This must also be true of anything
        matching these *-forms.  These restrictions allow the intersection
        algorithm to easily figure out which elements of s match up with
        which elements of s' when computing A(s,s').

(15) It is possible to recursively work out the intersections then
     for tags in an automatic manner.  For example, the intersection
	(tag (spend (amount (* range numeric (< 5000)))
                    (account (* set 12345 67890))
 	            (* reorder-insert (for socks shirt pants))
		    (date (* range alpha (>= 1997-01-01)))))
     intersects with
	(tag (spend (amount (* range numeric (< 1000)))
                    (account (* set 87654 12345))
 	            (for tie pants socks belt shirt)
		    (date (* range alpha (< 1998-01-01)))))
     to produce
	(tag (spend (amount (* range numeric (< 1000)))
                    (account 12345)
 	            (for tie pants socks belt shirt)
		    (date (* range alpha (< 1997-01-01)(>= 1998-01-01)))))
Ron Rivest