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

Intersection of tag fields


When performing reduction of certificate chains, one needs to perform
intersection of the tags in the chain.  What are the rules for this?
Here is a sketch of a proposal that is more specific than what is said in
3.4.1--3.4.3 of the draft.  This sketch needs a little bit of elaboration
to be complete.

Recall that a tag item is an object of the form
	( tag 
         ( t c1 c2 ... ck  ) )
where t is some specific tag-name like "ftp" or "spend" and the
constraints c1 ... ck specify further conditions.  

Also recall that ( tag ) specifies no constraint so that there is no
problem in intersecting a tag field of this type with any other tag, since
it is the identity for this intersection operation.

We introduce some special syntax to talk about sets of byte strings.  This
has the form ( * order-type arg1 ... argn ). For example:

	( * strings-with-prefix "http://a.com/" )

        ( * dates-in-range 1996-01-01 1996-12-31 )

        ( * numbers-in-range 1 499 )

        ( * alphabetic-in-range a zzzzzzzzzzzzzzzzzzz )

(here the ranges are inclusive of the end-points).  We may want other
order-types, even one defined by a program.

These * values may appear in tags as in
	( tag ( http ( * strings-with-prefix "http://a.com/" ) billg ) )

Intersecting two tags then means:
	-- checking that the tag types are the same
	-- producing a new output tag with the same type as the
           input tags.
	-- making sure the output tag has one element corresponding
           to each element of the first list, and one element corresponding
           to each element of the second list. The same element in the
           output may correspond to one element in each input list.  
           This matching may be based on position, or on sub-object types.
           (This part needs elaboration, but basically, we are ensuring
           that no constraint gets lost, and constraints are combined
           when they can be.)
	-- Constraints are combined recursively by the same algorithm
           that combines tags.
	-- Two *-type lists can be combined if they have the same
           order type.  (e.g. two date-ranges can be combined, or
           two strings-with-prefix can be combined.)  If such a
           combination yields an empty set, the intersection of the two
           tags fails.  A byte string can also be combined with a *-type list
           if it is a member of the set the *-list denotes, e.g.
		45 intersected with ( * numbers-in-range 1 499 ) is just 45 
	-- Otherwise two byte strings can be combined if they are equal.

This is the basic idea for handling the cases sketched in 3.4.1--3.4.3. 

Example:
tag T1 = ( tag ( spend 
                 ( account citicorp 123456 ) 
                 ( date ( * date-range 1996-01-01 1997-12-31 ) )
                 ( value ( * number-in-range 0 9999 ) )
               ) )
tag T2 = ( tag ( spend                                   
                 ( date 1996-08-07 )
                 ( value ( * number-in-range 100 1000000 ) ) ) )
when intersected yield
	 ( tag ( spend
                 ( account citicorp 123456 ) 
                 ( date 1996-08-07 )
                 ( value ( * number-in-range 100 9999 ) ) ) )

A bit further thought needs to go into the constraint matching process, since
we can have a mix of positional arguments and key-word-introduced subobjects.
Probably we need some more discpline here to make this work out smoothly, such
as using no positional parameters (unless there is only one parameter).

Ron Rivest
Follow-Ups: