Is this a novel secret splitting method, or a different view of an existing one?

Question

I did try this on Information Security, but they were happier to see it moved here. The crypto content is quite low. It's more about secret storage and robust recovery of information, for instance allowing the sysadmin's password to be recovered by a quorum of other users, should he go under a bus.

I should am aware of a number of secret splitting methods, Shamir's polynomials and Blakely's hyperplanes for instance. I have not seen the following described anywhere in the literature, and AFICS, notwithstanding it operates over finite fields, it does not appear to be the same as Shamir's.

While I was playing about trying to understand the mathematics behind Raid6, it became apparent that the ability to reconstruct data in the face of missing portions could form the basis of a threshold secret splitting scheme.

The normal Raid6 operation employs what in forward error correction would be known as a systematic encoding. That is, the encoding operation is designed to render the input information 'in clear' at the output, as far as possible, to minimise computation. For example, in the case of a 6 drive with 2 redundancy Raid6, the encoding of data abcd by matrix multiplication is as follows

 | 1 0 0 0 |           | a |
 | 0 1 0 0 |   | a |   | b |
 | 0 0 1 0 | x | b | = | c |
 | 0 0 0 1 |   | c |   | d |
 | 1 1 1 1 |   | d |   | P |
 | v w x y |           | Q |

resulting in the plain data on the first 4 drives, simple parity on the 5th, and the more complicated sum on the 6th drive using the distinct non-unity multipliers vwxy from the appropriate Galois Field, GF(256) for byte based discs or messages.

The data can be recovered from any four of abcdPQ, in the general case by inverting the appropriate reduced matrix, though in practical drives, a more efficient method is used that takes advantage of the systematic encoding when possible. This is equivalent to a six share threshold 4 data split, with obviously no secrecy.

In the secret splitting mode, the multiplication would be replaced by

 | m00 m01 m02 m03 |            | e0 |
 | m04 m05 m06 m07 |   | d  |   | e1 |
 | m08 m09 m10 m11 | x | r0 | = | e2 |
 | m12 m13 m14 m15 |   | r1 |   | e3 |
 | m16 m17 m18 m19 |   | r2 |   | e4 |
 | m20 m21 m22 m23 |            | e5 |

where mxy are distinct multipliers from GF(256) [edit, thx poncho, obvious, but I failed to state it first time round] that form a matrix for which any reduced square matrix is non-singular (not guaranteed with a random selection)[/edit], d is the data message, rx are independent cryptographically secure random numbers, ideally from a one time pad, and ex are the encodings. The random data is used only in the encoding, and does not have to be stored or transmitted to the decoder.

As far as I can see, all six encoded channels have the input data combined with 3 random numbers, so without the full theshhold number of shares, the data is unrecoverable. I am sure that at least one, and possibly several of mxx can be replaced with unity, while retaining security. [edit]In fact, specifying a column of unity multipliers feels like being sufficient to enforce non-singularity for any reduced matrix.[/edit]

The scheme can be trivially modified to any number of shares and threshhold level, using a GF(p) where p>shares.threshhold.

I am not suggesting this might be in any way superior to the existing known methods, especially not Krawczyk's which is far more efficient for large secrets. But given the straightforward formulation, I'm surprised that I've not seen it described anywhere.

Is it novel? And does it work as well as I think it should?

Answer 1

I haven't seen this one before before, but keep on reading...

It would appear to work, but you need to be a bit careful, specifically with your $mxy$ multipliers; it should be apparent that not just any random set of values would work there.

I believe that a necessary and sufficient condition would be "if you logically add a $(1, 0, 0, ..., 0)$ row to the matrix, then all submatricies consisting of $N$ rows from this extended matrix must be nonsingular" (where $N$ is the threshold number of shares); if this condition does not hold, then either there is a group of $N$ valid shares that cannot reconstruct the secret, or there is a group of $N-1$ valid shares that can. Proving it is sufficient is straightforward; proving that it is necessary would appear to require going through a number of subcases, depending on what subset of rows was linearly dependent, and whether that subset included the artifical $(1, 0, 0, 0, ..., 0)$ row.

Blom's key distribution scheme has exactly that same requirement to its internal matrix; his key distribution scheme isn't a secret sharing scheme; instead, it's a way to distribute key shares so that any two parties can agree on a key, and no set of $N-1$ other parties can recover it.

One suggestion to make Blom's scheme work was to use the matrix:

$$ \begin{matrix} 1^0 & 1^1 & 1^2 & 1^3\\ 2^0 & 2^1 & 2^2 & 2^3\\ 3^0 & 3^1 & 3^2 & 3^3\\ 4^0 & 4^1 & 4^2 & 4^3\\ 5^0 & 5^1 & 5^2 & 5^3\\ 6^0 & 6^1 & 6^2 & 6^3\\ \end{matrix} $$

(where $1, 2, 3, 4, 5, 6$ are distinct nonzero field elements)

This matrix meets the criteria I mentioned, and works great for you. However, if you look at it closely, it you use it, well, you've just rediscovered Shamir's original method :-)