The first requires $\Oh(\ell)$ arithmetic operation on encrypted values (secure addition and multiplication) in $\Oh(1)$ rounds. This is the most efficient constant-rounds solution to date. The second protocol requires only $\Oh \left( (\log^2 \ell)(\kappa + \loglog \ell) \right)$ arithmetic operations in $\Oh(\log^2 \ell)$ rounds, where $\kappa$ is a correctness parameter. Theoretically, this is the most efficient solution to date as all previous solutions have required $\Omega(\ell)$ operations. Indeed, the fact that an $o(\ell)$ solution is possible at all is highly surprising.
Category / Keywords: cryptographic protocols / Secure two-party computation, Secure integer division, Constant-rounds, Bit-Length Publication Info: A shorten version can be seen in Proc. FC' 2012 Date: received 28 Mar 2012, last revised 21 Mar 2013 Contact author: mdahl at cs au dk, ttoft@cs au dk, ncnfl@mail tsinghua edu cn Available formats: PDF | BibTeX Citation Note: This is the full version of the paper which was accepted to FC 2012. Version: 20130321:113606 (All versions of this report) Discussion forum: Show discussion | Start new discussion