k-Connected Graphs, their Generalizations and Applications to Privacy and Reliability in Point-To-Point Networks

Graph theory, in particular k-connectivity is useful to making networks reliable. In cryptography we deal with an adversary that may take control of nodes instead of dealing with faults occurring with a certain probability. The usual model used to describe the possible sets of nodes the adversary can take control over is to assume the number of the nodes is bounded by a threshold. A more general one is to use a general  adversary structure.

In contrast with traditional cryptography the work in this area assumes  nodes do not have shared keys. Questions that arise in cryptography are:  to achieve privacy only (against a passive adversary), reliability  (against an active adversary) and both. Moreover, we may want to achieve  this with probability 1 or with probability close to 1, interactively, or non-interactively.

Many of the necessary and sufficient conditions to achieve this correspond to connectivity conditions on graphs.  We very briefly survey the research when it is extended to partial broadcast networks, which are modeled by directed hypergraphs.  In this talk we abstract away details of the network, such as the protocols used today, whether we have a DNS, etc.