Cryptography Reference
In-Depth Information
2
l
k
X
X
(log n−l) + (r−2
k
)(log n−k−1) − (r−1) =
log n +
l=1
i=2
l−1
+1
k
X
2
l−1
(log n−l) + (r−2
k
)(log n−k−1) − (r−1)
= log n +
l=1
Now based on the identities
P
l=1
2
l−1
= 2
k
− 1 and
P
l=1
l2
l−1
= (k +
1)2
k
−2
k+1
+ 1 we simplify the expression to
2
k
log n− (k−1)2
k
−r + (r−2
k
)(log n−k−1)
After the calculations and using the fact k > log r−1 we get
r log n−r(k + 1) + 2
k+1
−r ≤ r log n−r(k + 2) + 2r ≤ r(log n− log r + 1)
This completes the proof.
A direct revocation algorithm.
We will next discuss a direct revocation algorithm for the CS method that
has the same performance as the generic algorithm that is inherited due to
factorizability. Given a set of users R to be revoked, the broadcast pattern that
covers [n]\R can be determined by computing first the Steiner tree Steiner(R).
Recall that the Steiner tree is the minimal subtree of the full binary tree that
connects all the leaves in R. Consider now the nodes that are “hanging” from
the tree Steiner(R). Assume there are m such nodes corresponding to the
subsets S
1
,S
2
,...,S
m
. We say a node is hanging from the Steiner tree if its
sibling is in the Steiner tree while itself is not. See Figure
2.10
for the hanging
nodes for a simple revocation instance in the case of 16 users; ; the nodes
hanging from the Steiner Tree constitute the broadcast pattern. It holds that
[n] \ R = ∪
i=1
S
i
; indeed for any i ∈ {1,...,m}, S
i
would not contain any
revoked user. On the other hand, if u ∈ R then, there exists some node S
that is on the path from u to the root of the binary tree and hangs from the
Steiner tree. It follows that the broadcast pattern that is revoking R would be
{S
1
,...,S
m
}. The transmission overhead of the broadcast encryption scheme
that is using the CS as the underlying set system would be upper-bounded
by the number of inner nodes in the Steiner tree Steiner(R). An analysis on
the number of nodes in a Steiner tree with |R| = r leaves would yield a
transmission overhead of size r log(n/r). We argue about this next.
Theorem 2.40. The size of the broadcast pattern output resulting from the
revocation algorithm outlined above is at most r log(n/r) where 0 < r < n is
the size of the revoked set R.
