3
$\begingroup$

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

$\endgroup$
0
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Assuming $secret\_share[i]$ as the initial shares? Then it should be $inverse(SD) * dkg[i]$. Also it should be mentioned that this requires $2*t + 1$ shares instead of $t + 1$. $\endgroup$
    – shumy
    Mar 6 '20 at 10:00
  • $\begingroup$ Thanks but why does it require 2T + 1? Degree reduction protocol should handle that right? $\endgroup$ Mar 7 '20 at 12:53
  • $\begingroup$ The reduction is the final result, but the first multiplication results in a polynomial of degree $2*t + 1$. $\endgroup$
    – shumy
    Mar 9 '20 at 20:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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