Sublinear Distributed Product Checks on Replicated Secret-Shared Data over Z2k Without Ring Extensions

Multiple works have designed or used maliciously secure honest majority MPC protocols over Z 2 𝑘 using replicated secret sharing (e.g. Koti et al. USENIX'21). A recent trend in the design of such MPC protocols is to first execute a semi-honest protocol, and then use a check that verifies the correctness of the computation requiring only sublinear amount of communication in terms of the circuit size. The so-called Galois ring extensions are needed in order to execute such checks over Z 2 𝑘 , but these rings incur incredibly high computation overheads, which completely undermine any potential benefits the ring Z 2 𝑘 had to begin with. In this work we revisit the task of designing sublinear distributed product checks on replicated secret-shared data over Z 2 𝑘 among three parties with an honest majority. We present a novel technique for verifying the correctness of a set of multiplication (in fact, inner product) triples, involving a sublinear cost in terms of the number of multiplications. Most importantly, unlike previous works, our tools do not rely on Galois ring extensions, which are computationally expensive, and only require computation over rings of the form Z 2 ℓ . In terms of communication, our checks are 3 ∼ 5× lighter than existing checks using ring extensions, which is already quite remarkable. However, our most noticeable improvement is in terms of computation: our checks are 17.7 ∼ 44.2× better than previous approaches, for many parameter regimes of interest. Our * Corresponding author This work is licensed under a Creative Commons Attribution International 4.0 License.