# Shamir Secret Sharing Modular Reduction

Say players use Shamir's secret sharing to share a value $k$ such that each player now holds $k_i$, a share of $k$. How can they securely compute $k \bmod m$ for some $m$.

Of course they can interpolate to get $k$ and then reduce it $\bmod \hspace{2pt} m$. But how can they perform some operation on their shares to obtain shares of $(k \bmod m)$ without revealing $k$?

-

First note that using MPC we can compute addition, subtraction, multiplication and division (multiplication by the inverse) on shares. It turns out there are also secure protocols out there for doing comparison (see http://viff.dk and their references).

So we could simply do something like this:


while k >= m:
k = k-m


$m$ could be public or secret shared.

This will be fairly slow if $k$ is large and $m$ is small. As poncho points out, someone learning $k\bmod{m}$ and the number of iterations of the loop will be able to recover $k$.

This could be mitigated by always running the loop the same number of times and using $t= (k>=m)$ (where $t$ takes on $0$ or $1$ accordingly) then doing $k=k-(t)m$. This has obvious limitations so it will depend on the situation as to whether or not this will be acceptable (note that we can upper bound the number of iterations if both $m$ and the order of the field used in Shamir are known).

There are more specialized protocols that would be faster and may solve the problem poncho pointed out.

-
I believe the idea is that recover $k \bmod m$ without anyone being able to learn more about $k$. If so, it doesn't quite work; someone learning $k \bmod m$ and the number of iterations we went through the above procedure can easily rederive the original $k$ value. –  poncho Jan 24 '14 at 14:20
MPC [thinking] Oh yes, Multi Party Computation. –  fgrieu Jan 24 '14 at 14:33
@poncho, good point. I'll have to dive deeper into the protocol outlined in the paper I linked to see if it mitigates that. –  mikeazo Jan 24 '14 at 17:35