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.

  • 3
    $\begingroup$ In general, working over different moduli is very challenging. I don't know of any way to do this... $\endgroup$ – Yehuda Lindell Nov 7 '18 at 12:11

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

  • $\begingroup$ and how do we compute the remainder of $a^{q-2}$ mod $q$ when $a^{q-2}$ is an element of $F_p$ (not $F_q$)? $\endgroup$ – ngn Dec 5 '18 at 8:20

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.


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.