Recently, Yifan Song, an assistant professor at Tsinghua University, and his team proposed a novel unconditionally secure multiparty computation protocol in the asynchronous network setting, which for the first time achieves an amortized cost of linear communication in the number of parties and constant number of secret sharing per gate. In the same time, the team also gave the first protocol for secret sharing with linear communication complexity in the number of parties. When combining these two results together, the team obtained the first unconditionally secure multiparty computation in the asynchronous network setting with linear communication per gate. The achieved results are of great importance in the area of distributed computing and secure multiparty computation. The above two works are both published in CRYPTO 2024. The co-authors of the second result, Xiaoyu Ji and Junru Li, are both Ph.D. students at IIIS, Tsinghua University.

Secure multiparty computation allows several mutually distrusted parties to accomplish a common computation task on their private data. Ben-Or, Canetti, Goldreich [STOC’ 93] and Ben-Or, Kelmer, Rabin [PODC’ 94] established the first feasibility results of secure multiparty computation in the asynchronous setting. Later, despite a great line of works focusing on improving the communication complexity, the previously best-known result with unconditional security still requires a communication complexity proportional to the 4th power of the number of parties. On the contrary, the best-known result in the synchronous setting has already achieved a linear communication complexity in the number of parties.

Yifan Song’s team proposed a novel secret-share based unconditionally secure multiparty computation protocol that achieves an amortized cost of linear communication in the number of parties and constant number of secret sharing per gate. Before that, the previously best-known result [IEEE Trans. Inf. Theory’ 17] requires quadratic communication and linear number of secret sharing per gate. In the same time, the team also achieved linear communication for secret sharing, which improves the previously best-known result [J. Crypto’ 23] that requires cubic communication in the number of parties. When combining these two results together, the team obtained the first unconditionally secure multiparty computation in the asynchronous network setting with linear communication per gate. These results provide possibility of achieving highly efficient secure multiparty computation without relying on synchronous clock.

From the technical side, the main difficulty in the asynchronous setting is to achieve liveness, which requires the protocol to terminate eventually. The reason behind this difficulty is that a party cannot distinguish a delayed message due to the network latency from a corrupted party not sending the message. To achieve liveness, a party needs to proceed after he receives enough number of messages (which is usually equal to the number of honest parties). On the other hand, the messages that are not delivered may come from honest parties while among the received messages, some of them are from corrupted parties. As a result, the number of corrupted parties that can be tolerated in the asynchronous setting is smaller than that in the synchronous setting. And this issue also makes the design of secure multiparty computation protocols in the asynchronous setting much more difficult than that in the synchronous setting. To overcome this difficulty, Yifan Song’s team proposed two efficient solutions but neither of these two solutions guarantees termination. The first solution terminates only if a sufficient number of corrupted parties participate in the protocol. The second solution terminates only if a bounded number of corrupted parties participate. By a careful combination of these two protocols, it is ensured that a party can participate in the second protocol only if he participates the first protocol. In this way, at least one of these two protocols will eventually terminate.

In summary, the proposed secure multiparty computation protocol closes the communication gap between the synchronous setting and the asynchronous setting. The achieved results and techniques are of great importance in the area of distributed computing and secure multiparty computation.

1. Towards Achieving Asynchronous MPC with Linear Communication and Optimal Resilience, Vipul Goyal, Chen-Da Liu-Zhang, and Yifan Song, https://eprint.iacr.org/2024/245, CRYPTO 2024.

2. Linear-Communication Asynchronous Complete Secret Sharing with Optimal Resilience, Xiaoyu Ji, Junru Li, Yifan Song, https://eprint.iacr.org/2024/243, CRYPTO 2024.

Bio

Yifan Song is an assistant professor at IIIS, Tsinghua University. He received the Ph.D. degree from Carnegie Mellon University in 2022, advised by Prof. Vipul Goyal. Before that, he received the Bachelor degree from Yao Class at Tsinghua University in 2017.

Yifan Song is generally interested in theoretical Cryptography and has a special focus on secure multiparty computation. He has published more than 20 papers in the top conferences of Cryptography such as CRYPTO, EUROCRYPT, USENIX Security and so on. He was a committee member of EUROCRYPT 2023, PKC 2024, and ASIACRYPT 2024.

Editor: Yueliang Jiang

Reviewer: Xiamin Lv