[Resource Topic] 2023/529: Secure Communication in Dynamic Incomplete Networks

Welcome to the resource topic for 2023/529

Secure Communication in Dynamic Incomplete Networks

Authors: Ivan Damgård, Divya Ravi, Daniel Tschudi, Sophia Yakoubov


In this paper, we explore the feasibility of reliable and private communication in dynamic networks, where in each round the adversary can choose which direct peer-to-peer links are available in the network graph, under the sole condition that the graph is k-connected at each round (for some k).

We show that reliable communication is possible in such a dynamic network if and only if k > 2t. We also show that if k = cn > 2t for a constant c, we can achieve reliable communication with polynomial round and communication complexity.

For unconditionally private communication, we show that for a passive adversary, k > t is sufficient (and clearly necessary). For an active adversary, we show that k > 2t is sufficient for statistical security (and clearly necessary), while k > 3t is sufficient for perfect security. We conjecture that, in contrast to the static case, k > 2t is not enough for perfect security, and we give evidence that the conjecture is true.

Once we have reliable and private communication between each pair of parties, we can emulate a complete network with secure channels, and we can use known protocols to do secure computation.

ePrint: https://eprint.iacr.org/2023/529

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .