**On Secure Two-party Integer Division**

*Morten Dahl, Chao Ning, Tomas Toft*

**Abstract: **We consider the problem of {\it secure integer division}: given two
Paillier encryptions of $\ell$-bit values $n$ and $d$, determine an
encryption of \intdiv{n}{d} without leaking any information about
$n$ or $d$. We propose two new protocols solving this problem.

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 16 Oct 2015

**Contact author: **ncnfl at 163 com

**Available format(s): **PDF | BibTeX Citation

**Note: **Extending the bit-length protocol to base-m and hybrid-base digit-length protocol.

**Version: **20151016:230655 (All versions of this report)

**Short URL: **ia.cr/2012/164

[ Cryptology ePrint archive ]