Algorithm for computing modular inverse in MPC

Question

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.

Answer 1

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$.

Answer 2

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.