Paper 2012/164

On Secure Two-party Integer Division

Morten Dahl, Chao Ning, and 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.

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

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. A shorten version can be seen in Proc. FC' 2012
Keywords
Secure two-party computationSecure integer divisionConstant-roundsBit-Length
Contact author(s)
ncnfl @ 163 com
History
2015-10-16: last of 3 revisions
2012-03-29: received
See all versions
Short URL
https://ia.cr/2012/164
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/164,
      author = {Morten Dahl and Chao Ning and Tomas Toft},
      title = {On Secure Two-party Integer Division},
      howpublished = {Cryptology ePrint Archive, Paper 2012/164},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/164}},
      url = {https://eprint.iacr.org/2012/164}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.