# Manual secret sharing?

What are feasible options for an equivalent of Shamir Secret Sharing using small tables, preferably usable with pen-and-paper? We want to share a secret $K$ into $n\ge2$ shares, so that $m$ shares ($2\le m\le n$) are necessary to reconstruct the secret, and less than $m$ shares reveal no information about $K$.

For $m=n$ (e.g. 2-out-of-2), we can use $n-1$ shares $S_i$ ($1\le i<n$) of uniformly random independent bits, and another $S_0$ that is the bitwise-XOR of the secret $K$ and the other shares: $S_{0,j}=K_j\oplus\left(\displaystyle\bigoplus_{i=1}^{n-1}S_{i,j}\right)$. The secret is recomposed by bitwise-XOR of the random shares: $K_j=\displaystyle\bigoplus_{i=0}^{n-1}S_{i,j}$.

This is easily extended to $2^k$ symbols, e.g. octal or hexadecimal.

For 2-out-of-3, we can use a ternary system, a first share $S_0$ of random trits, an two shares $S_i$ ($i\in\{1,2\}$ ) defined by $S_{i,j}=S_{1,j}+i\,K_j\bmod3$. The secret can be recomposed from any two shares, as: $$K_j\,=\,S_{1,j}-S_{0,j}\bmod3\,=\,S_{2,j}-S_{1,j}\bmod3\,=\,S_{0,j}-S_{2,j}\bmod3$$ The tables for addition (used for encoding) and subtraction (used for decoding) are:

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


This is easily extended to base $3^k$; e.g. for $k=2$

    | 0 1 2 3 4 5 6 7 8                 | 0 1 2 3 4 5 6 7 8
----+------------------             ----+------------------
+ 0 | 0 1 2 3 4 5 6 7 8             - 0 | 0 1 2 3 4 5 6 7 8
+ 1 | 1 2 0 4 5 3 7 8 6             - 1 | 2 0 1 5 3 4 8 6 7
+ 2 | 2 0 1 5 3 4 8 6 7             - 2 | 1 2 0 4 5 3 7 8 6
+ 3 | 3 4 5 6 7 8 0 1 2             - 3 | 6 7 8 0 1 2 3 4 5
+ 4 | 4 5 3 7 8 6 1 2 0             - 4 | 8 6 7 2 0 1 5 3 4
+ 5 | 5 3 4 8 6 7 2 0 1             - 5 | 7 8 6 1 2 0 4 5 3
+ 6 | 6 7 8 0 1 2 3 4 5             - 6 | 3 4 5 6 7 8 0 1 2
+ 7 | 7 8 6 1 2 0 4 5 3             - 7 | 5 3 4 8 6 7 2 0 1
+ 8 | 8 6 7 2 0 1 5 3 4             - 8 | 4 5 3 7 8 6 1 2 0


See this for $k=3$ used for the 26 letters and space.

As long as conciseness of the shares is not an issue, we can directly encode binary with the ternary system, octal with $k=2$, hex with $k=3$, base64 with $k=4$.

What about other $m$-out-of-$n$ schemes? In particular 2-out-of-4, 2-out-of-5, 3-out-of-4?

• Standard SSS should work decently over prime fields. Especially if you choose a convenient modulus, like 101. – CodesInChaos Oct 16 '17 at 14:18
• @CodesInChaos: SSS's requirement to compute inverses is annoying. Of course, you could just have a table of all 100 inverses mod 101... – poncho Oct 16 '17 at 14:24
• Would that be a 100x100 table or just a 10x10 table? Also it would be really nice to see this demonstrated so a layman could do it. And by "layman," I mean myself. :) – Meler Lawler Oct 9 '18 at 18:50

It is known that (m,n)-threshold schemes are equivalent to n-1 m-dimensional mutually orthogonal latin m-hypercubes. For m=2, there is a basic construction (Latin Squares) for prime n. For m > 2 you would need higher dimensional tables, there should still exist a simple way to generate them for prime n.

• Could you give a reference to that "it is known"? – Daniel Jan 11 '18 at 22:08
• (Late answer, answer to @Daniel and shameless plug alert) I explained a method to get threshold schemes from Latin Hypercubes tel.archives-ouvertes.fr/tel-00763117/document (p. 45) – Tarik Kaced Oct 10 '18 at 6:42
• Posting a screenshot of p. 45 seems like an easy way to get awarded best answer to this question :) I looked at it and it's really cool! – Meler Lawler Oct 10 '18 at 13:11 From page 45 of this very interesting paper.

What about other m-out-of-n schemes? In particular 2-out-of-4, 2-out-of-5, 3-out-of-4?

I don't know about 3-of-4, unfortunately.

• Unfortunately, L1 isn't a Latin square, as the 2nd column and 4th row have repeated 1, and no 3. – Aaron Toponce Oct 14 '18 at 3:02
• Thanks for pointing that out, I also noticed that sometime after posting this. I think the scheme still works though, despite the author's terminology mistake. – Meler Lawler Oct 14 '18 at 5:25