It is very straight-forward and intuitively to achieve addition, subtraction and even generalized polynomial using Beaver's Multiplication Triples. However division seems difficult to achieve on two secret-shared values (each with precision $f$).

Assuming the case of secure two-party computation, there are two secret values

$$[a]\leftarrow\{0,1\}^n, [b]\leftarrow\{0,1\}^n$$

And we want to securely compute

$$c= \Bigl\lfloor\dfrac{a}{b}\Bigr\rfloor$$

where $c$ is an integer.

So my question is : How to design a such division protocol, or is there any papers? Thanks a lot.


There exists a number of general multiparty protocols that can securely compute any function. Some of these, for instance SPDZ and this one, use Beaver triples. These protocols can compute integer division, since integer division is a function.

However, using general multiparty protocols may not be the most practical or efficient. So there has also been some research in specialized protocols for integer division. There is e.g. a paper describing a secure two-party protocol for integer division here. The "related work" section in that paper contains references to other integer division protocols for more than two parties. I'm not sure any of these protocols use Beaver triples, though.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.