1
$\begingroup$

In the answer to this post at security.stackexchange, someone describes how, using pencil and paper, one can do 2-of-3 secret sharing with a tabula recta. But I don't understand how he created his table, and although I can see some sort of pattern I wouldn't be able to reconstruct it in a pinch.

Another question I have is, is this sharing scheme information-theoretically secure? Does any individual share, taken alone, provide any information about the secret?

$\endgroup$
  • $\begingroup$ There's a description of how the table was constructed at the bottom of the post you linked to. While it could probably be made clearer, it would also help if you pointed out which parts of it you understood and which parts you didn't. $\endgroup$ – Ilmari Karonen Oct 8 '18 at 1:37
  • $\begingroup$ Using the 3x3 table, the formula SECRET[i] = (3 + SHARE3[i] - SHARE1[i]) % 3 works (I'm using my own notation). I thought if I used a 27 letter alphabet, I could use the formula SECRET[i] = (27 + SHARE3[i] - SHARE1[i]) % 27, where each letter represents its position in the alphabet from 0 to 26, but that works for every share except SHARE3. I can reconstruct SECRET from SHARE1 and SHARE2 this way, but not if SHARE3 is involved. $\endgroup$ – Meler Lawler Oct 8 '18 at 3:42
3
+50
$\begingroup$

We start by coding a secret $k\in\{0,1,2\}$ as three shares $x$, $y$, $z$ by

  • choosing share $x$ uniformly at random in $\in\{0,1,2\}$
  • choosing share $y$ as $(x-k)\bmod 3$
  • choosing share $z$ as $(y-k)\bmod 3$

One share gives no clue about $k$, but we can recover $k$ from any two shares:

  • from $x$ and $y$ as: $k=(x-y)\bmod 3$
  • from $y$ and $z$ as: $k=(y-z)\bmod 3$
  • from $z$ and $x$ as: $k=(z-x)\bmod 3$

Note: per standard notation of modular arithmetic, for $n>0$, the quantity $i\bmod n$ is defined as the $j$ with $0\le j<n$ such that $i-j$ is a multiple of $n$.

The table we need to carry this has $k=(x-y)\bmod 3$ at column $x$ and lines $y$, that is:

    |  0  1  2
----+----------
- 0 |  0  1  2
- 1 |  2  0  1
- 2 |  1  2  0

Now, if the secret consists of two digits each in $\{0,1,2\}$, we can express it as three shares of two digits each in $\{0,1,2\}$, by using the above method for each digit of the secret, yielding the corresponding digit for each of the three shares.

We can simplify doing that by building the following table, where each digit of the result is obtained by applying the previous table to the corresponding digit of each input:

     |  00  01  02  10  11  12  20  21  22
-----+-------------------------------------
- 00 |  00  01  02  10  11  12  20  21  22
- 01 |  02  00  01  12  10  11  22  20  21
- 02 |  01  02  00  11  12  10  21  22  20
- 10 |  20  21  22  00  01  02  10  11  12
- 11 |  22  20  21  02  00  01  12  10  11
- 12 |  21  22  20  01  02  00  11  12  10
- 20 |  10  11  12  20  21  22  00  01  02
- 21 |  12  10  11  22  20  21  02  00  01
- 22 |  11  12  10  21  22  20  01  02  00

We can then replace two-digit pairs by $3^2=9$ letters A..I (in row and column indexes, and the table itself), and we get:

     |  A   B   C   D   E   F   G   H   I
-----+-------------------------------------
- A  |  A   B   C   D   E   F   G   H   I
- B  |  C   A   B   F   D   E   I   G   H
- C  |  B   C   A   E   F   D   H   I   G
- D  |  G   H   I   A   B   C   D   E   F
- E  |  I   G   H   C   A   B   F   D   E
- F  |  H   I   G   B   C   A   E   F   D
- G  |  D   E   F   G   H   I   A   B   C
- H  |  F   D   E   I   G   H   C   A   B
- I  |  E   F   D   H   I   G   B   C   A

We can do the same thing for secrets consisting of three digits, then replace three-digit triples by $3^3=27$ signs: letters A..Z and . . That's how the table in my answer was constructed.

The mapping of $3^3=27$ three-digit triples to letters is arbitrary. We would obtain a table that works just as well for any mapping. We can additionally reorder lines and columns in a convenient order, e.g. alphabetical. That allows to generate different easy-to-use tables that work just as well.

We can also extend to $3^4=81$ symbols, allowing uppercase and lowercase, digits, and 19 typographical symbols (but if the symbols are ultimately printed, the font must allow recognizing between O and 0, l and 1 ).

$\endgroup$
  • $\begingroup$ Thank you for your response! I marked this as best answer, but I have to wait 21 hours to award the bounty. I haven't read your answer thoroughly yet, but if I have any questions I will post a comment here. $\endgroup$ – Meler Lawler Oct 8 '18 at 7:24
  • 1
    $\begingroup$ Okay, I do have a question now. The 3x3 table makes sense to me, since finding the intersection of any top row and left column number results in the difference of those two numbers. For instance, 2 -1 = 1. But using the second table, the intersection of 01 and -01 is not 00 as I would have expected; it's 02. This makes no sense to me, since 1-1 does not equal 2. $\endgroup$ – Meler Lawler Oct 8 '18 at 20:06
  • 1
    $\begingroup$ @Meler Lawler: oups! I made an error! Fixing that.. Done. $\endgroup$ – fgrieu Oct 8 '18 at 21:08

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.