Paper 2024/009

Information-Theoretically Secure Distributed Protocols for Two-Party MPC Primitives

Abstract

We study two-party secure computation in a \emph{distributed mediated} model with $D$ servers. We present \emph{information-theoretically secure} protocols for foundational primitives— $1$-out-of-$N$ and $k$-out-of-$N$ oblivious transfer (OT), Priced OT, Generalized OT, and Oblivious Multivariate Polynomial Evaluation (OMPE)—that (i) enforce receiver correctness, (ii) support an offline sender after setup, and (iii) achieve robustness against malicious receivers and malicious servers under honest-majority assumptions. Our approach reduces each primitive to a distributed scalar-product core combined with a \emph{distributed vector-validation} (DVV) mechanism that prevents unauthorized linear-combination leakage while preserving privacy. We prove unconditional privacy and robustness in the semi-honest setting and extend the guarantees to the malicious-server setting, tolerating up to $c < D/4$ or $c < D/3$ corrupt servers depending on the variant. The constructions are modular, require only lightweight client work (sharing and reconstruction), and allow the sender’s one-time upload to serve multiple, independent receivers without further interaction. We analyze the round and communication complexity of our protocols and provide empirical evidence of practical efficiency. The mediated setting naturally fits privacy-preserving services such as collaborative filtering, distributed constraint optimization, voting, and federated analytics. Collectively, our results show that distributed mediation yields simple, scalable, and unconditionally private realizations of core two-party MPC functionalities.