Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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}$?

share|improve this question

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.