0
$\begingroup$

i would like to know why there is a problem of not using random x-coordinates in shamir secret sharing schemes.

I consider that after evaluating the points in a polynomial $f(x)$, the share is composed by: $(x, f(x))$, where the $f(x)$ is secret and the $x$ could be public. So, why i always find in some literature that it is a problem using not random x coordinates? Could i have an example of why is it a problem?

Associating the shamir scheme with ortogonal arrays (respecting the strength and lambda properties), i know that fixing the x-coordinates i am restricting the matrix to only the known columns and, consequently, we have a smaller matrix. But we still have the perfect privacy properties, because even knowing the x-coordinates, each secret appears exactly the same quantity of times for each t-tuple, where $t$ is the threshold. Therefore, even knowing the x-coordinates, i can not know anything about the secret.

$\endgroup$
  • $\begingroup$ $x$ public or given to share holders? $\endgroup$ – kelalaka Oct 26 '18 at 15:05
  • $\begingroup$ Normally they are given to the share holders, but i think it could also be public. $\endgroup$ – Rick Oct 26 '18 at 15:06
  • $\begingroup$ Yes, i agre, but shamir secret sharing scheme is unconditionally secure. Even reducing the search space, if you do not know enough information, you can not identify the correct secret. When using a prime that is big enough, there would be many possibilites. $\endgroup$ – Rick Oct 26 '18 at 15:11
  • $\begingroup$ The random is the coefficients of the polynomial where $a_o = Secret\;to\; Share$ $\endgroup$ – kelalaka Oct 26 '18 at 15:15
  • $\begingroup$ Exactly. We need that the coeficientes of the polynomial $f(x)$ must be random. But the x-coordinates that are going to be used to evaluate the polynomial? Can i just use $\{1, 2, 3, 4, \ldots\}$ ? Is there any risk doing that? I just want to know if there is concrete problem doing that. $\endgroup$ – Rick Oct 26 '18 at 15:20
1
$\begingroup$

i would like to know why there is a problem of not using random x-coordinates in shamir secret sharing schemes.

There is no such problem.

The only requirements on the $x$-coordinates are:

  • They're all in the range $(1, p-1)$ (or $p^k - 1$ if you're using the extension field $GF(p^k)$; you can't use 0 as a coordinate (as $f(0)$ is the secret), and you can't you values outside the range.

  • They're distinct (if they're not, then the two shares with the same $x$ coordinate are the same share).

ANy arbitrary set of $x$-coordinates that meet these two requirements work just fine.

So, why i always find in some literature that it is a problem using not random x coordinates?

I suspect that you are misinterpreting the literature. For the coefficients of the secret polynomial $f(x)$, it is necessary that the non-constant terms be random; if they are not, then it is possible for a small group to recover the secret.

There is no corresponding requirement on the $x$; they can be any values you find convenient (as long as they meet the above two requirement)

| 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.