Secure Communication in Dynamic Incomplete Networks

TY - GEN

T1 - Secure Communication in Dynamic Incomplete Networks

AU - Damgård, Ivan

AU - Ravi, Divya

AU - Tschudi, Daniel

AU - Yakoubov, Sophia

N1 - 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)

PY - 2023/7

Y1 - 2023/7

N2 - 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.

AB - 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.

KW - Dynamic Incomplete Network

KW - Information-theoretic

KW - Secure Communication

UR - http://www.scopus.com/inward/record.url?scp=85168994172&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ITC.2023.13

DO - 10.4230/LIPIcs.ITC.2023.13

M3 - Article in proceedings

AN - SCOPUS:85168994172

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 13:1--13:21

BT - 4th Conference on Information-Theoretic Cryptography, ITC 2023

A2 - Chung, Kai-Min

PB - Schloss Dagstuhl--Leibniz-Zentrum für Informatik

T2 - 4th Conference on Information-Theoretic Cryptography, ITC 2023

Y2 - 6 June 2023 through 8 June 2023

ER -