International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Weakly Super-Invertible Matrices and Constant Communication Dishonest Majority MPC

Authors:
Alexander Bienstock , JPMorgan AI Research & JPMorgan AlgoCRYPT CoE
Kevin Yeo , Google and Columbia University
Download:
Search ePrint
Search Google
Conference: EUROCRYPT 2025
Abstract: In recent years, there has been tremendous progress in improving the concrete communication complexity of dishonest majority MPC. In the sub-optimal corruption threshold setting where t<(1−ε)⋅n for some constant 0<ε≤1/2, Sharing Transformation (Goyal et al., CRYPTO'22) and SuperPack (Escudero et al., EUROCRYPT'23) presented protocols with information-theoretic online phases requiring O(1) field elements of total communication per multiplication gate. However, Sharing Transformation assumes that their offline phase is instantiated by a trusted party, while SuperPack instantiates their offline phase with large communication of Ω(n) per multiplication gate assuming oblivious linear evaluation (OLE) correlations. The main bottleneck in instantiating the offline phases of both protocols is generating random packed beaver triples of the form [a],[b],[c], for random a,b∈Fk, and c=a∗b∈Fk, where k=Ω(n) is the packing parameter. To address this bottleneck, our main technical contribution is introducing and constructing weakly super-invertible matrices, a relaxation of super-invertible matrices in which sub-matrices have high (but not necessarily full) rank. This relaxation allows for matrices with only O~(n) non-zero entries, enabling a first step towards generating packed beaver triples with O~(1) total communication per underlying triple, assuming OLE correlations. As the second (and final) step, we use the efficient triple extraction protocol of (Choudhury and Patra, Trans. Inform. Theory '17). We also implement our packed beaver triple protocol and provide experimental results. Our new protocol obtains up to 38% smaller communication and 9% reduction in runtime compared to SuperPack's triple protocol. Additionally, by instantiating SuperPack's offline phase with our new protocol, we obtain up to 16% communication reductions. Finally, we use our packed beaver triple protocol to instantiate the offline phase of Sharing Transformation, yielding a dishonest majority MPC protocol with O~(|C|) total communication across both the offline and online phases.
BibTeX
@inproceedings{eurocrypt-2025-35062,
  title={Weakly Super-Invertible Matrices and Constant Communication Dishonest Majority MPC},
  publisher={Springer-Verlag},
  author={Alexander Bienstock and Kevin Yeo},
  year=2025
}