# Algorithm for computing modular inverse in MPC

Is there any known algorithm for calculating $$a^{-1} \pmod{q}$$, where $$q < p$$ and $$F_{p}$$ is the prime field of the MPC, in a linear secret sharing scheme ?

I have tried using the standard algorithm, in which the parties generate $$r$$, then run secure multiplication on shared values to get $$r⋅a$$ and open it, and then each local invert the result. Finally, each uses local scalar multiplication of their share of $$r$$ to get shares of $$a^{-1} \pmod{q}$$. However this doesn't work when the field of inverse is different from the MPC field.

• In general, working over different moduli is very challenging. I don't know of any way to do this... – Yehuda Lindell Nov 7 '18 at 12:11

In general: $$a^{-1} \equiv a^{\phi (q)-1} \pmod q$$ where $$\phi$$ is euler totient function. If $$q$$ is a prime, then $$\phi (q)=q-1$$ and thus $$a^{-1} \equiv a^{q-2} \pmod q$$.

• and how do we compute the remainder of $a^{q-2}$ mod $q$ when $a^{q-2}$ is an element of $F_p$ (not $F_q$)? – ngn Dec 5 '18 at 8:20

Recently a method of doing share conversions for generic field or rings has been done here. Basically this paper offers a solution of converting a sharing of $$a \in F_p$$ i.e. $$[a]_p$$ into a sharing of $$a \in F_q$$ i.e. $$[a]_q$$.

How? Generate some random bits $$[b]_p, [b]_q$$ which are the same in both fields - using cut and choose. To go from $$[a]_p \rightarrow [a]_q$$ do the following:

1. Mask your input with $$\log{p}$$ random bits and set $$m \leftarrow \mathsf{Open}\big( [a]_p - \sum_{i=0}^{\log{p}}2^i[b_i]_p \big)$$.
2. Take $$m$$ as public input to your $$F_q$$ sharing algorithm and perform the subtraction modulo $$p$$ but this time in $$F_q$$ using the double shared random bits. More formally, compute $$[a]_q \leftarrow \big( m + \sum_{i=0}^{\log{p}}2^i[b_i]_q \big) \bmod p$$.

There is a caveat though. In order to get the right amount of statistical security and have the opened values look uniformly random you need $$p$$ and $$q$$ to be close to a power of $$2$$.

To answer your question, just convert $$[a]_p \rightarrow [a]_q$$ and then do the inversion of $$[a]_q \rightarrow [a^{-1}]_q$$ as you described.