2
$\begingroup$

MPC protocols have a harder time handling division (truncation) than multiplication. The case I am considering is when the divisor is a public value. Dividing it may lead to a wrong result due to wrapping around the ring, or we need to pay more cost to get a faithful result. But if the divisor is public, parties can compute its reciprocal offline and then multiply to the reciprocal at the online stage. Correct reciprocal can be computed since we do not care much about the offline overhead. Is there any problem with this solution?

$\endgroup$
0

1 Answer 1

0
$\begingroup$

If we are working modulo $p=99999999999999999989$ (which is prime), and divide $x=1000000$ by $d=7$ using the question's method $q\gets x\,(d^{-1}\bmod p)\bmod p$, we end up with $q=57142857142857285708$.

The mathematician is happy because $x=q\,d\bmod p$ , but the beancounter?

That said, the method does work to divide $x=999999$ or $x=7000000$ by $7$, and more generally if and only if $x$ is a multiple of $d$. So perhaps to divide $x$ by $d$ we can start from $x$ scaled such that $x$ is a multiple of any quantity $d$ that we might want to divide by later, and then the question's method is fine.

Should the multiparty computation support that, an alternative would be to limit the range of $x$ such that $0\le x<\lfloor p/d\rfloor$, and compute $\lfloor x/d\rfloor$ as $$q\gets\min_{j\in[0,d)}((x-j)\,(d^{-1}\bmod p)\bmod p)$$ which insures that $x=q\,d+j$ for some $j\in[0,d)$, making the beancounter happy.

$\endgroup$
2
  • $\begingroup$ Thanks for the reply! It really answers my question. If I understand correctly, the $d^{-1}(kd+j) \bmod p$ becomes a wrong number, where $kd+j=x$. The problem is caused by the extra term $j$? $\endgroup$
    – Zhengyi Li
    Dec 7, 2022 at 8:42
  • $\begingroup$ @ZhengyiLi: yes. The question's method of division of $x$ by $d$ only works (from the beancounter's perspective) when $x=kd$ for some $k$, and then returns $q=k=x/d$. $\endgroup$
    – fgrieu
    Dec 7, 2022 at 11:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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