0
$\begingroup$

A proposed secret sharing scheme: Suppose that $p:S\times Y\to X$, with $|Y|\geq|S|$ is a cipher where, $y\in Y$ is the key and $x\in X$ the code, $p$ is bijective, namely $(x,y)$ is associated with only one $s$. Hence the decrypted message $s=x\oplus y$ and it is easy to proove it.

$\textbf{Proof:}$ Suppose that we have a mechanism of communication $\mathcal{M}=(p,d)$ such that $\mathcal{M}$ is defined over $(Y,S,X)$, where $Y$ is the key, $S$ the message and $X$ the cipher spaces respectively. To simplify the problem even more I assume that $Y=M=L=G$ where $G$ is an arbitrary finite field.

$$p(y,s)=x,\quad\text{is the encrypted message, which by definition equals $x$}$$

$$h(y,x)=s,\quad\text{is the decrypted message, which by definition equals $s$}$$

So, indeed $(y,x)$ is defined to be associated with only one $s$ and hence $p(y,\cdot)$ is bijective by definition. To answer the question how are they associated, when someone knows both $x$ and $y$, then indeed $x\oplus_{G} y=s$

In order to decrypt the message we have that

$$d(y,x)=d(y,g(y,s))=y\oplus_G x=s$$

where $\oplus_{G}$ is the operation of $+$ as it is defined in the finite field $G$. And hence we have show that the calculation that you ask for, it holds by definition.

$\textbf{Proposed scheme:}$ Could I use the following sharing scheme here: Instead of sharing the secret $s$ I divide the key of the encrypted message by generating a cipher with $k$ keys and only if someone knows all the keys and the one code that is generated, then she will learn the secret $s$ - Let y be shared in $k$ shares such that $y=\sum_{i=1}^k y_i$ where as in Shamir's scheme every $y_i$ is random variable and all of them are independent and define another cipher $$p:S\times(\Pi_{i\in K}Y)\to X$$ such that the $k+1$-vector $\left(i.e. (s,y_1,y_2,\cdots,y_k)\right)$ is associated with one $s$ and hence the message is decrypted (namely reconstructed) only if all the players communicate and add their $k+1$ shares, namely $s=x\oplus\sum_{i=1}^ky_i=x\oplus y$

Is this scheme some well known scheme?

$\endgroup$
1
$\begingroup$

Is this scheme some well known scheme?

It appears to be the well known $(n,n)$ secret sharing scheme, using a group operation (note: you said a finite field; however since you never use the multiplication operation, it works just as well over any finite group [1]).

That is:

  • $n-1$ of the secrets are random group elements $r_i$

  • The last group element is $r_{n-1} = s - \Sigma_{i=0}^{n-2} r_i$

  • Given the $n$ shares $r_i$, the shared secret $s = \Sigma_{i=0}^{n-1} r_i$

It should be obvious that, with $n-1$ of the shares, you get no information about $s$.

This is a simple extension of the xor sharing scheme that was shown to you not too long ago; yes, it is well known.


[1]: It does work in nonabelian groups, but then you have to be careful about ordering, and in any case, we rarely use nonabelian groups in crypto.

$\endgroup$
5
  • $\begingroup$ I prefer the finite field assumption than the abelian group, however they seem to work perfect. In case qe do not work in abelian groups do you know what assumptions do we need? $\endgroup$ Jan 11 at 19:58
  • $\begingroup$ @HungerLearn: in the nonabelian case, we have (generating the last share) $r_{n-1} = -(r_0 + r_1 + ... + r_{n-2}) + s$ and (recovering the secret) $s = r_0 + r_1 + ... + r_{n-1}$ $\endgroup$
    – poncho
    Jan 11 at 20:41
  • $\begingroup$ Well I did not understand the difference... In this case we do not recover the secret? $\endgroup$ Jan 11 at 20:51
  • 1
    $\begingroup$ @HungerLearn: in nonabelian groups, we don't always have $a + b = b + a$; hence when adding terms up, we need to be careful about the ordering... $\endgroup$
    – poncho
    Jan 11 at 20:52
  • $\begingroup$ thanks ...my I forgot this :P $\endgroup$ Jan 11 at 21:19

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.