1
$\begingroup$

I am currently reading the book Cryptography: Theory and Practice (4th edition) by Stinson and Paterson and going through the exercises. I have reached the Threshold schemes section and am currently doing the exercises related to Shamir's secret sharing scheme.

The first exercise (11.8 in the 4th edition of the book) asks to write a computer program to compute a key starting from a list of shares, which I have done, and then test that the program computes the same key with different combinations of $x$ and $y$ values (which are provided in the exercise instructions), which I have also done.

Exercise 11.8 (b) then proceeds to ask the following:

Having determined the key, compute the share that would be given to a participant with x-coordinate equal to 10000. (Note that this can be done without computing the whole secret polynomial a(x).)

Perhaps I am misunderstanding the question, but my understanding is that the resulting $y = a(x)$ share does not depend on the $x$ value alone. Indeed, looking at the formula for computing a share:

$$a(x) = K + \sum_{j=1}^{t-1} a_jx_j \pmod p$$

(with $t$ the minimum number of shares required to reconstruct the key $K$)

we see that the final value of $a(x)$ will not only depend on the chosen $x$ values, but also from the chosen $a$ values. The values $a_1,...,a_n$ are also chosen by the dealer at the beginning of the key distribution process.

In light of all this, am I misunderstanding the exercise question or is it not possible to have a unique answer, unless you know all the $a_1,...,a_n$ values, which the exercise does not provide?

Or in other more concise words: am I supposed to have one and only one value for $a(10000)$?

Improve this question
$\endgroup$
3
$\begingroup$

In exercise 11.8, you have written a program that recovers the shared secret, that is, given $n$ pairs $x_i, y_i$ with $y_i = P(x_i)$ where $P$ is an unknown $n-1$ degree polynomial, evaluates $P(0)$.

Now, exercise 11.8b asks you to find the share with $x=10000$, that is, $y = P(10000)$ for the unknown polynomial $P$ that you have $n$ shares with already.

Here is one approach; define $P'(x) = P(x + 10000)$, and then trick your program into evaluating $P'(0)$. The question then is "how do you find the $n$ pairs $x'_i, y'_i$ that satisifies $y'_i = P'(x'_i)$, using the $x_i, y_i$ pairs you have?".

I hope that is a enough of a hint...

Improve this answer
$\endgroup$
5
  • $\begingroup$ Here is the thing: I have written a function in my code that calculates $P(x)$, and it is working, but the value of $P(10000)$ changes at every run of the program (again, since the values $a_1,...,a_n$ are chosen randomly at every run). Are you suggesting that I should evaluate the coefficients of the polynomial for my $x_1,...,x_n$ values, and use those in my subsequent calculations? That's the only step I could think of that could be missing, but I am not sure it is what you are referring to here. $\endgroup$ – user1301428 Jun 22 '20 at 15:24
  • $\begingroup$ @user1301428: isn't exercise 11.8b meant to be run based on the $x_i, y_i$ values given as test examples in exercise 11.8a? If so, why are you choosing $a_1, .. a_n$ randomly? Aren't they implicit from the test data? $\endgroup$ – poncho Jun 22 '20 at 17:10
  • $\begingroup$ I think this is exactly where I got confused. I was trying to calculate $P(10000)$ based on shares I created with random $a_1,...,a_n$ values, but in this case it's true that I am already given the shares, so that step is not necessary. So from the existing $x$ and $y$ coordinates, I will have to 1) calculate the coefficients of the polynomial, and 2) calculate $P(10000)$ based on these coefficients. Am I correct? $\endgroup$ – user1301428 Jun 22 '20 at 17:49
  • $\begingroup$ @user1301428: no, you don't need to compute the coefficients of the polynomial - actually, that's the point of the exercise, as there's an easier way with the tool you've already built... $\endgroup$ – poncho Jun 22 '20 at 17:51
  • $\begingroup$ I have upvoted your answer as I am sure it is a useful hint to anyone else who might have the same question in the future. However, since it doesn't really answer my question and only gave an additional sub-exercise as an answer, I am not marking it as accepted, so other users have the chance to contribute and improve your answer. I understand we need to be careful to avoid giving answers to people who might just be trying to get exercise solutions for coursework, but not everyone is in school. Sometimes you just have a question and you need an explanation to understand the topic better. $\endgroup$ – user1301428 Jun 23 '20 at 7:40

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.