Limited-Sharing Multi-Party Computation With Reduced Recovery Threshold

In secure multi-party computation, multiple data sources are involved, and a master needs to compute a function over them. This computation is often offloaded to processing nodes, some of which may collude in an attempt to extract private information. Therefore, ensuring the privacy of the data is crucial. In this work, we assume that the data are large matrices, which need to be partitioned into smaller pieces for storage in the processors. Additionally, there is a limited-capacity communication link between the data sources and processors. Consequently, we aim to upload all the data in a single round, while allowing processors to communicate with one another. We propose an approach to matrix multiplication that incorporates Strassen algorithm, enabling us to compute the function with fewer processors while preserving privacy against both the processing nodes and the master. Moreover, our scheme efficiently handles a distributed batch matrix multiplication setting, where an identical function needs to be applied to different datasets.