Welcome to the resource topic for 2024/972
Title:
Efficient Secure Communication Over Dynamic Incomplete Networks With Minimal Connectivity
Authors: Ivan Damgård, Divya Ravi, Lawrence Roy, Daniel Tschudi, Sophia Yakoubov
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.
ePrint: https://eprint.iacr.org/2024/972
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .