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.
Boolean circuits are Turing complete and so the answer is yes for any computation. Specifically, for this case, the circuit will assume that the loop never exits early (and if it finishes early, then the circuit will not change the result). In general, if you need to compute a branch in a circuit, then the circuit will always have both branches.
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$.
