Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review
Final published version
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 language | English |
---|---|
Title of host publication | 4th Conference on Information-Theoretic Cryptography, ITC 2023 |
Editors | Kai-Min Chung |
Publisher | Schloss Dagstuhl--Leibniz-Zentrum für Informatik |
Publication year | Jul 2023 |
Pages | 13:1--13:21 |
Article number | 13 |
ISBN (electronic) | 9783959772716 |
DOIs | |
Publication status | Published - Jul 2023 |
Event | 4th Conference on Information-Theoretic Cryptography, ITC 2023 - Aarhus, Denmark Duration: 6 Jun 2023 → 8 Jun 2023 |
Conference | 4th Conference on Information-Theoretic Cryptography, ITC 2023 |
---|---|
Land | Denmark |
By | Aarhus |
Periode | 06/06/2023 → 08/06/2023 |
Series | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Volume | 267 |
ISSN | 1868-8969 |
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)
See relations at Aarhus University Citationformats
ID: 341330055