964 reputation
48
bio website
location
age
visits member for 2 years, 7 months
seen 7 hours ago

Mar
7
revised How to generate a random integer in interval $[1, 2^n-1]$ from random integer in interval $[0, 2^n-1]$?
added 1 characters in body
Feb
16
answered Do deterministic secret sharing schemes exist?
Nov
26
comment Upper bound Linear Feedback Shift Register
What does a linear feedback shift register with $R$ registers mean? In general, the period of a polynomial $g(x)$ is the least integer $e$ such that $g(x)$ divides $x^e -1$. If $g(x)$ is the feedback polynomial of an LFSR, then $e$ is the upper bound you seek. But determining $e$ for a given $g(x)$ is by no means a trivial task.
Nov
11
awarded  Necromancer
Oct
1
comment RS Erasure Coding and Shamir's Secret Sharing
Yes, with $3$-out-of-$4$ secret sharing, you cannot recover the secret from $4$ shares if one share is corrupt but you don't know which one. (If you do know which share is corrupt, just ignore it and recover using the known $3$ good ones). With $2$-out-of-$4$ sharing, you can recover the secret if all $4$ shares are present as long as (i) at most one share is bad (but you don't know which one) or (ii) one, or even two shares, are known to be bad and you know which ones. As before, ignore the known bad shares and reconstruct from the known good ones (at least two are available).
Oct
1
comment RS Erasure Coding and Shamir's Secret Sharing
@mikeazo How many uncorrupted shares do you need for reconstruction? If $2$ good shares are required to reconstruct, then you use a $[4,2]$ Reed-Solomon code. It can reconstruct the secret if any two good shares are available. It can reconstruct if two good shares are available and a third "My flash drive got laundered" share is present (just ignore the clean guy's share!). And it can reconstruct the secret if all $4$ parties are present and (possibly) one of the shares is bad, but it is not known which one is bad. (If you know which share is bad, just ignore it and use 2 good shares).
Sep
29
comment Why does Shamir's Secret Sharing Scheme need a finite field?
OK, I edited my answer to remove the references to the Fundamental Theorem of Algebra. But isn't it true that if a degree-$n$ polynomial in $\mathbb F_q[x]$ does not have $n$ roots in the finite field $\mathbb F_q$, then all its $n$ roots lie in a finite extension field $\mathbb F_{q^m}$ where $m$ is some finite integer? Or are you saying that the roots lie in no finite extension of $F_q$, and we must always go to nonfinite extensions?
Sep
29
revised Why does Shamir's Secret Sharing Scheme need a finite field?
added 552 characters in body
Sep
23
comment RS Erasure Coding and Shamir's Secret Sharing
@mikeazo I found the programs here to be useful. If I remember correctly, the Reed-Solomon stuff is in C or C++.
Sep
23
comment RS Erasure Coding and Shamir's Secret Sharing
@mikeazo Sorry, I don't know of any Reed-Solomon implementations suited for secret-sharing applications. Most Reed-Solomon decoder implementations that I am aware of are for error-control purposes in digital communications schemes or digital video recording schemes, and VLSI implementation as an ASIC rather than software routines is the norm. Adapting these for secret-sharing would be difficult to say the least.
Sep
22
awarded  Yearling
Jul
25
comment Solve a system of non linear equations over GF
Sigh.... No, you cannot use the idea mentioned in my previous comment for square roots for other roots in GF$(2^m)$. The kinds of equations you are looking to solve seem to be closely related to Lagrange interpolation and thus should not need $n$-th roots (or square roots for that matter) in the solution process, but if you feel that they do, then to each his own.
Jul
25
comment Solve a system of non linear equations over GF
It seems that these questions will never converge... In a finite field GF$(2^m)$, every element has a square root (not true in GF$(p^m)$ for $p > 2$) and the square root can be found easily. One way that always works is to square the element $m-1$ times: $$\sqrt{x_0} = \underbrace{((\cdots ((x)^2)^2\cdots)^2)^2} ~~~ m-1 ~\text{squarings}$$ More efficient methods use the properties of the irreducible polynomial used to define the field, or log tables, etc.
Jul
24
revised Is the polynomial reconstruction problem really “intractable”?
inserted two missing words
Jul
24
answered Is the polynomial reconstruction problem really “intractable”?
Jul
20
answered Solve a system of non linear equations over GF
Jul
20
revised Why does Shamir's Secret Sharing Scheme need a finite field?
deleted 4 characters in body
Jul
20
comment Why does Shamir's Secret Sharing Scheme need a finite field?
$$\begin{align}x+y+z&=1\\2x+2y+2z&=2\\3x+3y+3z&=3\end{align}$$ has multiple solutions but not a unique solution in any field; $$\begin{align}x+y+z&=0\\2x+2y+2z&=1\\3x+3y+3z&=1\end{align}$$ has no solutions in any field because the equations are inconsistent.
Jul
20
comment Why does Shamir's Secret Sharing Scheme need a finite field?
@Herc11 My comment was with regard to your question about 3 equations and 3 unknowns in general and not about the specific equations in your question 9294.
Jul
20
comment Why does Shamir's Secret Sharing Scheme need a finite field?
If the three equations have a unique solution in a field whether it is a prime field (integers modulo a prime $p$) or an extension field (what you seem to be referring to as "GF generated by ir. polynomials), then standard calculations will give the right answer. The choice of irreducible polynomial merely changes the names we give to elements of the extension field and so the answer might "look" different but it is still the same answer: all that has happened is that we are using a different basis to represent the answer.