How to do division in secure multi-party computation (mpc)?

Question

In the practical application of secure multi-party computation, the operation of division is inevitable. But I don't know how to construct a division?

In order to make the problem more accurate and easy to understand and answer, the following three mainstream paths are used to directly benchmark specific algorithms to describe the problem. The three paths selected here are:

• Arithmetic modulo a prime；
• Arithmetic modulo $2^k$；
• Binary circuits.

Path 1: arithmetic module a prime, benchmarking SPDZ algorithm. Among the available papers at present, it seems that only the calculation methods of addition and multiplication are described. Addition is directly operated locally, and the multiplication method is calculated by beaver triple array. So, how should I do division? A more intuitive idea is to use the finite field $\mathbb{F}_p$ to calculate the inverse element of the divisor，such as finding the inverse $a^{-1}$ of a，then multiplying this inverse. The question is: how to calculate the inverse of a secret sharing [a]? What is the specific method here? Or is there any other way to do division without calculating the inverse?

Path 2：Arithmetic modulo $2^k$：benchmarking paper:"SPDZ 2k: Efficient MPC mod 2k for Dishonest Majority". What is confusing is that on modulo $2^k$, a ring is constructed instead of a finite field. That is, Fermat's theorem is no longer satisfied. On a finite ring, the elements in ring does not necessarily have an inverse. So, how should I do division?

Path 3：Binary circuits： There are two technical routes in Binary circuits: the technical route based on yao's garbled circuit and the technical route based on Boolean sharing (for example, GMW and tinyOT algorithms). For these two routes, can I divide as long as the corresponding circuit can be constructed? However, no relevant paper has been found to construct the circuit under division.

Answer 1

Path 1: there is a protocol which lets you perform division. Suppose you're given $[x]$ and you want to compute $[x^{-1}]$:

• Take a random element $[r]$
• $[y] \gets [r] * [x]$
• Open $[y]$ and obtain $y$
• If $y = 0$ then abort because you're dividing by 0
• $[z] \gets [r] * y^{-1}$
• Return $[z]$

This protocol will cost you one multiplication and one opening. If you have special preprocessing tuples like $([r], [r^{-1}])$ then you can do better.

Path 2: The answer to this part will depend on what you mean by division. If you're talking about division in the ring $Z_{2^k}$ then it would be undefined. But the purpose of computation in $Z_{2^k}$ is to emulate what a CPU would do, and the CPU division is more like a truncation. If it's truncation (division by a power of 2), then a protocols exists here in Figure 10 of https://eprint.iacr.org/2019/599.pdf.

Path 3: Yes, you need to essentially evaluate the division circuit for whatever number representation that you pick. For example, if you're using IEEE floating point arithmetic then you'll need about 82k AND gates (see page 10 of https://eprint.iacr.org/2021/054.pdf).