CryptoDB
Honest Majority MPC with $\Tilde{O}(|C|)$ Communication in Minicrypt
| Authors: |
|
|---|---|
| Download: | |
| Conference: | EUROCRYPT 2025 |
| Abstract: | In this work, we consider the communication complexity of MPC protocol in honest majority setting achieving malicious security in both information-theoretic setting and computational setting. On the one hand, we study the possibility of basing honest majority MPC protocols on oblivious linear evaluation (OLE)-hybrid model efficiently. More precisely, we instantiate preprocessing phase of the recent work Sharing Transformation (Goyal, Polychroniadou and Song, CRYPTO 2022) assuming random OLE correlations. Notably, we are able to prepare packed Beaver triples with malicious security achieving amortized communication $O(n)$ field elements plus $O(n)$ number of OLE correlations per packed Beaver triple, which is the best known result. To further efficiently prepare random OLE correlations, we resort to IKNP-style OT extension protocols (CRYPTO 2003) in random oracle model. On the other hand, we derive a communication lower bound for preparing OLE correlations in the information-theoretic setting based on negative results due to Damg{\aa}rd, Larsen, and Nielsen (CRYPTO 2019). Combining our positive result with the work of Goyal, Polychroniadou and Song (CRYPTO 2022), we derive an MPC protocol with amortized communication of $O(\ell+\kappa)$ elements per gate in random oracle model achieving malicious security, where $\ell$ denotes the length of a field element and $\kappa$ is the security parameter. |
BibTeX
@inproceedings{eurocrypt-2025-35003,
title={Honest Majority MPC with $\Tilde{O}(|C|)$ Communication in Minicrypt},
publisher={Springer-Verlag},
author={Yifan Song and Xiaxi Ye},
year=2025
}