Welcome to the resource topic for 2012/164
Title:
On Secure Two-party Integer Division
Authors: 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.
ePrint: https://eprint.iacr.org/2012/164
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .