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?

  • 2
    Standard SSS should work decently over prime fields. Especially if you choose a convenient modulus, like 101. – CodesInChaos Oct 16 '17 at 14:18
  • 3
    @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 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.

  • 3
    Could you give a reference to that "it is known"? – Daniel Jan 11 at 22:08
  • 2
    (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 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 at 13:11

2-of-4 secret sharing scheme using Latin squares.

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.

  • 1
    Unfortunately, L1 isn't a Latin square, as the 2nd column and 4th row have repeated 1, and no 3. – Aaron Toponce Oct 14 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 at 5:25

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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