Cryptography Reference
In-Depth Information
Definition 2.18. A collection of families Φ parameterized by n is defined by
six algorithms (tst,mbr,slo,sbs,cvr,spt) and a constant cvm, a finite al-
phabet and a length function l(·). Each element of Φ is encoded over the alpha-
bet with length of at most l(n) where n is the number of users, and we denote
the set of encodings by J. Below the input s is thought to be a string of length
at most l(N). The algorithms are defined as follows.
1. tst: (Encoding Testing); given s, returns 1 if s is a valid encoding
of a member of Φ or 0 otherwise, i.e. returns 1 if s ∈ J or 0
otherwise.
2. mbr: (Membership Testing); given (s,u) returns 1 if u belongs
to the set encoded by s, 0 otherwise.
3.
slo: (Outside Selection); given a list of {s
1
,s
2
,...s
r
} ⊆ Φ it
returns an element u outside of the union of the sets encoded by
{s
1
,s
2
,...s
r
} or ⊥ if no such element exists.
sbs: (Inclusion Testing); given (s,s
0
) returns 1 if and only if s
is a subset of s
0
.
4.
5.
cvr: (Parent Finding); given (s,i) for i ≤ cvm, it returns a
parent s
0
of s, i.e., an s
0
such that sbs(s,s
0
) = 1 and there exists
no s
00
such that sbs(s,s
00
) = sbs(s
00
,s
0
) = 1 holds. There are
possibly up to cvm parents of s; the index i refers to a specific
parent according to some order.
We also assume that cvr(s,j) = ⊥ if no j-th parent of s exists.
For convenience we will also assume if cvr(s,i),cvr(s,j) are
both defined it holds |cvr(s,i)| ≥ |cvr(s,j)| for i ≤ j, i.e., the
parents are ordered from larger to smaller.
spt: (Split Finding); given s it returns a pair (s
0
,s
00
) such that
the union of the subsets represented by s
0
,s
00
is equal to the subset
represented by s and s
0
,s
00
are disjoint. If s is an atom it returns
⊥.
6.
We say that a family Φ is e
cient if l(n) is polylogarithmic in n and the
above six algorithms are polynomial-time.
The split finding algorithm cited above is not needed for the purpose of
broadcast encryption but it will become handy for traitor tracing something
we will elaborate on in Chapter
4
. In some set systems we note that splitting
may return more than 2 subsets. We give the computational specification of
various collections Φ for existing subset cover schemes in Section
2.5
.
2.3.3 Compression of Key Material
In this section we will focus on the issue of key assignment and perform
a closer examination of how KeyGen can be designed to improve its key
storage characteristics. This is an important aspect that also has a bearing in
