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$
6
  • 1
    $\begingroup$ Write the question more clearly please, defining the symbols you use. $\endgroup$
    – kodlu
    Oct 23, 2018 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$ Oct 23, 2018 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$ Oct 23, 2018 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$ Oct 23, 2018 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, 2018 at 9:14

2 Answers 2

2
$\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$
1
  • $\begingroup$ Hi Mark, thanks for this! I was a bit unsure if this is a mistake! $\endgroup$ Oct 24, 2018 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 and acknowledge you have read our privacy policy.

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