Why not substitute division of a public value by multiplication to its reciprocal?

Zhengyi Li

12/7/23, 7:17 AM

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?

1 + 0

multiparty-computation

Score:0

Crypto

fgrieu

12/7/23, 7:42 AM

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.

+ 2

Zhengyi Li

12/7/23, 8:42 AM

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

fgrieu

12/7/23, 11:14 AM

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

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Why not substitute division of a public value by multiplication to its reciprocal?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.