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


1 Answer 1


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.

  • 2
    $\begingroup$ 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. $\endgroup$
    – poncho
    Commented Jan 24, 2014 at 14:20
  • $\begingroup$ MPC [thinking] Oh yes, Multi Party Computation. $\endgroup$
    – fgrieu
    Commented Jan 24, 2014 at 14:33
  • 1
    $\begingroup$ @poncho, good point. I'll have to dive deeper into the protocol outlined in the paper I linked to see if it mitigates that. $\endgroup$
    – mikeazo
    Commented Jan 24, 2014 at 17:35

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.