Aarhus University Seal

Secure Communication in Dynamic Incomplete Networks

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

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.

Original languageEnglish
Title of host publication4th Conference on Information-Theoretic Cryptography, ITC 2023
EditorsKai-Min Chung
PublisherSchloss Dagstuhl--Leibniz-Zentrum für Informatik
Publication yearJul 2023
Article number13
ISBN (electronic)9783959772716
Publication statusPublished - Jul 2023
Event4th Conference on Information-Theoretic Cryptography, ITC 2023 - Aarhus, Denmark
Duration: 6 Jun 20238 Jun 2023


Conference4th Conference on Information-Theoretic Cryptography, ITC 2023
SeriesLeibniz International Proceedings in Informatics, LIPIcs

Bibliographical note

Publisher Copyright:
© Ivan Damgård, Divya Ravi, Daniel Tschudi, and Sophia Yakoubov; licensed under Creative Commons License CC-BY 4.0 4th Conference on Information-Theoretic Cryptography (ITC 2023)

    Research areas

  • Dynamic Incomplete Network, Information-theoretic, Secure Communication

See relations at Aarhus University Citationformats

ID: 341330055