Let $k \in \Z_p$ be a secret key shared among $\ell$ parties, where party $i = 1, 2, \dots, \ell$ receives a share $s_i = a i + k \bmod p$, for some randomly chosen and secretly kept $a \in \Z_p$ (fixed for all parties).
- Assume that $p$ large enough prime number. How many parties are needed to reconstruct the key $k$?
- Does $a$ need to be invertible modulo $p$? Answer with
yesorno.
Instead of using a large number $p$, one decides, due to hardware limitations, to use a small prime number $q$, a vectorized key $k \in \Z_q^m$, and shares $s_i = i a + k \bmod q$ for some randomly chosen vector $a \in \Z_q^m$.
- If $q^m > p$, is this approach at least as secure as the previous scheme? Answer with
yesorno. - What is the smallest $q$ that works for $\ell = 50$ parties?
- Is it necessary that $q$ and $p$ are prime numbers?
Submit the answer as a sequence like 1 yes yes 2 yes.