1
$\begingroup$

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.)

Thanks very much in advance.

$\endgroup$
  • 1
    $\begingroup$ Write the question more clearly please, defining the symbols you use. $\endgroup$ – kodlu Oct 23 '18 at 0:31
  • $\begingroup$ 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! $\endgroup$ – Rahul Mathur Oct 23 '18 at 6:57
  • 1
    $\begingroup$ 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$. $\endgroup$ – Ilmari Karonen Oct 23 '18 at 11:01
  • $\begingroup$ 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! $\endgroup$ – Rahul Mathur Oct 23 '18 at 18:06
  • 1
    $\begingroup$ Editing the question for more readability, with LaTeX, just use $ $ outside the expressions for proper typesetting. $\endgroup$ – kodlu Oct 24 '18 at 9:14
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Hi Mark, thanks for this! I was a bit unsure if this is a mistake! $\endgroup$ – Rahul Mathur Oct 24 '18 at 15:04
1
$\begingroup$

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.

Somehow the information on the multishares is "spread-out" by the polynomial.

$\endgroup$

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.