Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question

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.

share|improve this answer
2  
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 at 14:20
    
MPC [thinking] Oh yes, Multi Party Computation. –  fgrieu Jan 24 at 14:33
1  
@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 at 17:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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