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
Abstract

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
dynamic graphsreliable communicationprivate communicationsecret sharing
Contact author(s)
ivan @ cs au dk
divya @ cs au dk
dt @ concordium com
sophia yakoubov @ cs au dk
History
2023-04-12: approved
2023-04-12: received
See all versions
Short URL
https://ia.cr/2023/529
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/529,
      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},
      url = {https://eprint.iacr.org/2023/529}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.