Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

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.