|
We study the design of efficient and private protocols for polynomial operations in the shared-coefficients setting. We propose efficient protocols for \emph{polynomial multiplication}, \emph{division with remainder}, \emph{polynomial interpolation}, \emph{polynomial gcd}, and a few other operations. All the protocols introduced in this paper are \emph{constant-round}, and more efficient than the \emph{general} MPC. The protocols are all composable, and can be combined to perform more complicated functionalities. We focus on using a \emph{threshold additively homomorphic public key scheme} due to the applications of our protocols. But, our protocols can also be securely computed in the \emph{information-theoretic} setting. Finally, we mention some applications of our protocols to \emph{privacy-preserving set-operations}.
|