International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Efficient Secure Communication Over Dynamic Incomplete Networks With Minimal Connectivity

Authors:
Ivan Damgård , Aarhus University
Divya Ravi , University of Amsterdam
Lawrence Roy , Aarhus University
Daniel Tschudi , Concordium, INS OST
Sophia Yakoubov , Aarhus University
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: TCC 2024
Abstract: We study the problem of implementing unconditionally secure reliable and private communication (and hence secure computation) in dynamic incomplete networks. Our model assumes that the network is always k-connected, for some k, but the concrete connection graph is adversarially chosen in each round of interaction. We show that, with n players and t malicious corruptions, perfectly secure communication is possible if and only if k > 2t. This disproves a conjecture from earlier work, that k > 3t is necessary. Our new protocols are much more efficient than previous work; in particular, we improve the round and communication complexity by an exponential factor (in n) in both the semi-honest and the malicious corruption setting, leading to protocols with polynomial complexity.
BibTeX
@inproceedings{tcc-2024-34765,
  title={Efficient Secure Communication Over Dynamic Incomplete Networks With Minimal Connectivity},
  publisher={Springer-Verlag},
  author={Ivan Damgård and Divya Ravi and Lawrence Roy and Daniel Tschudi and Sophia Yakoubov},
  year=2024
}