0
$\begingroup$

So for an unknown number of parties $x$, I make $x-1$ random $n$-bit strings represented by {$r_1, r_2,...,r_{x-1}$}. Where $s$ is the complete string split up between $x$ parties (yes?).

I then send each party one of the fragments $s_i$, so party 1 would get $s_1$, party 2 would get $s_2$ etc. all the way through to $s_{x-1}$. Along with these fragments. I then send $r_1⊕...⊕r_{x-1}⊕s$ to party $x$.

The message $s$ can then be reconstructed by XORing all the fragments together. Any singular $x-1$ party should not have enough information to reconstruct a message. But then what happens if there are only two parties? if $x=2$, then the message $s$ would be divided between $x-1=1$, which means that that singular party would acquire the entire $n$-bit string on their own, or am I over looking something that prevents this so that any $x-1$ party does infact not have enough information to reconstruct the message, even if it was only 1-bit ($n=1$) in length?

What about if 3 parties share two keys $a,b$? Assuming their fragments are $f_j$ for $a$ and $g_j$ for $b$ (that is these are $r_j$ fragments, and party 1 has $g_1$ and $f_1$, party 2 has $g_2$ and $f_2$ etc), could they manage to derive the secret if each party makes $z_j=f_j⊕g_j$, using the $z_j$ values of each?

$\endgroup$
  • $\begingroup$ Why do you send the x-or part? $\endgroup$ – kelalaka Oct 22 '19 at 8:48
  • $\begingroup$ Final party has the method $\endgroup$ – Anan Oct 22 '19 at 9:21
  • $\begingroup$ In the last paragraph, "Assuming their fragments are $f_j$ for $a$ and $g_j$ for $y$" , should be $g_j$ for $b$? $\endgroup$ – Changyu Dong Oct 22 '19 at 9:24
  • 1
    $\begingroup$ You really should use one notation for your shares. Right now, you have $r_i, s_i$ for the entire strings and then use $f$ and $g$ in the last paragraph.Also, you initially write about sharing a key in the title, and then all of a sudden you share a message. $\endgroup$ – tylo Oct 22 '19 at 11:25
  • $\begingroup$ s is the message, r is a fragment of s, f and g are defined unique variants of r $\endgroup$ – Anan Oct 22 '19 at 11:35
0
$\begingroup$

So for an unknown number of parties $x$, I make $x-1$ random $n$-bit strings represented by {$r_1, r_2,...,r_{x-1}$}. Where $s$ is the complete string split up between $x$ parties (yes?).

I then send each party one of the fragments $s_i$, so party 1 would get $s_1$, party 2 would get $s_2$ etc. all the way through to $s_{x-1}$. Along with these fragments. I then send $r_1⊕...⊕r_{x-1}⊕s$ to party $x$.

That is not how it is typically done. One issue is that two parties (say, party 1 and party $x$) get partial information of the shared secret, that is, the part that was masked by $r_1$.

Instead, what we do is make $x-1$ random strings (each as long as the secret $s$). Then, we send party 1 the string $r_1$ (not $s_1$), party 2 would get $r_2$, etc. And then send $r_1 \oplus r_2 \oplus ... \oplus r_{x-1} \oplus s$ to party $x$.

This can be seen to yield no information about $s$ to any $x-1$ parties, and still makes $s$ recoverable to someone with all $x$ shares.

Studying this version of the protocol may answer your questions.

|improve this answer|||||
$\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.