ppt

Explicit Exclusive Set
Systems with Applications to
Broadcast Encryption
Craig Gentry
Stanford
Zulfikar Ramzan
Symantec
FOCS 2006
David P. Woodruff
MIT
Broadcast Encryption
Clients
Server
1 server,
n clients
Only
privileged
users can understand broadcasts
E.g.,
those
who pay to
their
monthly
Server
broadcasts
all clients
atbills
once
 Need to encrypt broadcasts
 E.g., payperview TV, music, videos
Subset Cover Framework [NNL]

Offline stage:

For some S ½ [n], server creates a key K(S) and
distributes it to all users in S

Let C be the collection of S

Server space complexity ~ |C|

ith user space complexity ~ # S containing i
Subset Cover Framework [NNL]

Online stage:

Given a set R ½ [n] of at most r revoked users

Server establishes a session key M that only users in
the set [n] n R know
 Finds S1, …, St 2 C with [n] n R = S1 [ … [ St


Encrypt M under each of K(S1), …, K(St)
Content encrypted using session key M
Subset Cover Framework [NNL]

Communication complexity ~ t

Tolerate up to r revoked users

Tolerate any number of colluders

Information-theoretic security
The Combinatorics Problem

Find a family C of subsets of {1, …., n}
such that any large set S µ {1, …, n} is
the union of a small number of sets in C
S = S1 [ S2 [  [ St

Parameters:
 Universe is [n] = {1, …, n}
 |S| >= n-r
 Write S as a union of · t sets in C

Goal:
 Minimize |C|
A Lower Bound
Claim:
Proof:
1.
At least
sets of size ¸ n-r
2.
Only
3.
Thus,
4.
Solve for |C|
different unions
Known Upper Bounds
t
|C|
authors
(r log n / log r)2
(r log n / log r)2
GSY
r log n/r
2n
LNN, ALO
2r
n log n
LNN
r3 log n / log r
r3 log n /log r
KRS
Bad: once n and r are chosen, t and |C| are fixed
Known Upper Bounds

Only known general result:


If r · t, then |C| = O(t3(nt)r/t log n)
[KR]
Drawbacks:





Probabilistic method
To write S = S1 [ S2 [ … [ St , solve Set-Cover
C has large description
No way to verify C is correct
Suboptimal size:
Our Results

Main result: tight upper bound |C| = poly(r,t)


Match lower bound up to poly(r,t)



n, r, t all arbitrary
In applications r, t << n
When r,t << n, get |C| = O(rt
)
Our construction is explicit


Find sets S = S1 [ … [ St in poly(r, t, log n) time
Improved cryptographic applications
Cryptographic Implications

Our explicit exclusive set system yield almost optimal
information-theoretic broadcast encryption and multicertificate revocation schemes

General n,r,t
 Contrasts with previous explicit systems

Poly(r,t, log n) time to find keys for broadcast
 Contrasts with probabilistic constructions

Parameters
 For poly(r, log n) server storage complexity, we can
set t = r log (n/r), but previously t = (r2 log n)
Techniques

Case analysis:

r, t << n:
algebraic solution

general r, t:
use divide-and-conquer approach
to reduce to previous case
Case: r,t << n

Find a prime p = n1/t + 

Users [n] are points in (Fp)t

Consider the ring Fp[X1, …, Xt]

Goal: find set of polynomials C such that
for any R ½ [n] with |R| · r, there exist
p1, …, pt 2 C such that
R = Variety(p1, …, pt)
Case: r,t << n

First design a polynomial collection so that for
any R ½ [n] with |R| · r such that for every
coordinate i, 1 · i · t,
All |R| points differ on the ith coordinate (*)

Then perform a few permutations :[n] -> [n]
and construct new polynomial collections on
([n]). Take the union of these collections.

Can find the  deterministically using MDS
codes
Example Collection: r = 2, t = 3
For r = 2, t = 3, our collection is:
1.
(X1 – a)(X1 – b) for all distinct a,b
2.
aX1 + b – X2 for any a, b 2 Fp
3.
aX2 + b – X3 for any a,b 2 Fp
Revoke u = (u1, u2, u3) and v = (v1, v2, v3)
u1  v1, u2  v2, and u3  v3
Let p1 = (X1 – u1)(X1-v1). Find p2 by interpolating from
au1 + b – u2 = 0, av1 + b – v2 = 0
Find p3 by interpolation. Variety(p1, p2,p3) = u, v
We broadcast with keys K(pi), distributed to users which don’t vanish
on pi
If u1  v1, u2 = v2, and u3  v3, then (u1, u2, v3) also in variety…
Our General Collection
and
Intuition: First type of polynomials implement a
“base case”.
Second type of polynomials implement “AND”s.
Wrapping up the r,t << n case.

Using many tricks – balancing techniques,
expanders, etc., can show even without distinct
coordinates, can achieve size O(rt
).

Almost matches the (t

Open question: resolve this gap.
) lower bound.
General n, r, t
1
x
xxx
i
j
x
x
n
 Problem! n2 term ?!?
 Let m be such that r/m, t/m << n
 Fix:- hash [n] to [r2] first
 For every interval [i, j], form an exclusive set
system
with n’ =hashes
j-i+1, so
r’ =
r/m,ist’an
= injective
t/m
- do enough
there
hash for every R
 Given a set R, find intervals which evenly
partition
- applyR.construction above on [r2]
Summary and Open Questions

Main result: tight explicit upper bound
|C| = poly(r,t)
 n, r, t arbitrary
 Cover sets in poly(r, t, log n) time
 Optimal # of keys per user

Other result: Slightly improve [LS] lower bound
on keys per user in any scheme using a relaxed
sunflower lemma: from (
)/(rt) to (
)/r

Open question: improve poly(r,t) factors