5
$\begingroup$

We are trying to implement a general file recovery algorithm using Galois Fields. We have implemented the operations for Galois Fields GF(2^8) succesfully, but we're are running into a problem for the case with 4 data drives and 4 parity drives. More specifically, the case where data drives 0, 1, and 2, and parity drive 2 are missing.

Following the implementation in this paper, we construct an 8 by 4 matrix:

1   0   0   0 
0   1   0   0
0   0   1   0
0   0   0   1
1   1   1   1
1   2   3   4
1^2 2^2 3^2 4^2
1^3 2^3 3^3 4^3

Since datadrives 0, 1, and 2, and parity drive 2 are compromised, we omit the rows 0, 1, 2, and 6. That leaves

0   0   0   1         0  0  0  1 
1   1   1   1     =   1  1  1  1
1   2   3   4         1  2  3  4
1^3 2^3 3^3 4^3       1  8 15 64

Let's call this matrix A'. If D is the data vector, and E' is the vector corresponding to the data on the drives that did not fail, we should be able to solve A' D = E' for D.

D = A'^{-1} A' D = A'^{-1} E'

However, matrix A' doesn't seem to be invertible. See also this code snippet at sageMath:

SageMath even shows that the matrix can be simplified to

A' =
[0 0 0 1]
[1 1 1 1]
[1 0 1 0]
[1 0 1 0]

which is clearly not invertible. Somehow the parity rows [1^1, 2^1, 3^1, 4^1] and [1^3, 2^3, 3^3, 4^3] are linearly dependent. We thought these rows were constructed to be independent, even with the operations on GF(2^8)

Clearly, we're missing something, but at this point, we're not sure what's happening here.

UPDATE 1

So it turns out the generator matrix in that paper was completely wrong. Following the suggestion by Jyrki in the comments here, we constructed the desired matrix starting from a variant of the Vandermonde matrix. This variant is of the form:

$$G = \left( \begin{array}{ cccc } \alpha_0^0 & \alpha_0^1 & .. & \alpha_0^d \\ \alpha_1^0 & \alpha_1^1 & .. & \alpha_1^d \\ .. & .. & .. & .. & .. \\ \alpha_{d+p}^0 & \alpha_{d+p}^1 & .. & \alpha_{d+p}^d \\ \end{array} \right)$$ where the $d$ is the number of data bits, $p$ is the number of parity bits, and $\alpha_i$ are chosen elements of order $2^8$ in $GF(2^8)$. These alpha can be constructed by taking the Galois Field element with 2 as its integer representation, and raising it to a power that shares no prime factors with $2^8 - 1$. So:

$\alpha_0 = 2^1$,

$\alpha_1 = 2^2$,

$\alpha_2 = 2^4$ (skip $2^3$ because 3 has a prime in common with $2^8-1$),

$\alpha_3 = 2^7$ (skip $2^5$ and $2^6$ because 5 and 6 share prime factors with $2^8-1$),

$\alpha_4 = 2^8$, etc

I must admit that I don't understand this argument completely, but it works for now. For the top $d \times d$ block (let's call it $P$), we compute $P^{-1}$ and calculate $GP^{-1}$ to get it in the desired form.

We also tried the matrix on described in this paper, which uses the same base $\alpha$, which also works as far as we can tell.

