License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITC.2023.13
URN: urn:nbn:de:0030-drops-183419
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18341/
Go to the corresponding LIPIcs Volume Portal

Damgård, Ivan ; Ravi, Divya ; Tschudi, Daniel ; Yakoubov, Sophia

Secure Communication in Dynamic Incomplete Networks

pdf-format:
LIPIcs-ITC-2023-13.pdf (0.9 MB)

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 > 2 t 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.

BibTeX - Entry

@InProceedings{damgard_et_al:LIPIcs.ITC.2023.13,
  author =	{Damg\r{a}rd, Ivan and Ravi, Divya and Tschudi, Daniel and Yakoubov, Sophia},
  title =	{{Secure Communication in Dynamic Incomplete Networks}},
  booktitle =	{4th Conference on Information-Theoretic Cryptography (ITC 2023)},
  pages =	{13:1--13:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-271-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{267},
  editor =	{Chung, Kai-Min},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18341},
  URN =		{urn:nbn:de:0030-drops-183419},
  doi =		{10.4230/LIPIcs.ITC.2023.13},
  annote =	{Keywords: Secure Communication, Dynamic Incomplete Network, Information-theoretic}
}

Keywords: Secure Communication, Dynamic Incomplete Network, Information-theoretic
Collection: 4th Conference on Information-Theoretic Cryptography (ITC 2023)
Issue Date: 2023
Date of publication: 21.07.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI