5

I'm working on trying to understand how to use Reed-Solomon decoding to make Shamir secret sharing robust to cheaters as mentioned here. I'm following the setup shown at the bottom of page 40 in this paper.

So, here is my simple example. I'm working in $\mathbb{Z}_{11}$. Let $p(x)=8+3x$ be the polynomial I'm using for sharing (so my secret is $8$). I compute 4 shares using $x=1,2,3,4$ and get $0,3,6,9$ as the shares.

From the setup in the second paper, I set $G=\left(\begin{array}{cccc} 1 & 1 & 1 & 1\\1&2&3&4\end{array}\right)$. Thanks to the answer I got yesterday, I know that $H=\left(\begin{array}{cccc} 1 & 9 & 1 & 0\\2&8&0&1\end{array}\right)$.

Say I receive the word $r=\left(\begin{array}{cccc} 0 & 4 & 6 & 9\end{array}\right)$, notice the error in the second position. Thus $rH^T=\left(\begin{array}{cc} 9 & 8\end{array}\right)$, which are my syndromes.

From Wikipedia we have the error locator polynomial $\Lambda(x)=1+\Lambda_1x^1+\dots+\Lambda_vx^v$ where the $\Lambda_i$ can be computed from:

enter image description here

Note that in my case $v=1$ so the system of equations is very simple $S_1\Lambda_1=-S_2$ or $9\Lambda_1=-8=3$ so $\Lambda_1=4$ and $\Lambda(x)=4x+1$.

The root of $\Lambda(x)$ I got as $8$.

Given the roots, I should be able to find the error locators. According to Wikipedia, "the error locators are the reciprocals of those roots", so my error locator is $8^{-1}=7$.

From there, Wikipedia says the error location is the log base $a$ of the locator. Since I did my encoding as $p(1),p(2),p(3),p(4)$ instead of $p(a^1),p(a^2),p(a^3),p(a^4)$ there really isn't an $a$.

Is decoding possible based on the way I did my encoding? Do I need to change my encoding method?

If I don't need to change, where do I go from here to find and correct the error? Have I done things right up to this point?

On a side note, I put my syndromes into the berlekamp-massey algorithm using Sage and got the polynomial $x+4$ in return which has $7$ as its root.

Community
  • 1
mikeazo
  • 412
  • I don't have the time to take a close look at this now, but it seems to me that the description on that Wikipedia page uses a description of RS-codes in terms of generator polynomials. That means that symbol positions are fixed to appear in the order of consecutive powers of a primitive element of the field as opposed to in some other order (as here). The basic problem is that your description of the code (or the syndrome) does not match that of the Wikipedia page. There are decoding approaches that work for other symbol orders, but I would need to think about it more to suggest one. – Jyrki Lahtonen Oct 08 '13 at 12:48
  • In your toy case the received word gives you four points on the plane. Decoding amounts to figuring out which of those four points is not collinear with the others. – Jyrki Lahtonen Oct 08 '13 at 13:02
  • FWIW, I ended up scrapping this method and doing an ${n \choose t}$ brute force decoding. Whatever value appears most is the winner. Works fine since my $n$ and $t$ are small. – mikeazo Feb 19 '15 at 20:14

0 Answers0