We have also looked at multiple other software implementations, where they appear to determine the parity block in one go (so without calculating $GP^{-1}$. The code however is very difficult to understand. Could there be a standard procedure to immediately generate that bottom block or do these software packages only work for a specific order of the field and polynomial?

$\endgroup$
13
  • $\begingroup$ $3^3$ is $27$, not $15$. But it's not clear to me what numbers like $15$ and $27$ mean in the field of $64$ elements. $\endgroup$ May 10, 2020 at 23:26
  • 1
    $\begingroup$ I think, @reuns, that the computer scientists have a convention of representing a quantity in $\Bbb F_{2^n}$ by $n$ bits (but I don’t know what basis is chosen) and treating those $n$ bits as an integer between $0$ and $2^n-1$, at least for purposes of display. $\endgroup$
    – Lubin
    May 11, 2020 at 2:57
  • 1
    $\begingroup$ So this is the answer ? @Lubin Sagemath has a way to use this bit representation but here the OP failed to do so in his code $\endgroup$
    – reuns
    May 11, 2020 at 3:07
  • 1
    $\begingroup$ What still confuses me is that @reuns answer uses F.fetch_int(2^3) instead of F.fetch_int(2)^3 for the elements in the matrix. I would think that since the elements in the Vandermonde matrix are elements of the field, you would need to use multiplication and exponentiation as defined on the field as well. $\endgroup$
    – Rufus1123
    May 11, 2020 at 8:34
  • 2
    $\begingroup$ @GerryMyerson What Lubin said. This is common enough for people implementing finite fields of characteristic two. Too common, if you ask me, for the poor students have little chance of understanding what may go wrong without a full cours on algebraic structures. It is a common source of confusion on this site with many people with background only in exactly one of algebra/programming. I have tried to deal with it dozens of times already. To meet the goals of me personal policy on duplicates I probably should write another tailored Q&A pair I could refer askers to. $\endgroup$ May 11, 2020 at 12:02

1 Answer 1

2
$\begingroup$

Even though the OP apparently used Sage incorrectly, the example matrix $A$ is singular, and there is an error in the argument from the article. The weak argument in the source is on page 6. The matrix is constructed by putting an n×n identity block on top of a Vandermonde block of the same size. The author then bluntly claims that because the rows of the Vandermonde block are linearly independent (correct) any collection of $n$ rows of the $(2n)\times n$ matrix is also linearly independent. There is no reason for that to be the case.

In fact, the title page of the linked article contains the disclaimer:

The information dispersal matrix $A$ given in this paper does not have the desired properties. Please see TechnicalReportCS-03-504 for a correction to this problem. This technical report is available at http://www.cs.utk.edu/~plank/papers/CS-03-504.pdf


Also see Lubin's comment, you need to use Sage's function for conversion of integers to elements of the field

     F =GF(256)
     MS = MatrixSpace(F, 4, 4)

     M = MS.matrix([0,0,0,1, 1,1,1,1, 1,F.fetch_int(2),F.fetch_int(3),F.fetch_int(4), 1,F.fetch_int(2)^3,F.fetch_int(3)^3,F.fetch_int(4)^3])
     print(M)
$\endgroup$
11
  • $\begingroup$ To tell you the truth, I was immediately suspicious of that construction. I have seen many this kind of constructs serving various ends in my time so that I guess I can claim to have a relatively strong intuition. I didn't check the correction, but I think the authors need to use an MDS-code or some such. Anyway, a fix exists :-) $\endgroup$ May 11, 2020 at 5:52
  • $\begingroup$ Unfortunately, the link does not work for me. So what you are saying is that de Vandermonde block is indeed singular, obviously the identity block is singular, but there are no guarantees for any $n\times n$ subset of the $(2n) \times n$? $\endgroup$
    – Rufus1123
    May 11, 2020 at 8:39
  • 1
    $\begingroup$ @Rufus1123 The Vandermonde block is non-singular, the identity block is non-singular, but a random collection of $n$ rows from the combined $A$ need not be. If the link in the article does not work, you have to contact the author. I cannot help you with that. $\endgroup$ May 11, 2020 at 9:13
  • $\begingroup$ Well, looks like the link was misspelled with html where pdfshould have been. $\endgroup$ May 11, 2020 at 9:16
  • 1
    $\begingroup$ @Devedse Thanks for the vote of confidence. I don't have time to check it out now. AFAICT you want a matrix $A$ such that 1) the top half is an identity block (you want the data also to be coded "as is"), and 2) you want any combination of $n$ out of $2n$ rows to be linearly independent. I would construct such a matrix by i) picking $2n$ columns of an MDS-code (such as Reed-Solomon) of codimension $n$ to get a matrix $M$, ii) invert the matrix $P$ of the leftmost $n$ columns, iii) calculate $P^{-1}M$ to get an identity block to the left but keep the linear independence of columns, $\endgroup$ May 11, 2020 at 11:52

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.