Secret sharing using CRT

Secret sharing using CRT

Gal (guest) 18 Jan 2014 14:25

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

Re: Secret sharing using CRT

nbitansky 18 Jan 2014 15:58

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.

guyb (guest) 19 Jan 2014 08:44

hi nir,
why is the min value in the first bullet is 2M and not M?
the secret is between M and 2M, so i thought the product should be at least the size of the gap (2M-M)

thanks

nbitansky 19 Jan 2014 09:27

Yes, the condition I stated is not tight, it is just a straightforward sufficient condition that doesn't exploit the lower-bound on the size of $S$. Your condition is definitely sufficient and also tight!

Gal (guest) 18 Jan 2014 17:19

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 ?

Gal (guest) 18 Jan 2014 17:22

never mind, I think i got it

nbitansky 18 Jan 2014 17:27

Each large enough set $T$ of participants corresponds to some product $P_T$, and it is guaranteed that $S<P_T$, so $S \mod P_T$ is the same as $S$ itself.

Aviv (guest) 19 Jan 2014 10:30

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?

nbitansky 19 Jan 2014 11:31

We only defined secret sharing for an honest dealer. The participants never get $S$ itself, but only their share $S \mod p_i$.