Paper 2024/009

Distributed Protocols for Oblivious Transfer and Polynomial Evaluation

Abstract

A secure multiparty computation (MPC) allows several parties to compute a function over their inputs while keeping their inputs private. In its basic setting, the protocol involves only parties that hold inputs. In distributed MPC, there are also external servers who perform a distributed protocol that executes the needed computation, without learning information on the inputs and outputs. Here we propose distributed protocols for several fundamental MPC functionalities. We begin with a Distributed Scalar Product (DSP) protocol for computing scalar products of private vectors. We build upon DSP in designing various protocols for Oblivious Transfer (OT): k-out-of-N OT, Priced OT, and Generalized OT. We also use DSP for Oblivious Polynomial Evaluation (OPE) and Oblivious Multivariate Polynomial Evaluation (OMPE). All those problems involve a sender and a receiver, both of whom hold private vectors; the goal is to let the receiver learn the scalar product of those two vectors. However, in each of these problems the receiver must submit a vector of a specified form. Hence, a crucial ingredient in our protocols is a sub-protocol for validating that the receiver’s vector complies with the relevant restrictions, without learning anything else on that vector. Therefore, while previous studies presented distributed protocols for 1-out-of-N OT and OPE, our protocols are the first ones that are secure against malicious receivers. Our distributed protocols for the other OT variants and for OMPE are the first ones that handle such problems. In addition, while previous art assumed semi-honest servers, we present protocols that are secure even when some of the servers are malicious. Our protocols offer information-theoretic security and they are very efficient.