Multi-Linear Secret Sharing vs. Shamir Secret Sharing

Question

I hope someone can help me. I read several papers including the original paper, "Multi-linear Secret-sharing Schemes," by Beimel et al., and watched the following video https://www.youtube.com/watch?v=3GFdp7V_yog but still struggling with the concept of multi-linear secret sharing scheme. I know that in LSSS, the secret is an element of a field, and a dealer distributes shares to parties. Consequently, the parties can independently use linear mapping to recover the secret. I will use the same example in the video; a secret is shared in field, F_2, and the matrix is as follows:

My questions are:

1. The first and the second rows of the matrix are labeled to the same party, ie P_2, but how can you give different shares to the same party?
2. Only P_2 and P_4 can recover the secret because when they combine their shares, the r_2, r_3, and r_4 gets canceled, But P_2 already has r_2 in two different rows. What is the difference between row 1 and row 2?
3. what is the difference between Shamir's secret sharing and multi-linear secret sharing.

Thank you

Answer 1

I'm not an expert but I will try to answer from my understanding.

1. LSS allows you to divide the secret to many shares and it does not limit you to give only one share to a person. In the example you have given, the secret is divided into 5 shares and gave to 4 people. In this case, P_2 receives 2 shares.

2. Having r_2 in two different rows doesn't help much in this case because there are other terms to help hiding the secret. You can treat both row as a different share of secret. In this case, it is hold by the same person P_2.

3. The above example is Linear Secret Sharing, where the reconstruction of the secret come from the linear algebra operation from the matrix used. Multi-Linear Secret Sharing is like an extension to LSS by hiding more than one secret at the same time and use the similar algorithm to reconstruct the secret.

Shamir Secret Sharing, on the other hand, rely on polynomial interpolation to reconstruct the hidden secret. Using the fact that d+1 points can interpolate degree d polynomial with Lagrange's Coefficient, we can assure that for d+1 shares can reconstruct the hidden secret. This is a good explanation video on SSS.