Cryptography Reference
In-Depth Information
Fig. 2.10. Steiner tree that is connecting the revoked leaves.
Proof. Observe that the number of subsets hanging from the Steiner Tree
Steiner(R) is exactly the number of nodes in Steiner(R) that have degree 1.
We will now prove the above claim by induction on the height of the tree, i.e.
induction on log n.
Base Case log n = 1: This case corresponds to a set system with two users
only, and the claim can be easily seen to hold for any r, r = 1,2.
Induction Assumption for log n = s: Suppose that the number of subsets
hanging from the Steiner Tree Steiner(R) is at most r(s−log r) for any subset
R ⊆ N with |R| = r and 0 < r < n.
Induction Step for log n = s+1: We have two cases: either all the revoked
users are located on the same subtree of one of the children of the root, or
r = r 1 + r 2 so that r 1 users are located on the left child of the root, and r 2
users are located on the right child.
In the first case, due to induction assumption, Steiner(R) would yield at
most r(s−log r)+1 nodes of degree 1, where the extra node is because of the
root, and the remaining are within the child contains all revoked users. The
induction step is proven in this case since r(s− log r) + 1 ≤ r(s + 1− log r).
In the second case, due to the induction assumption Steiner(R) would yield
at most r 1 (s− log r 1 ) + r 2 (s− log r 2 ) nodes of degree 1.
r 1 (s− log r 1 ) + r 2 (s− log r 2 ) = rs− (r 1 log r 1 + r 2 log r 2 )
≤ rs− (−r + r log r)
= r(s + 1) −r log r
= r(s + 1− log r)
The above, indeed, holds, since it holds that r(log r − 1) ≤ r 1 log r 1 +
r 2 log r 2 for any possible r,r 1 ,r 2 with r = r 1 + r 2 .
 
Search WWH ::




Custom Search