Score:0

Secret sharing questions

ua flag

I would like to make a few questions about Shamir's secret sharing scheme and. To begin with, I am starting with the next theorem that determines the intuition of the whole theorem.

$\textbf{Theorem:}$ Let $p$ be a prime, and let $\{(x_1,y_1), . . . ,(x_{t+1},y_{t+1})\}\subseteq\mathbb{Z}_p$ to be a set of points whose $x_i$ values are all distinct. Then there is a unique degree-$t$ polynomial $f$ with coefficients from $\mathbb{Z}_p$ that satisfies $y_i \equiv_p f(x_i)$ for all $i$ (I would add to the theorem where $s=f(0)$).

As we already know in a $k$ out of $n$ secret sharing scheme, each agent splits the secret in $n$ parts however only $k=t+1$ parts (of a polynomial of degree $t$) are needed if we want to compute the secret. Suppose that $f$ is the polynomial function such that

$$f(x)=a_tx^t+a_{t-1}x^{t-1}+\cdots+a_1x+a_0=s+\sum_{i=1}^ta_ix^i,\quad\text{such that $y_i \equiv_p f(x_i)$ and $s=f(0)$}\quad (1)$$

  1. When we say that a dealer shares the secret does this mean that every player takes a pair of $(x_i,f(x_i))$ such that $y_i \equiv_p f(x_i)$ from the $n$-pairs, namely $i=1,2,3...,n$? If we have more pairs of points of those needed by the theorem to construct the polynomial function $(1)$ what becomes with the rest of them? I don't get it.
  2. All these $t+1$ pairs are chosen randomly to reconstruct the secret in the reconstruction phase or they collude? Could anybody show the mathematical formulations form the point that $f$ is chosen to the reconstruct $s$ based on the theorem?
Score:1
sa flag

If you want $k$ users to be able to reconstruct $s$ and no smaller number of users to be able to learn anything about the secret, you must have a polynomial $f$ of degree $k-1.$

The dealer gives exactly one share $(x_i,f(x_i))$ to user $i,$ for $i=1,2,\ldots,n$.

That is all that user gets. It doesn't really matter which user gets which share.

As long as $p-1\geq n,$ $n$ users can be supported. Let $S=\{x_1,\ldots,x_n\}$ be the points that determine the currently used shares.

The "leftover shares" can be used later if new people join, so it may not be a bad idea to have $p$ appreciably bigger than $n,$ the current number of users.

Note that we assume that the dealer is a trusted third party and that the users will actually supply the correct share when asked by the dealer, otherwise things won't work, and more sophisticated schemes are needed.

This also applies if $k$ users can themselves get together to reconstruct, they must not lie about their shares and if exactly one of $k$ users is dishonest, he/she can learn the shares of the rest of the users, which means the rest cannot compute the secret correctly but he/she can if the remaining $k-1$ users are honest.

Score:-1
ua flag

Although I am not sure for this and this is not a complete asnwer and I hope if anybody sees what I am writing he/she could verify it, If the players are $n$, the $(k,n)$ secret sharing scheme means that I will split $s$ in $n$ parts, such that the polynomial $f$ is a polynomial function of degree $t$ that takes as input $s$ and the $t$ and with the process $y_i\equiv_p f(x_i)$ gives back t+1 pairs. In equivalent terms

$$\left\{f(s,t)|\text{$s=f(0)$ and $y_i\equiv_p f(x_i)$ for $i=\{1,2,...,t+1\}$}\right\}$$

But thre rest of the splitting parts of $s$ that are accounted to be $j=n-(t+1)$ where $t<2n-1$ I do get it also how are they used. I mean there is a reason behinf it...that I can not figure it out....

Hunger Learn avatar
ua flag
This is just a comment. It was just too big to fit in comments. This is not an answer. I hope it is helpful somehow...
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.