Cryptography Reference
In-Depth Information
that is selected by A in its first stage. The simulation of the second stage
of A within experiment Exp 2 can be carried out by B 2 without problem by
resorting to its encryption oracle whenever needed.
Based on the assumption on the underlying encryption scheme we have
that Prob[Exp kem
B 2 (1 n )]−1/2|≤ ε 2 . We observe that in the key encapsulation
attack of B 2 in the conditional space b = 0, the adversary B ke 2 (1 n ) operates
identically to the experiment Exp v− 2 while in the conditional space b = 1 it
operates identically to the experiment Exp 2 . Based on this derive the proof
of the claim.
We are now ready to give the proof of the theorem. First recall from our
first claim that there is a v 0 ∈{1,...,t} such that
ε
t·|Φ|
| p v 0 1 −p v 0
1 |≥
2 |≤ 2ε 1 as well as |p v 0 1
p v 0 2 | ≤ 2ε 1 . We know that for any a,b,c,d,e, |a−b| ≥ d and |b−c| ≤ e
implies |a − c| ≥ d − e. By combining this with the above facts we have
|p v 0 −1
2
From our second claim we know that |p v 0
1 −p v 0
−p v 0
2 | ≥ ε/(t·|Φ|) − 4ε 1 . Now based on our third claim we have that
|p v 0 −1
2
−p v 0
2 |≤ 2ε 2 . From this we obtain ε ≤ 2t·|Φ|·(2ε 1 2 ) which completes
the proof.
2.2.2 The Subset Cover Framework
Among set systems, fully-exclusive set systems are of interest due to their
support for revocation for any number of receivers. The subset cover frame-
work class of fully-exclusive set systems to be used in broadcast encryption
template given in Figure 2.2 . We can list the requirements of a set system Φ
to be considered in the framework as follows:
1. The set system Φ is fully-exclusive, i.e. Φ is (n,n,t)-exclusive where Φ is
defined over a set of size n, and t is a function of the size r of the revoked
set.
2. The set system is accompanied with an e cient revocation algorithm
Revoke that produces the indices j i ,i = 1,...,s of the subsets that cover
the set of enabled users [n] \R. We require the e ciency in the following
sense: (i) The time required to compute the pattern is e cient, i.e. poly-
log in the number of receivers (ii) The output pattern consists of minimal
number of subsets that is a function of n and r = |R|.
3. The set system Φ supports “bifurcation property”: it should be possible
to split any subset S ∈ Φ into two roughly equal sets, i.e. that there exists
S 1 ,S 2 ∈ Φ such that S = S 1 ∪ S 2 and |S 1 |/|S 2 | is bounded above from a
constant. In some cases, although the first split might not hold the above
property, it is also acceptable if the relative size of the larger subset in
consecutive split operations converges to the bound quickly.
Search WWH ::




Custom Search