4
$\begingroup$

In this post, a couple comments suggested that a tabula recta could be used to perform Shamir Secret Sharing. I'm specifically interested in this statement:

you could just have a table of all 100 inverses mod 101

If this simply means a 10x10 table, that's no problem. That's smaller than a regular tabula recta. But even if it's 100x100, I am still interested in how this would work.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ I think what the comment "you could just have a table of all 100 inverses mod 101" means is that you could easily compute the inverse for each value in $\mathbb{Z}_{101}$ and create a lookup table (i.e. map) of value -> inverse to quickly find inverses. Note that this works because 101 is prime so all elements of $\mathbb{Z}_{101}$ are in $\mathbb{Z}^{\times}_{101}$. $\endgroup$
    – puzzlepalace
    Oct 12, 2018 at 5:21
  • 1
    $\begingroup$ I concur with puzzlepalace. I think the comment was referring to a construct which would greatly improve the efficiency of some of the operations at the cost of some initial expense of constructing the table. It is possible to build a set of tables, if you wanted, to be able to lookup secrets given their shares, but the number of combinations grows very quickly. This approach would not be very practical since a simple vector dot product will suffice. $\endgroup$
    – Ken Goss
    Oct 12, 2018 at 13:48

1 Answer 1

Reset to default
2
+100
$\begingroup$

Taking the question as literally as possible, I have provided my pencil and paper tables for a scheme among three parties with a polynomial of degree 2 and a field of $\mathbb{Z}_5$ to keep things feasible for a pencil and paper example. Given the tables, in order to reconstruct any secret look up the table to be used by the share from party 1 (table numbers are denoted in a box to the upper left of each table), the row to be used by the share from party 2 and the column to be used by the share for party 3.

I've provided an example polynomial $4x^2+3x+1$ which evaluates correctly to 1, the secret, at $x=0$, 3 when $x=1$, 3 when $x=2$, and finally 1 when $x=3$. Then, to reveal the secret, take these shares and look them up as described. I've boxed in red the correct value from following the described procedure. This set of tables should work for any polynomial valid in the field described and for shares based on players associated with the same values for $x$. Shamir Tables for a polynomial of degree 2 and a field <span class=$\mathbb{Z}_5$">

Improve this answer
$\endgroup$
12
  • 1
    $\begingroup$ Thank you very much! I gave you best answer but I have to wait 3 hours to award the bounty. When I get around to learning your method I'll post any questions I have here and perhaps you could help me out (if I have any difficulty following your instructions). $\endgroup$
    – Meler Lawler
    Oct 13, 2018 at 0:56
  • 1
    $\begingroup$ "in order to reconstruct any secret look of the table to be used by the share from party 1" I suspect there is a typo somewhere, right? Look "up" the table, not look "of"? $\endgroup$
    – Meler Lawler
    Oct 13, 2018 at 2:14
  • 1
    $\begingroup$ Quite right. It should have been "up" not "of". I've corrected the answer. $\endgroup$
    – Ken Goss
    Oct 13, 2018 at 2:15
  • 1
    $\begingroup$ The share with 'x' coordinate 0 just gives the secret. It is not distributed. I included it for completeness to demonstrate that the polynomial does indeed carry the correct y-intercept for the secret. You'd take the value from the polynomial for x=1 to select the table, the value of the point for x=2 to select the row, and the value for x=3 to select the column. $\endgroup$
    – Ken Goss
    Oct 13, 2018 at 2:37
  • 1
    $\begingroup$ All operations are in the group defined by the scheme's modulus, in this case 5. So it's not the number of tables, the number of tables is itself a result of the choice of the group for the secret sharing scheme. 8 is congruent to 3 in $\mathbb{Z}_5$. So the 'y' from share 1 selects the table, the y from share 2 selects the row, and the y from share 3 selects the column. $\endgroup$
    – Ken Goss
    Oct 13, 2018 at 2:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.