Subject: [MSEC] A basic question about LKH

From: "QinKe" <[email-masked]>
Date: Fri, 26 Aug 2005 12:16:39 +0800

Dear folks:

I have some basic questions about this figure LKH which exists in many theises about secure multicast:

                                 k
                                 |
                 +---------------+---------------+
                 |                               |
               k_(1-4)                        k_(5-8)
                 |                               |
        +--------+------+                 +------+-----+
        |               |                 |            |
       k_(1-2)         k_(3-4)          k_(5-6)      k_(7-8)
        |               |                 |            |
  +-----+-----+     +---+---+        +----+----+   +---+----+
  |           |     |       |        |         |   |        |
  k1          k2    k3      k4       k5        k6  k7       k8

The authors described the process of a new member's addition or a current member's eviction. 
What I'd like to know is that if the tree is a complete binary tree, then where will the GC set member 9? Like this?

                 ......      
                   |        
             +-----+-----+   
             |           |    
             k1          k2
             |
          +--+
          |
          k9

But we can't make such an assumption that member 1 provides forwarding service.           
Therefore, the tree is really a binary tree? If not, the re-keying messages must be different from that of binary tree. I fell into confusion...

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

---

From: Mark Baugher <[email-masked]>
Date: Thu, 25 Aug 2005 23:55:48 -0700

hi,
   LKH does not specify the tree type or balancing algorithms.  RFC 2627 
does not specify that the tree needs to be balanced or binary.  
Standard algorithms for adding and removing nodes to a tree such as a 
binary tree, balancing a tree, etc. can be used.  RFC 2627 does specify 
what needs to be done when a path changes from the root to a leaf such 
as when a node is added to the tree or removed from the tree for the 
purposes of adding a leaf, removing a leaf or balancing the tree.  The 
GC must send the updated keys to the leaves that are in the affected 
subtree.  From p. 14 of 2627:
"...Starting with those nodes all of whose children
    are leaves and proceeding towards the root, the server transmits the
    key for each node, encrypted using the keys for each of that node's
    children."

I modified your diagram below to show one way of adding a leaf, k9 by 
giving k7, k8 and k9 a new common ancestor.  In order to make this 
change, two keys are sent to k7, k8, k9.  One key is k_(7-9) encrypted 
with k_(7-8) and the second key is k_(7-9) encrypted with k_(9).

The point is, however, that whatever algorithm is use for the tree is 
internal to the GC and not specified by RFC 2627.

Mark
On Aug 25, 2005, at 9:16 PM, QinKe wrote:

>                k_(1-4)                        k_(5-8) +-----+
>         +--------+------+                 +------+----+    k_(7-9)
>         |               |                 |            +-----+----+
>        k_(1-2)         k_(3-4)          k_(5-6)      k_(7-8)    k_(9)
>         |               |                 |            |          |
>   +-----+-----+     +---+---+        +----+----+   +---+----+     +
>   |           |     |       |        |         |   |        |     |
>   k1          k2    k3      k4       k5        k6  k7       k8   k9
>
> What I'd like to know is that if the tree is a complete binary tree, 
> then where will the GC set member 9? Like this?
>
>                  ......
>                    |
>              +-----+-----+
>              |           |
>              k1          k2
>              |
>           +--+
>           |
>           k9
>
> Therefore, the tree is really a binary tree? If not, the re-keying 
> messages must be different from that of binary tree. I fell into 
> confusion...
>
>