1
$\begingroup$

Suppose that $y$ is a uniform random variable that is defined over the field (or group or abelian group) $Y$. Let us suppose that there are $N=\{1,2,\cdots,i\cdots,N\}$ agents and only one of them, say $i$, knows the random variable $y$. She wants to share the secret with the other $|N|-1$ players. So we could assume that player $i$ could find $x_1,x_2,\cdots,x_{K}$, where $K=|N|-1$, i.i.d uniform random variables over the space $Y$ and $a_1,a_2,...,a_k$ non_zero constants such that the $$\sum_{j\neq i}^Na_jx_j=y?$$

So every player $j=-i$ would know the part a_jx_j and only if all of them make a cross communication and calculate $a_1x_1\oplus_Ya_2x_2\oplus_Y\cdots\oplus_Ya_kx_k$ then all together will learn $y$. Could this be a secret sharing scheme, where the uniform random variable $Y$ could be written as a linear combination of a family of i.i.d. uniform random vectors that also belong to $Y$?

If my idea is not how could someone enrich it so as to become complete and a multiparty computation will need to be applied so as the players would obtain the secret $y$ only if they contribute all of them their private information that they got from the agent $i$?

What could be the weakness of such a scheme and how could we confront it? Does this have bounds?

P.S. i dont know if it is necessary to write the calculation in the following way

$$(a_1\otimes_Yx_1)\oplus_Y(a_2\otimes_Yx_2)\oplus_Y\cdots\oplus_Y(a_k\otimes_Yx_k)$$

$\endgroup$

1 Answer 1

2
$\begingroup$

Have you looked at Shamir secret sharing?

For your case, it seems like all $K$ players are required to reconstruct $y$. I think this is true because if a single player $j$ decides not to share their value $a_jx_j$, then the players would add up their values and get:

$$ \sum_{i\neq j,i=1}^K a_ix_i = y - a_jx_j$$

Since $a_jx_j$ is (hopefully) uniformly random, this gives them no information about $y$.

It looks like you've included player $i$, who knows the value $y$ directly, in the set of players. From the above, this means all players need to cooperate, including player $i$, to recover $y$. But if all players decide to cooperate, they don't need any secret shares, since player $i$ has the secret value. Instead of using a secret sharing scheme, player $i$ can send nothing at first, and then when they all agree to recover the secret value $y$, then player $i$ can just send everyone the value $y$.

Shamir secret sharing can give you a $t$-out-of-$K$ scheme, so that player $i$ can compute values $x_i$ to give to every player, such that if at least $t$ players cooperate, those players can compute values for $a_i$ so that the sum of $a_ix_i$ for all cooperating players will equal $y$.

Shamir secret sharing with $t=K$ looks very similar to what you've described, the only difference being that there is no $a_i$ and the $x_i$ are allowed to be $0$. For this scheme, you would choose uniformly random $x_i$ to for all $i$ except $i=K$. Then set

$$ x_K = y - \sum_{i=1}^{K-1}x_i$$

Then any set of $K-1$ secret values are uniformly random and independent of $y$, which basically the best security guarantee you can hope for.

From these values of $x_i$, if you want the scheme to resemble your original proposal, you could pick a random non-zero $x_i'$, and set $a_i = x_i'^{-1}x_i$. In fact, each player could do this themselves, so it will not change security. But I don't see what functionality it gives you.

$\endgroup$
5
  • $\begingroup$ I explicitly write that player $i$ has a secret who wants to share it with the others. Player $i$ just sends a part of her secret to the rest of the players. I do not say that he also takes part in the calculation of the secret. Isn't that obvious? $\endgroup$ Jan 7, 2022 at 9:46
  • $\begingroup$ Yes, I've seen the Shamir's secret sharing scheme but to my opinion I want something simpler that resembles is somehow. You ask me about what functionality $a_i$ gives, well maybe it would be betted if I write $\sum_j a_js_i$, namely that player $1$ will obtain $a_1$ part of $s_i$, player $K$ takes the part $a_k$ of $s_i$ etc $\endgroup$ Jan 7, 2022 at 9:52
  • $\begingroup$ If player $i$ isn't taking part, then the second half of my answer still makes sense (assuming there are $K$ players besides player $i$). But $K$-out-of-$K$ SSS already gives you information-theoretic security and can even be used directly in MPC for any linear operation. What do you actually want to do that needs the extra pieces $a_j$ and $s_i$? $\endgroup$
    – Sam Jaques
    Jan 7, 2022 at 9:57
  • $\begingroup$ So your point is that I could write in a simply way that $y=\sum_{j\neq i}^Kx_j$ and if all $j$ players communicate each other their part $x_j$ of the secret then they will learn the $\sum_{j\neq i}^Kx_j$ which is what I want. Furthermore, If I use some extra parameter like $a_j$, then these a_j could have also some use or interpretation in the sense that some players take $a$ and some others take $x$ and at the end of the day the combination of all $a_j*x_j$ will give the secret? $\endgroup$ Jan 7, 2022 at 10:04
  • $\begingroup$ ok i will write a new post and will ask for a specific shceme that could be secure $\endgroup$ Jan 7, 2022 at 10:44

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.