# computing INV in boolean circuit for MPC

Is it feasible to generate an efficient MPC function that compute $a^{-1}$ for $a \in \mathbb{F_q}$, with Boolean circuit?

The naive way seems impossible since the depth of the computation might needed to be known in advance. (for example in computation of Extended GCD).

Edit: my intentions for the question were: Is there a more way to compute inverse instead of using EGCD (i.e a similar way to compute the INV that is more suitable to transfer to MPC)

Thanks.

If your question is about efficiency, then there may be more efficient ways to compute this than in a circuit. For example, use MPC to compute $r\cdot a$ where $r$ is an unknown random value. Then, the parties compute $b=(r\cdot a)^{-1} \bmod q$, and then securely compute $r \cdot b$. This result is $a^{-1} \bmod q$. There are many ways to do this, using homomorphic encryption (e.g., Paillier), OT and so on. However, the main challenge is to prevent cheating, if you want malicious security. It also depends if you are looking at the honest majority or dishonest majority setting. For an honest majority, one just uses standard techniques to generate a secret sharing of $r$. The parties then run secure multiplication on shared values to get $r\cdot a$ and open it, and then each local invert the result. Finally, each uses local scalar multiplication of their share of $r$ with $b$ to get shares of $a^{-1} \bmod q$.