2
$\begingroup$

Shamir's secret sharing protocol generates a polynomial over a prime field $F_p$.

Is it possible to generates it over $Z_n^*$ as well?

The reason is that I want to combine a secret shared value in another scheme. For example sign on it with an RSA signature (that is over $Z_n^*$.

Thanks.

$\endgroup$

2 Answers 2

2
$\begingroup$

You actually have Shamir secret-sharing as long as you have interpolation, and you have interpolation for any ring $R$ as long as your evaluation points $\alpha_1,\ldots,\alpha_\ell$ satisfy the following condition:

For all $i\neq j$ it holds that $\alpha_i - \alpha_j\in R$ is a unit.*

The way you prove this is exactly the same as you prove it for the field case, the only thing you really need to do is to invert elements of the form $\alpha_i - \alpha_j$, thus the requirement.

For any ring of the form $\Bbb Z_{p\cdot q}$, you can find sequences with this property that are as long as $\min(p,q)$.

*A unit is an element with a multiplicative inverse.

$\endgroup$
1
  • $\begingroup$ Yes, a ring will do, and in this case it will work just fine as explained above. A footnote (just be cautious) that now secret sharing is operating over $Z_n$ rather than $Z_n^*$. If require strictly secret sharing over $Z_n^*$, the scheme needs to be multiplicative. $\endgroup$ Jun 1, 2018 at 11:35
1
$\begingroup$

If you just want to sign the shares like you said, then you don't need the shares to be in $Z_n^*$. You can just share over $F_p$ as usual. To sign a message, usually the message is hashed first and then the hash value is fed in the signing/verification algorithms. Therefore the fact that the shares are in $F_p$ will not affect signature generation and verification.

Shamir's secret sharing cannot be over $Z_n^*$ because $Z_n^*$ is not closed under $+$. But there are other secret sharing schemes over $Z_n^*$. As an example, the simplest one is this:

  1. to share a secret $s \in Z_n^*$, choose $r_1,\ldots,r_{t-1}$ uniformly at random from $Z_n^*$.Compute $r_0 = s\cdot \frac{1}{\prod_{i=1}^{t-1} r_i}$.
  2. Now you have $t$ shares $r_0,\ldots,r_{t-1}$, and you can distribute them to $t$ parties.
  3. To reconstruct the secret, multiply all shares together and you get the secret $s=\prod_{i=0}^{t-1} r_i$.
$\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.