Subject: [MSEC] Re: draft-irtf-smug-subsetdifference-00.txt

From: Mark Baugher <[email-masked]>
Date: Tue, 23 Oct 2001 12:57:22 -0700

Dalit
   We are a bit late in posting information from the London meeting on our 
smug (now gsec) website as it is "under new management."  We should get it 
posted soon.

thanks, Mark
At 11:23 AM 10/14/2001 +0300, Dalit Naor wrote:

>Below are my remarks on Mark's comments regarding our I-D. The attachment
>has been deleted as I hope it appears on the site soon (will be glad to
>send it to whoever is interested).
>Further comments are welcome.
>
>Regards, Dalit.
>
>---------------------- Forwarded by Dalit Naor/Haifa/IBM on 10/14/2001
>10:12 AM ---------------------------
>
>
>
>
>
>Dalit Naor
>10/11/2001 03:45 PM
>
>
>To:   [email-masked]
>cc:   Jeff Lotspiech/Almaden/IBM@IBMUS, [email-masked], Jeffry
>       Ullman/Fort Lauderdale/IBM@IBMUS
>
>From: Dalit Naor/Haifa/IBM@IBMIL
>Subject:  Re: draft-irtf-smug-subsetdifference-00.txt
>Importance:    Normal
>
>
>
>Mark,
>
>Thanks for your useful comments, both on the algorithm and on the
>exposition in the I-D.
>
>I will do my best to incorporate your suggestions (or any others, if any
>arrive) into the next revision, and make it more self-contained. Since the
>algorithm has been completely implemented and its specs have been written,
>I believe I can also include implementation details in the next round.  For
>now, I am attaching a pdf file that contains slides presented  by Ran
>Canetti at the IRTF meeting in London. I believe these pictures and
>diagrams are quite useful for understanding the algorithm's details. Is it
>possible to post it on the  SMuG site?
>
>As for your concern regarding the size of the tree, you are correct. It
>should be as large as the maximum number of users throughout the lifetime
>of the system.  However, how large can this be? let's take a numeric
>example. For the total of 4B users you need a tree of depth 32, requiring a
>user to store about 500 keys. A further optimization can be done that
>requires a user to store only about 300 (for the same number of users)  and
>adding at most 64 more keys to the message size. I recently looked at a
>paper "Comparison of Hierarchical Key Distribution Schemes", by Dondeti,
>Mukherjee and Samal, which looked at real-life  benchmarks for group
>memberships. As for as I can tell, the total number of users was not
>reported explicitly, but the numbers didn't get to the billions. Do you
>have any concrete examples?
>
>Finally please note that my email address has been changed and is now
>[email-masked]
>
>Below is the attached presentation.
>
>Regards, Dalit.
>
>
>
>
>
>
>Mark Baugher <[email-masked]> on 10/05/2001 02:13:12 AM
>
>To:   Jeff Lotspiech/Almaden/IBM@IBMUS, Dalit Naor/Almaden/IBM@IBMUS
>cc:   [email-masked], [email-masked],
>       [email-masked]
>Subject:  draft-irtf-smug-subsetdifference-00.txt
>
>
>
>Jeff, Dalit
>      I think
>http://search.ietf.org/internet-drafts/draft-irtf-smug-subsetdifference-00.txt
>
>is a very important draft on key revocation.  Thanks for submitting
>it.  Anyone considering LKH or a similar type of algorithm should study
>subset difference.  We should ask if there's any reason to use LKH or LKH+
>given subset difference, which does not require a receiver to keep a
>history of membership changes as LKH-style algorithms do.  The only issue
>that comes to my mind is the larger amount of initial state.  I'll come
>back to that at the end of this note.
>
>      I hope interested people take the time to read your I-D.  In addition
>to copying smug (now gsec) your draft is of interest to other groups.  It's
>of interest to the Internet Digital Rights Management research group
>because this algorithm spans both network and removable-media delivery of
>keying material, which is used in various copy protection schemes.  In
>addition to IDRM, I also am copying IETF msec, which is developing key
>management protocols that incorporate key revocation such as LKH+.
>
>      The subset-difference I-D took me a lot of time to read compared to,
>say, LKH, and I found it necessary to also read
>http://www.wisdom.weizmann.ac.il/~naor/PAPERS/2nl.html.  I don't think we
>need proofs in the I-D, a well-reviewed paper should suffice, but I needed
>the explanation and examples from the longer work (Revocation and Traitor
>Tracing Schemes for Stateless Receivers - 2nl.html) to understand what
>you're describing in the I-D.  If this work is to become the basis for
>standards such as a key revocation algorithm used by an MSEC key management
>protocol, it should be more accessible and self-contained, in my
>opinion.  For example, "Steiner Trees" is used in the I-D but is not
>defined; a crisp definition of how this concept is being applied would
>help.   I hope the next version of your draft can help the implementer by
>providing the detail to put the algorithm into code and validate
>correctness.
>
>    I found the word "stateless" to be misleading since the first step to
>initialize a member is to install state in the form of keys.  "Static
>state" seems to be more descriptive than "stateless."  I was a bit
>mystified in the beginning in trying to understand the process of adding
>members, which is not described for good reason:  The initial tree is as
>large as it will ever be.  Every new member has a label in the tree, or one
>can be created on demand as you describe.  But the tree gets no larger,
>does it?  I am persuaded by your arguments that this inefficiency is
>probably not great since labels and keys can be dynamically generated in a
>Group Controller/Key Server.  But we do commit to more space at the
>receiver than the LKH-style key revocation.  This is the only downside I
>see at present wrt LKH.
>
>Mark
>
>
>
>
>
>*******Attachment(s) have been removed*******
>
>
>---------------------------------------------------
>---------------------------------------------------
>CONTRIBUTIONS: Mail to [email-masked]
>UNSUBSCRIBE: Send "unsubscribe smug"  to [email-masked]
>PROBLEMS: Report to [email-masked]
>TO SUBSCRIBE: Send "subscribe smug" to [email-masked]

_______________________________________________
msec mailing list
[email-masked]
http://www.pairlist.net/mailman/listinfo/msec