Paper 2025/283

Honest Majority MPC with O~(|C|) Communication in Minicrypt

Yifan Song, Tsinghua University and Shanghai Qi Zhi Institute
Xiaxi Ye, Tsinghua University
Abstract

In this work, we consider the communication complexity of MPC protocols 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 with information-theoretic security. 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 of field elements plus a 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 (Ishai et al., 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å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 elements per gate in random oracle model achieving malicious security, where denotes the length of a field element and is the security parameter.

Note: Acknowledgement added.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in EUROCRYPT 2025
Keywords
Communication complexityMultiparty computationInformation-theoretic securityLightweight cryptography
Contact author(s)
yfsong @ mail tsinghua edu cn
yexx23 @ mails tsinghua edu cn
History
2025-02-24: revised
2025-02-19: received
See all versions
Short URL
https://ia.cr/2025/283
License
Creative Commons Attribution-NonCommercial
CC BY-NC

BibTeX

@misc{cryptoeprint:2025/283,
      author = {Yifan Song and Xiaxi Ye},
      title = {Honest Majority {MPC} with $\tilde{O}(|C|)$ Communication in Minicrypt},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/283},
      year = {2025},
      url = {https://eprint.iacr.org/2025/283}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.