Rhombus: Fast Homomorphic Matrix-Vector Multiplication for Secure Two-Party Inference

We present Rhombus, a new secure matrix-vector multiplication (MVM) protocol in the semi-honest two-party setting, which is able to be seamlessly integrated into existing privacy-preserving machine learning (PPML) frameworks and serve as the basis of secure computation in linear layers. Rhombus adopts RLWE-based homomorphic encryption (HE) with coefficient encoding, which allows messages to be chosen from not only a field Fp but also a ring Z2l, where the latter supports faster computation in non-linear layers. To achieve better efficiency, we develop an input-output packing technique that reduces the communication cost incurred by HE with coefficient encoding by about 21×, and propose a split-point picking technique that reduces the number of rotations to that sublinear in the matrix dimension. Compared to the recent protocol HELiKs by Balla and Koushanfar (CCS'23), our implementation demonstrates that Rhombus improves the whole performance of an MVM protocol by a factor of 7.4x 8x, and improves the end-to-end performance of secure two-party inference of ResNet50 by a factor of 4.6x 18x.