Shamir's Secret Sharing of modular inverse

Question

Given a secret $K \bmod q$ which is shared among entities $E_1,…,E_n$ using polynomial Shamir's Secret Sharing, how can the inverse of $k$ be shared without revealing $k$ and $k^{-1}$?

Answer 1

I'm assuming $q$ is prime.

Note that $k^{-1}\equiv k^{q-2}\bmod{q}$.

We can compute $k^{q-2}\bmod{q}$ via a multiparty computation protocol such as the one outlined in this paper ($\S3.1)$. Or, since $q$ is likely a public parameter, you can even do the simple square-and-multiply algorithm (for example, VIFF provides this capability).

You might also be able to compute the modular inverse via the extended euclidean algorithm implemented using general MPC techniques. The reason I say might is that the extended euclidean algorithm does have a conditional branch in it. While this is technically not a problem for MPC, it could leak information in the real world that you wouldn't want to leak.

Answer 2

All this happens in your prime field q:

1. Use a secure DKG algorithm to distribute shares of a random number
2. Each party computes secret_share[i] * dkg[i]
3. Use a secure degree-reduction protocol (aka: redistribution) on those shares
4. Each can then reconstructs secret_share * dkg == SD
5. Each can then compute inverse(SD) * dkg[i], which are shares of the inverse

You should be very aware that this protocol is protected solely by the quality of the random numbers used, and the correctness of the DKG.

(Also, it's been tested and works fine)