I'm learning (well, reading about and struggling to comprehend) a variant of Shamir Secret Sharing that goes like this:
Luckily, Shamir’s scheme can be generalised to what we’ll called the packed scheme, which removes this last constraint. Now, instead of picking a random polynomial such that $f(0) = x$, to share a vector of $L$ secrets $x = [x1, x2, …, xL]$, we pick a random polynomial such that $f(-1) = x1$, $f(-2) = x2$, …, $f(-L) = xL$, and like before use $f(1)$, $f(2)$, …, $f(N)$ as the shares.
I was wondering how would one go about contriving a polynomial under those constraints.
One naive way to do it, would be choosing the other points (or shares) randomly, and then interpolate all these points, more precisely:
If you want a polynomial of degree k and you have to share L secrets(L$<$k), then you choose k-L+1 other points (or shares) at random. You will have L+(k-L+1) points which you can interpolate to obtain P (the polynomial of degree k interpolating these points) and choose the rest of the shares using P.