# Can Reed Solomon parity blocks be used as an all-or-nothing transform?

Consider the following scheme:

1. Perform an (N,N) Reed-Solomon encoding (i.e. N data blocks, N parity blocks)
2. Drop the N data blocks and keep only the N parity blocks.

Are these N parity blocks an all-or-nothing transform? (meaning missing even one parity block does not permit decoding the original data blocks)

Reed-Solomon codes are Maximum-Distance-Separable codes and thus have the property that in a $$[n,k]$$ RS code ---- meaning than there are a total of $$n$$ blocks of which $$k$$ are data blocks and $$n-k$$ are parity block ($$n=2N$$ and $$k=N$$ in the OP's notation) ---- any $$k$$ blocks are sufficient to reconstruct the entire codeword, that is, all the blocks can be found if we know $$k$$ of them. Note that it does not matter whether the $$k$$ blocks available are a mixture of data and parity blocks or parity blocks only, just as long as $$k$$ blocks are available.

So, in the scheme envisioned by the OP, if one has a $$[2N,N]$$ Reed-Solomon code ($$N$$ data blocks, $$N$$ parity blocks, for a total of $$2N$$ blocks) and keeps only the $$N$$ parity blocks, the $$N$$ data blocks can be reconstructed. If fewer than $$N$$ of the parity blocks, then the data blocks cannot be reconstructed in the sense that the decoder can come up with a list of $$M$$ possible candidates for the $$N$$ data blocks but cannot say which of the candidates is the correct one. Here, each of the $$M$$ candidates on the list is a vector $$[D_1, D_2, \ldots, D_N]$$ of $$N$$ data block (each $$D_i$$ is a data block) and the decoder cannot determine which is the correct vector of $$N$$ data blocks. What is $$M$$? Well, $$M$$ is the number of possible distinct values that each data block might have and thus is either the number of elements in the finite field over which the Reed-Solomon code is defined, or some power $$L$$ thereof if each data block is a vector of length $$L$$ over the finite field (and we are using an interleaved Reed-Solomon code). Either way, $$M$$ is pretty large.

• Thank you @dilip, the answer is clear. As a side question, imagine that I want to add an extra constraint to my problem : "The $N$ data blocks should be reconstructed exclusively from the $N$ parity blocks, and not from a mixture of data and parity blocks". Would Reed-Solomon (non-systematic?) still be a candidate for this constrained scheme? – stefanix May 26 at 7:09
• @stefanix As I said in my answer, it does not matter to the general (erasures-correcting) decoding algorithm whether the $N$ available blocks are parity blocks only or a mixture of data and parity blocks. But it is certainly possible to modify the general algorithm to tell it to refuse to decode a mixture of data and parity blocks, and decode iff $N$ parity blocks are available. Similarly, when $<N$ blocks are available, the standard RS decoder fails to decode (gives error signal only), and it is necessary to re-program it to spit out the list of $M$ possible vectors of data blocks instead. – Dilip Sarwate May 27 at 2:37

A Reed-Solomon code is an MDS code over the symbol alphabet $$\mathbb{F}_q,$$ with parameters $$[n,k,n-k+1]$$. Here, the length $$n=2N$$ the dimension $$k=N$$ and the minimum distance is $$d=N+1.$$

Such codes form Orthogonal Arrays of strength $$t=n-d+1=N+1.$$

And an OA of strength $$t$$ is also an OA of strength $$t'\leq t.$$ Take $$t'=N.$$ Thus, yes, dropping one of the $$N$$ parity blocks would result in an AONT, leaking no information about the missing block.

Edit: In general any $$N$$ blocks are enough to reconstruct the missing blocks.

• Just to make sure: dropping one of the N parity blocks does not leak any information on any of the N data blocks? – stefanix May 22 at 15:24
• So how many blocks do you need in total to reconstruct the data? – stefanix May 24 at 8:56
• My comment above is in error, I will edit the body of the paper, to stop the confusion. – kodlu May 24 at 22:27
• Your last paragraph is incorrect even after the edit. – Dilip Sarwate May 25 at 14:53
• OK, much better after the second edit. – Dilip Sarwate May 27 at 2:26