Transcript Expander Graphs for Digital Stream Authentication and Robust

Expander Graphs for Digital
Stream Authentication and
Robust Overlay Networks
Presented by
Neeraj Agrawal, Zifei Zhong
Contents
•
•
•
•
•
Introduction
Authentication of Digital Broadcast Data
Overlay Networks
Basic Definitions & Theorems
Expander-Based Authentication:
-- DAG Expander Construction & Analysis
-- Authentication Graph
• Expander-Based Overlay Network
-- Construction & Analysis
-- Applications
• Conclusion and Future work.
Introduction
Expander Graphs for
• Authenticating the digital data over lossy
network
• Construction of robust Overlay Networks
Authentication of Digital Broadcast
Data
• Goal
To ensure that digitally broadcast streams
originate from the purported source.
• Challenge
Internet and other networks are not perfect
and lost packets are generally not transmitted.
Possible Solutions
• Shared Secret between sender and
receivers
Sender computes the MAC using a shared
key and receiver uses this key to authenticate
the packets.
• Disadvantage
Anyone with the shared secret could forge or
leak the shared secret.
Possible Solutions (Cont…)
• Asymmetric Cryptography
Sender can sign each packet with its private
key and each receiver verifies the signature of
each packet with corresponding public key.
• Disadvantage
Heavy overhead of generation and
verification of packets.
Possible Solutions (Cont…)
• Graph Based Authentication
Possible Solutions (Cont…)
• Drawbacks:
Since the degree of the vertices in the graph are
not constant they grow linearly to the number of
nodes in the graph.
Due to this the efficiency of the implementation
is reduced.
Overlay Networks
• Overlay networks are formed from a subset of
nodes in underlying network. The participating
nodes communicate via virtual links between two
nodes that may not be directly connected in the
underlying network. (ex. MBone, ABone,
Gnutella).
• Goal is to improve the reachability of any node in
the network using expander graphs thereby
making the network robust.
Expander Graph based
Authentication
Expander Graph based
Authentication (Cont…)
• Let {P0, …, Pn-1} be the consecutive packets that need to
be broadcasted. Then a directed acyclic graph is
constructed out of these n vertices where vertex i
corresponds to the packet Pi. An edge (i,j) in the graph
indicates the authentication relationship between packet
Pi and Pj
• To authenticate a packet Pj receiver simply computes the
hash of Pj and checks whether it equals the
corresponding hash value carried in Pi.
• The DAG formed by the n nodes and the edges
corresponding to the authentication relationship is known
as authentication graph.
Expander Graph based
Authentication (Cont…)
• Notations
Up Vertex:
A vertex is said to be up if the corresponding
packet is received.
Up Path:
A path is said to be up if all the vertices on
the path are up.
Signature Packet:
Starting packet of the stream is called
signature packet which is signed by senders
public key. Receivers authenticate other
packets by following the edge starting from
this signature packet.
Expander Graph based
Authentication (Cont…)
• Assumptions
1. All receivers receive the signature packet.
2. Senders and Receivers have large buffering capacity.
3. Probabilistic model for packet loss is assumed where
each packet in the stream can be received with
probability p independent of other packets.
4. Hash function is assumed to be collision resistant, i.e. it
is computationally infeasible to find two different values
that hash to the same value.
Basic Definitions & Theorems
• Definition 1. Bipartite Graph
A bipartite graph
is an undirected graph
consisting of two non-overlapping sets of vertices V1 and
V2 and edges connecting the two sets of vertices, i.e. if
an edge
, then either
or
u V2 , v V1 . G is called a (n1,n2)-bipartite graph with
degree (d1,d2) if |V1| = n1, |V2| = n2; and every node in
V1 has degree at most d1, every node in V2 has degree
at most d2. If d1 = d2 we say the degree is d1
Now the boring journey starts…
Basic Definitions & Theorems
• Definition 2. Bipartite Expander
A bipartite graph
is (c1,c2)-expanding
if for i = 1,2, for every
, where | S | | V3i | 2ci ,
| T S  | ci | S ,| where T(S) is the set of neighbors
of S in V3-I. if c1=c2, we say the graph is c1expanding.
… definitions are hard to remember, especially long ones…
Basic Definitions & Theorems
• Definition 3. Ordinary Expander Graph
An undirected graph G  V , E  is c-expanding if for
every
where | T S | c  1 | S | , | S | | V | 2c 
where T(S) is the set of neighbors of S (not including S).
  
