Hi, I encountered question 4 in 2010B and found it very difficult (regarding t out of n sharing using CRT)
I couldn't understand how any t out of n participants will restore the same S each time, using only CRT.
Thanks,
Gal
Spoiler alert:
The question seems to have proper guidance.
- To guarantee reconstruction it is enough to have $(\min p_i)^{t}$>2M$.
- To guarantee that the secret isn't determined by any $t-1$ participants it is enough to have $(\max p_i)^{t-1}$<M/2$.
Make sure you understand why.
I guess that it follows from the CRT property that
"there is a unique integer x<product(n1,n2,…)"
but why is it guaranteed that any t (or more) participants trying to reconstruct the secret will reach the same S ?
I mean , let's consider we have 4 participants
and each one is given S mod pi
S mod p1, S mod p2, S mod p3 , S mod p4
and consider t=2;
so if 1 and 2 were to reconstruct the secret
we know that there is a unique integer x1 such that
x1= S mod p1, x1= S mod p2
and, if 3 and 4 were to reconstruct the secret
and we know that there is a unique integer x2 such that
x2 = S mod p3, x2 = S mod p4
but why does x1 = x2 ?
One thing that bothers me in this question is that there's no real "hiding". for example if one participant is evil enough, he can just take S without applying the mod function. Or even just use some really big numbers in order to overcome the condition we have specified in the above.
Do I miss anything with the definitions given in the question?