# Multi-secret sharing (Packed secret sharing) - Some questions

In the publication - "Communication complexity of secure computation", I have encountered a small problem - on page 5 of the literature under the heading "Theorem 1" they have described a $$(c,d; k,n)$$ multi-party secret sharing scheme.

Here, $$d$$ denotes the minimum number of parties that must come together to recover the secret, $$k$$ denotes the number of secrets, $$n$$ denotes the number of parties and $$c$$ denotes the maximum number of parties who together cannot gain any further information about the secret by collaborating.

I quote the text when it describes a $$(t - k + 1, t + 1, k , n)$$ multi-secret sharing scheme - (note $$k \leq t< n$$).

Theorem 1: There is a $$(t– k+ l,t + 1; k,n)$$- multi-secret sharing scheme to share $$k$$ elements of a finite field $$\mathbb{F}$$ among $$n$$ players, with $$k < n,$$ where each multi-share is a single element of F.

Proof: Let $$S_1, \ldots,S_k$$ be the Dealer’s secrets. Assume that $$a_l,....,a_k$$ and $$e_l,....,e_k$$ are pre-selected elements of $$\mathbb{F}$$ that are known to the Dealer and all $$n$$ players.

A generalization of Shamir’s secret-sharing scheme suffices. In the Distribution Phase, each player $$i$$ receives the multi-share $$p(a_i),$$ where $$p(x) \in F[x]$$ is an otherwise random degree $$t$$ polynomial such that $$p(e_i) = S_i, 1 \leq i \leq k.$$
More specifically, $$p(x) = q(x) \prod_{i = 1}^{k}(x – e_i) + \sum_{i = 1}^{k}S_i L_i(x),$$ where $$q(x)$$ is a completely random degree $$t – k$$ polynomial, and where $$L_i(x)$$ is the Lagrange polynomial.

i. I seem to only see the $$k$$ multi-shares distributed to k out of n parties. Is this understanding of mine incorrect? What is the role of the other $$(n-k)$$ parties?

ii. Are there any further resources online that I could refer to for such multi-secret sharing schemes? (preferably not academic literature as I'd like to work through some examples.)

• Write the question more clearly please, defining the symbols you use. Oct 23, 2018 at 0:31
• Hi, thanks for the feedback - I've tried to improve the same - do let me know if this is more sensible and clear than before! Oct 23, 2018 at 6:57
• You might need to quote a bit more context. Without reading the (paywalled) paper, I can't really tell what the other parties might be doing. It could even be that the $1 \le i \le k$ is just a typo, and it should read $1 \le i \le n$. Oct 23, 2018 at 11:01
• Hi, thanks for that - just realized that I have access to it because of my university account - I have updated the same to include some more text! Oct 23, 2018 at 18:06
• Editing the question for more readability, with LaTeX, just use  outside the expressions for proper typesetting. Oct 24, 2018 at 9:14

I believe there is a typo in the paper: instead of $$k$$ elements $$a_1, \dots, a_k$$ there should actually be $$n$$ fixed public elements, i.e. $$a_1, \dots, a_n \in \mathbb F$$. To secret-share, first determine $$p(x)$$ based on the dealer's secrets. Then, give $$p(a_i)$$ to player $$i$$ for each $$1 \leq i \leq n$$.
From your quote, I get that ALL participants receive $$p(a_i)$$ where $$p$$ itself depends on the $$k$$ multishares. Therefore, ALL participants receive some information.