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

From: "Dalit Naor" <[email-masked]>
Date: Sun, 14 Oct 2001 11:23:08 +0300

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*******

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