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: LSSS

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

  • $\begingroup$ I think you’re more likely to get help if you make your question as self-contained as possible by, for instance, defining the construction you’re considering explicitly $\endgroup$ – Daniel Feb 15 at 3:38
  • $\begingroup$ @Daniel. Thank you very much for your feedback. I edited my question. $\endgroup$ – Mona Feb 15 at 13:31

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.

  • $\begingroup$ Thank you very much! That's a great help! $\endgroup$ – Mona Feb 18 at 12:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.