These are the slides I presented at the 41st IETF.

Matt

# A New (sequence ) Structure

{rivest,elien,fredette,morcos}@theory.lcs.mit.edu
• The current sequence structure does not represent all cert chains efficiently, and does not handle threshold subjects well.
• We propose a new (sequence ) structure and give examples.

# (sequence ) Name Problems

• When the same name is used more than once in a sequence, the certs to reduce it must be included more than once.
Example:
```K1         => K1 bob friends friends
K1 bob     => K2
K2 friends => K3
K3 friends => K1 bob friends parents
K1 bob     => K2
K2 friends => K3
K3 parents => K4
```

# Named Subsequences

• We now allow sequences to define and reference named subsequences.
Example:
```(sequence
(def S1 (sequence (cert (issuer K1) (subject K2))
(cert (issuer K2) (subject K3))))
(cert (issuer K0) (subject K1))
(ref S1)
(cert (issuer K3) (subject K4)))
```

# New (sequence ) Grammar

```<new-seq-ent>:: <seq-ent> | <seq-def> | <seq-ref> ;

<seq-def>:: "(" "def" <seq-def-name> <seq-def-value> ")" ;
<seq-def-name>:: <hash> | <byte-string> ;
<seq-def-value>:: <pub-key> | <cert> | <sequence> ;

<seq-ref>:: "(" "ref" <seq-def-name> ")" ;
```
• Subsequence definitions can nest.
• Subsequence names have lexical scope.
• Use of a subsequence name references the most recent completed sequence with that name.

# (sequence ) k-of-n Problems

• The (do k-of-n) framework in the draft requires that all thresholds converge on a single simple subject.
• But the draft says that requests may be multiply signed, and that thresholds may leave authority divided, for sharing.
• The draft also allows for nested threshold subjects in certs.

# (process-threshold )

• We use named subsequences to reduce the members of a threshold subject.
• There are two reserved subsequence names. kill removes a subject from a threshold, and keep specifies "no change".
Example:
```(sequence
(def S1 (cert (issuer K2) (subject K3)))
(def S1 (cert (issuer K4) (subject K3)))
(cert (issuer K0) (subject (k-of-n 3 4 K1 K2 K3 K4)))
(process-threshold kill S1 keep S2))
```

# New (sequence ) Grammar, II

```<new-seq-ent>:: <seq-ent> | <seq-def> | <seq-ref> | <proc-t> ;

<proc-t>:: "(" "process-threshold" <proc-t-ent>* ")" ;
<proc-t-ent>:: <proc-t> | <seq-def-name> ;
```
• Whenever the currently reduced subject is a k-of-n, (process-threshold ) must be used, with the names of n subsequences, to reduce the threshold members.

# Miscellaneous

• We eliminate (do hash); instead, use (def ) to name an object with its hash:
```(sequence
(def (hash md5 |abcdef==|) (public-key (...)))
(cert (issuer (hash md5 |abcdef==|))
(subject (...)))
...)
```
• This consolidates naming mechanisms and makes for more readable sequences.

April 6, 1998
fredette@theory.lcs.mit.edu