IACR News item: 17 June 2024
Ivan Damgård, Divya Ravi, Lawrence Roy, Daniel Tschudi, Sophia Yakoubov
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.
Additional news items may be found on the IACR news page.