Paper 2023/529

Secure Communication in Dynamic Incomplete Networks

Ivan Damgård, Aarhus University
Divya Ravi, Aarhus University
Daniel Tschudi, Concordium
Sophia Yakoubov, Aarhus University

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.

Available format(s)
Cryptographic protocols
Publication info
dynamic graphsreliable communicationprivate communicationsecret sharing
Contact author(s)
ivan @ cs au dk
divya @ cs au dk
dt @ concordium com
sophia yakoubov @ cs au dk
2023-04-12: approved
2023-04-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ivan Damgård and Divya Ravi and Daniel Tschudi and Sophia Yakoubov},
      title = {Secure Communication in Dynamic Incomplete Networks},
      howpublished = {Cryptology ePrint Archive, Paper 2023/529},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.