… they do not grow longer, fortunately …

Basic Definitions & Theorems
• Theorem 1. Ramanujan Graph
The Ramanujan graph construction give a (n, n)-bipartite
expander graph of degree d for every n = q +1, d = p+1
where p and q are two primes congruent to 1 modulo 4.
These graphs are (d/8)-expanding. The same
construction can be used to construct ordinary expander
graphs with n vertices and degree d and (d/8)-expanding.
… let’s simply call it Rama graph…
Basic Definitions & Theorems
• Theorem 2. Chernoff Bound
Let X1, X2, …, Xn be independent random variables such
that for 1  i  n, Pr[ X i  1]  pi , Pr[ X i  0]  1  pi
where 0  pi  1.
Define X 
X,
n
1
i
and define
  E[X ].


0    1, Pr[ X  1    ]  exp   2 2 .
…chernoff bound is useful, we should know it…
Then for
Basic Definitions & Theorems
• Corollary 3
Given a set of s no des where each node is up
independently with probability p, the probability that at
least (ps/2) nodes are up is at least 1  exp  ps 8.
Yeah…, just apply the chernoff bound, we get it…
Expander-Based Authentication:
-- DAG Expander Construction & Analysis
• How to construct…
Use the expansion property of expanders to construct an
authentication graph allowing a receiver to authenticate
a received packet with high probability.
Let’s first see how to use a (n, n)-bipartite expander
graph with degree d and expander factor c to construct a
(n/a, n)-bipartite expander…
The idea seems not difficult…
Expander-Based Authentication:
-- DAG Expander Construction & Analysis
• Lemma 1
Given a (n, n)-bipartite expander graph with degree d
and expansion factor c, we can explicitly construct a (n/a,
n)-bipartite expander of degree (da, d) and is (ac, c/a)expanding.
This point is obvious…
Expander-Based Authentication:
-- DAG Expander Construction & Analysis
• Construction
We construct a layered DAG expander using the (na, n)-bipartite
expanders found by applying Lemma 1 to any (n, n)-bipartite
expander graph.
1). The 0-th layer contains the root R, and for all i the i-th layer
i
contains a vertices. Layers i-1 and i are connected using a copy of
an a i 1 , a i  -bipartite expander graph from Lemma 1.
2). The edges point from layer i-1 to layer i. Let c denote the
expansion factor from the i-th layer to i-1th layer.
Wow~, somehow complicated…
Expander-Based Authentication:
-- DAG Expander Construction & Analysis
• An example of construction
…it’s a dull figure…
Expander-Based Authentication:
-- DAG Expander Construction & Analysis
• Property Analysis
Claim 1: suppose
cp 2
t i 1
Then the probability that
 a 2c .
i
| Si | cp 2
t i
is at least
 t i
 1  cp   
exp  cp 8




1   exp   
 1
.


  1

4
2
1  exp  cp 8






…but…, how can you claim that …
Expander-Based Authentication:
-- DAG Expander Construction & Analysis
• Property Analysis
Claim 2: with probability at least
exp  cp 8
1
,
1  exp  cp 8
there is an m for which
| S m | a
m 1
…terrible… this one is based on the previous …
2c 
Expander-Based Authentication:
-- DAG Expander Construction & Analysis
• Property Analysis
Claim 3: if
| S m | a m1 2c 
i
|
S
|

pa
4 for all i < m, with probability at least
then
i
exp  ap 16
1   exp  a p 16  1 
.
1  exp  ap 16
i 1
m 1

i

…well… we require LESS complicated things…
Expander-Based Authentication:
-- DAG Expander Construction & Analysis
• Property Analysis
Theorem 4: Assume each vertex except the root R in
our DAG expander is up independently with probability p,
where c is the expansion factor from i-1th layer, c>4/p
and a>4/p. If a vertex v is up, then there exists an up
path from R to v with probability at least
exp  cp 8
exp  cp 16
1

.
1  exp  cp 8 1  exp  cp 16
…en~…, this is from the previous 3 claims..
Expander-Based Authentication:
-- Authentication Graph
• How to build the authentication graph?
1). Exploit the DAG construction, let the root be the 1st
packet P0.
2). Number the vertices from 0 to n-1 layer by layer. Any
vertex on layer i has a lower number than any vertex on
layer i+1. Let vertex i correspond to packet Pi.
…well~…, finally we come out from the hell ...
Expander-Based Authentication:
-- Authentication Graph
• Properties
1). Each packet except for those corresponding to leaves
on the DAG expander has a constant number d*a
embedded hash values, and the constant number d*a is
independent of the size of graph.
2). The authentication probability is at least
exp  cp 8
exp  ap 16
1

1  exp  cp 8 1  exp  ap 16
…aha, …now I know what the theorem 4 does..
Expander-Based Authentication:
-- Authentication Graph
• Properties
-- We can control the arrival probability by a and d…
Corollary 5. Assume we have a DAG expander, each
vertex in it except the root R is up independently with
probability p, and d>32a/p and a>4/p. If a vertex v is up,
then there exists an up path from R to v with probability
at least
exp  dp 64a 
exp  ap 16
1

1  exp  dp 64a  1  exp  ap 16
…???, …this is somewhat different...
Expander-Based Overlay Networks:
-- Construction & Analysis
• Construction
1). Given n nodes, we build the overlay network as the
Ramanujan expander graph with n nodes and degree d.
2). Each node corresponds to a host in the overlay
network, while each edge represent a virtual link
between the two connected hosts.
3). Assume transmission time and latency are bounded.
…ooh, …what’s this…
Expander-Based Overlay Networks:
-- Construction & Analysis
• Analysis
Lemma 2. With probability at least
exp  dp 64
1
1  exp  dp 64
any up node v can reach more than pn/4 up nodes
within distance O(log n) via up paths.
…well, …something not easy …
Expander-Based Overlay Networks:
-- Construction & Analysis
• Analysis
Claim 1. Suppose
dp 16
Then the probability that
i 1
.
 4n d
| Si | dp 16 is at least
i
 1  dp   
exp  dp 64


1   exp     1 
 4  16  
1  exp  dp 64
l 1


i
…god, …it’s another nightmare …
Expander-Based Overlay Networks:
-- Construction & Analysis
• Analysis
exp  dp 64
Claim 2. With probability at least 1 
,
1  exp  dp 64
there is an m for which
| Si | 4n / d
and m = O(log n).
…somehow not as tough as before …
Expander-Based Overlay Networks:
-- Construction & Analysis
• Analysis
Lemma 3. Any two sets of size at least
2n
d
in a Ramanujan expander with n nodes and degree d
have at least one edge between the two sets.
…but, …where is the proof…
Expander-Based Overlay Networks:
-- Construction & Analysis
• Analysis
Theorem 6. Let G be an undirected Ramanujan
expander graph on n nodes with degree d. Assume
each node in the graph is up independently with
probability p. For any two up nodes v and w, the
probability that there is an up path of length O(log n)
from v to w is 1  2 exp( dp / 64) given that d (8 p) .
1  exp( dp / 64)
Similarly a broadcast message by v will reach a
particular node in an up path of length O(log n) with
probability at least 1  2 exp( dp / 64)
2
1  exp( dp / 64)
…good~, …we are approaching the end…
Expander-Based Overlay Networks:
-- Application to Decentralized Certificate Revocation
• Overlay networks can have an effective graph for
distributing certificate revocation messages.
• Since the graph for representing the overlay network is
constant degree it requires only constant number of
messages to send or receive the revocation message.
• Each node is reachable by an up path of length O(log n)
• Even if a high fraction of node fails each up node will
receive the revocation message in O(log n) steps with
probability 1  2 exp( dp / 64)
1  exp( dp / 64)
Expander-Based Overlay Networks:
-- Application in building Survival Networks
• If an adversary can take out nodes in the network with
independent probability then the results described in the
previous slide implies that we can always build up the
overlay network that is highly survivable.
Conclusion
• An efficient construction for authentication
graph of constant degree. It is an
improvement over previous solution which
used O(n) degree.
• This construction provides high probability
of authentication.
• A proven lower bound of probability that a
packet can be authenticated upon arrival
has be provided
Conclusion (cont...)
• The lower bound is independent of the
size of the graph.
• Undirected expander graphs and results
discussed can be used to construct
efficient, robust and scalable overlay
networks.
• Overlay networks provide efficient solution
to the decentralized certification revocation
problem.
Future Work
• Expander Construction is still an active
area in the graph theory.
• There is still lots of scope for improvement
ex. Probability bound can be improved by
using Kahle’s results.
Questions, please ~:-)