Cryptography Reference
In-Depth Information
upper bound for the transmission overhead by providing an upper bound on
the size of the lower-maximal partition of I∩P u for any ideal I and atom u of
Φ in terms of the size of ideal I.
Theorem 2.36. Suppose that a fully-exclusive set system Φ over [n] is factor-
izable. If for any subset S ∈ Φ and an atom u, it holds that ord((S)∩P u ) ≤ f
then for any ` 1 ,...,` r ∈ [n], ord(∩ i=1 P ` i ) ≤ r(f −1) + 1.
Proof. Theorem 2.36 We consider the successive chopping of filters F ` 1 ,...,F ` r
from Φ. Given the factorizability of the family, each chopping operation applies
to a specific ideal in the lower-maximal partition. Initially this ideal is Φ, in
the second step it is one of the ideals of P ` 1 and so on. Given that ord((S) ∩
P u ) ≤ f for any S ∈ Φ, we have that at each successive chopping, the ideal
that is selected will be removed from the list and at most f ideals would
be added. Thus, the total number of ideals at the end will be bounded by
f + (r−1)(f −1) = r·f −r + 1.
2.5 Constructions
In this section we present a series of constructions of broadcast encryption
schemes in the key poset framework. In each case we give first a combinatorial
description and then we provide the key poset description.
2.5.1 Complete Subtree
The Complete Subtree (CS) is a method that defines a set system over a
binary tree where the users are located on the leaves of the tree, and any
intermediate node defines a subset in the set system which contains the users
placed on the leaves rooted at this node. It is assumed that the number of
users n is a power of 2. In this way a set system Φ CS is defined over a user
population [n] = {1,...,n} that consists of 2n−1 subsets each corresponding
to a node in the full binary tree with n leaves.
Set system description in the KP framework.
We next provide the description of the complete subtree method in the key
poset framework. Let J CS be the set of encodings of subsets in the set system
Φ CS defined over the set N = {1,...,n}. Recall that for simplicity, we assume
that log n is an integer.
An encoding j ∈J CS is a binary string of length at most log n. Each such
encoding corresponds to an index of a node in a full binary tree where the
indices are constructed in a top-down manner: the root of the binary tree is
encoded by (the empty string by ), an index of a left child is constructed by
appending '0' to its parent index, while an index of a right child is constructed
by appending '1' to its parent index.
 
 
Search WWH ::




Custom Search