On Secure Two-party Integer Division

Morten Dahl; Chao Ning; Tomas Toft

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 $ℓ$ -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 arithmetic operation on encrypted values (secure addition and multiplication) in rounds. This is the most efficient constant-rounds solution to date. The second protocol requires only arithmetic operations in rounds, where is a correctness parameter. Theoretically, this is the most efficient solution to date as all previous solutions have required operations. Indeed, the fact that an 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 computation Secure integer division Constant-rounds Bit-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: 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},
      url = {https://eprint.iacr.org/2012/164}
}