Efficient Secure Communication Over Dynamic Incomplete Networks With Minimal Connectivity

Ivan Bjerre Damgård; Divya Ravi; Lawrence David Roy; Daniel Tschudi; Sophia Yakoubov

doi:10.1007/978-3-031-78023-3_9

Efficient Secure Communication Over Dynamic Incomplete Networks With Minimal Connectivity

Ivan Bjerre Damgård
, Divya Ravi
, Lawrence David Roy
, Daniel Tschudi
, Sophia Yakoubov

Department of Computer Science

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

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.

Original language	English
Title of host publication	Theory of Cryptography - 22nd International Conference, TCC 2024, Proceedings
Editors	Elette Boyle, Elette Boyle, Mohammad Mahmoody
Number of pages	27
Place of publication	Cham
Publisher	Springer
Publication date	2025
Pages	266–292
ISBN (Print)	978-3-031-78022-6
ISBN (Electronic)	978-3-031-78023-3
DOIs	https://doi.org/10.1007/978-3-031-78023-3_9
Publication status	Published - 2025

Series	Lecture Notes in Computer Science
Volume	15367
ISSN	0302-9743

Access to Document

10.1007/978-3-031-78023-3_9

Library access?

Check availability with the Royal Danish Library

Cite this

Damgård, Ivan Bjerre ; Ravi, Divya ; Roy, Lawrence David et al. / Efficient Secure Communication Over Dynamic Incomplete Networks With Minimal Connectivity. Theory of Cryptography - 22nd International Conference, TCC 2024, Proceedings. editor / Elette Boyle ; Elette Boyle ; Mohammad Mahmoody. Cham : Springer, 2025. pp. 266–292 (Lecture Notes in Computer Science, Vol. 15367).

@inproceedings{bdd8a6a4a7c54ae29c3ed20d3b81722a,

title = "Efficient Secure Communication Over Dynamic Incomplete Networks With Minimal Connectivity",

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.",

author = "Damg{\aa}rd, \{Ivan Bjerre\} and Divya Ravi and Roy, \{Lawrence David\} and Daniel Tschudi and Sophia Yakoubov",

year = "2025",

doi = "10.1007/978-3-031-78023-3\_9",

language = "English",

isbn = "978-3-031-78022-6",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "266–292",

editor = "Elette Boyle and Elette Boyle and Mohammad Mahmoody",

booktitle = "Theory of Cryptography - 22nd International Conference, TCC 2024, Proceedings",

address = "Netherlands",

}

Damgård, IB, Ravi, D, Roy, LD, Tschudi, D & Yakoubov, S 2025, Efficient Secure Communication Over Dynamic Incomplete Networks With Minimal Connectivity. in E Boyle, E Boyle & M Mahmoody (eds), Theory of Cryptography - 22nd International Conference, TCC 2024, Proceedings. Springer, Cham, Lecture Notes in Computer Science, vol. 15367, pp. 266–292. https://doi.org/10.1007/978-3-031-78023-3_9

Efficient Secure Communication Over Dynamic Incomplete Networks With Minimal Connectivity. / Damgård, Ivan Bjerre; Ravi, Divya; Roy, Lawrence David et al.
Theory of Cryptography - 22nd International Conference, TCC 2024, Proceedings. ed. / Elette Boyle; Elette Boyle; Mohammad Mahmoody. Cham: Springer, 2025. p. 266–292 (Lecture Notes in Computer Science, Vol. 15367).

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Efficient Secure Communication Over Dynamic Incomplete Networks With Minimal Connectivity

AU - Damgård, Ivan Bjerre

AU - Ravi, Divya

AU - Roy, Lawrence David

AU - Tschudi, Daniel

AU - Yakoubov, Sophia

PY - 2025

Y1 - 2025

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

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

UR - https://www.scopus.com/pages/publications/85211892226

U2 - 10.1007/978-3-031-78023-3_9

DO - 10.1007/978-3-031-78023-3_9

M3 - Article in proceedings

SN - 978-3-031-78022-6

T3 - Lecture Notes in Computer Science

SP - 266

EP - 292

BT - Theory of Cryptography - 22nd International Conference, TCC 2024, Proceedings

A2 - Boyle, Elette

A2 - Mahmoody, Mohammad

PB - Springer

CY - Cham

ER -

Damgård IB, Ravi D, Roy LD, Tschudi D, Yakoubov S. Efficient Secure Communication Over Dynamic Incomplete Networks With Minimal Connectivity. In Boyle E, Boyle E, Mahmoody M, editors, Theory of Cryptography - 22nd International Conference, TCC 2024, Proceedings. Cham: Springer. 2025. p. 266–292. (Lecture Notes in Computer Science, Vol. 15367). doi: 10.1007/978-3-031-78023-3_9

Efficient Secure Communication Over Dynamic Incomplete Networks With Minimal Connectivity

Abstract

Access to Document

Library access?

Other files and links

Fingerprint

Cite this