1
$\begingroup$

I am trying to do a homework in which implement a variation of this paper and I don't know how to generate a polynomial of degree $m-1$. This polynomial is used to generate the $y_0$ and $y_1$ values.

I am using JCE for doing the coding. What do I need to do to achieve this?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

I assume you're referring to section 5 of the paper you linked to, which reads:

5 An instance using polynomials

In this section, we describe an instance of the technique of Section 4 using Shamir's secret sharing scheme [25]. In this scheme, $\mathrm{hpwd}_a$ is shared by choosing a random polynomial $f_a \in \mathbb Z_q[x]$ of degree $m - 1$ such that $f_a(0) = \mathrm{hpwd}_a$. The shares are points on this polynomial. We present the method in two steps, by first describing a simpler variation and then extending it in Section 5.4 to be more secure against an offline attack.

To choose a random polynomial $f(x) = c_k x^k + \dotsb + c_1 x + c_0$ of degree $k$ in the polynomial ring $\mathbb Z_q[x]$ simply means choosing $k+1$ random coefficients $c_0, c_1, \dotsb, c_k$ uniformly from the finite field $\mathbb Z_q$. However, the additional constraint that $f(0) = c_0$ should take a particular fixed value means that, in fact, only the $k$ coefficients $c_1, \dotsc, c_k$ can be chosen randomly, while the constant coefficient $c_0$ is fixed.

(Note that, using this procedure, there's a one in $q$ chance that $f$ will actually be of a degree lower than $k$, because $c_k = 0$ by chance. However, in the context of Shamir's secret sharing that's exactly what you want: the polynomial really should be randomly chosen from the set of polynomials of degree at most $k$ in $\mathbb Z_q[x]$ whose lowest coefficient has the desired secret value.)

Ps. A note on notation: $\mathbb Z_q$ here denotes the ring of integers modulo $q$, which is a field if and only if $q$ is prime. However, Shamir's secret sharing actually works in any finite field $\mathbb F_q$, which exist for all prime powers $q = p^n$. In particular, the characteristic-2 fields $\mathbb F_{2^n}$ are often convenient to work in, since their elements correspond naturally with $n$-bit bitstrings. The downside, of course, is that multiplication in finite fields of non-prime order is slightly trickier to implement (or, rather, that you're somewhat less likely to find an existing built-in implementation of it). For more details, see e.g. Galois fields in cryptography.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ ... and with probability $q^{-k}$ all of $c_1, c_2, \ldots, c_k$ would turn out to be $0$ and all the sharers would get individual copies of the secret instead of shares of the secret. I believe that in the context of Shamir's secret sharing scheme, $c_k$ must be chosen at random from the nonzero elements of the finite field. Else, the property that at least $k$ shares are needed to reconstruct the secret will not hold; $k-1$ shareholders (possibly even fewer if $f$ is of even smaller degree by happenstance) will be able to reconstruct the secret. $\endgroup$
    – Dilip Sarwate
    Commented Feb 24, 2013 at 22:43
  • 1
    $\begingroup$ @Dilip: While $k-1$ shareholders could indeed reconstruct the secret if $c_k=0$, they won't know that's the case unless they find a $k$-th shareholder to confirm it. Indeed, as far as they know, their chance of successfully doing that is the same ($1/q$) as of recovering the secret simply by randomly guessing some other participant's share. In fact, by the information-theoretical security of Shamir's scheme, it can be shown that knowing any $k-1$ shares provides no information about the secret, as long as all the non-constant coefficients of the polynomial are chosen uniformly at random. $\endgroup$
    – Ilmari Karonen
    Commented Feb 25, 2013 at 6:29
  • $\begingroup$ @Dilip: Anyway, any given participant's share will be equal to the secret with probability $1/q$ anyway, simply because the underlying field only has $q$ elements to choose from. This doesn't matter, since such coincidences are completely random and provide no information about the secret. If the idea still bothers you, you could always work in, say, $GF(2^{256})$, where any of this would be astronomically unlikely to happen. $\endgroup$
    – Ilmari Karonen
    Commented Feb 25, 2013 at 6:38
  • $\begingroup$ On the other hand, if $k-1$ shareholders attempt a reconstruction and get the secret to be "Attack at dawn!" (fits nicely as a single symbol in $GF(2^{256})$ :-) ), they might not want to look for a $k$-th shareholder to confirm. Just joking, but more to the point since you have brought up $GF(2^{256}) = \mathbb F_{2^{256}} \neq \mathbb Z_{2^{256}}$, could you please change all the $\mathbb Z_q$'s in your answer to $\mathbb F_q$'s? Thanks. $\endgroup$
    – Dilip Sarwate
    Commented Feb 25, 2013 at 12:38
  • $\begingroup$ @Dilip: Good suggestion. I left the $\mathbb Z_q$'s unchanged, since that was the notation used in the quoted paper, and changing it mid-answer seemed needlessly confusing to me. I did, however add a (hopefully) clarifying note at the end. As for your scenario, the whole point is that, if the shareholders have no prior reason to assume that $c_k=0$, then assuming that and observing that it implies a particular value of the secret (e.g. "Attack at dawn"), however likely a priori, gives them no new information (in a sense that can be formalized and proven) about the actual secret. $\endgroup$
    – Ilmari Karonen
    Commented Feb 25, 2013 at 15:25

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.