Secure Distributed Computation of the Square Root and Applications

Abstract

The square root is an important mathematical primitive whose secure, efficient, distributed computation has so far not been possible. We present a solution to this problem based on Goldschmidt's algorithm. The starting point is computed by linear approximation of the normalized input using carefully chosen coefficients. The whole algorithm is presented in the fixed-point arithmetic framework of Catrina/Saxena for secure computation. Experimental results demonstrate the feasibility of our algorithm and we show applicability by using our protocol as a building block for a secure QR-Decomposition of a rational-valued matrix.