Assume that $n = 2r+1$. There are $n$ elements $a_1,a_2,\ldots,a_n$ from a finite field $\mathcal{F}$, and $n$ parties. Each party knows the values of at least $r+1$ elements out of those $n$ elements. In addition, every value $a_j$ is known by at least $r+1$ different parties. Also note that every party only knows which $r+1$ values it has, but it doesn't know which $t+1$ values other parties have.

Every party gets to broadcast one message to all the parties (I assume all the broadcasts happen exactly at the same time). (That message may also contains a bit set representing the set of field elements the party knows.) How can the parties communicate effectively so that after the communication phase, every party knows all the values $a_1, a_2, \ldots , a_n$?

Basic ideas about the question:

  • Example for naive solution: Every party broadcasts all the $r+1$ elements it knows together with a bit-set representing which elements it sent. Then we have a total network complexity of $n(n(r+1 + (n/8))) = O(n^3)$. (Here $n/8$ represents the size of the bit-set).

  • Regarding the optimal solution: Using Information considerations, we get that every party needs to know $r$ more field values. Hence at least $rn = O(n^2)$ network complexity is needed to solve this problem.

My attempts at finding a solution:

  • Let $A$ be a matrix of size $(cn)\times n$ (Where $c$ is some small constant. You may assume that $c=2$ if it makes reading easier). I define Proper Erasure as changing some of the entries of the matrix $A$ to $0$, where only $r$ entries in any raw may be changed, and only $cr$ entries in any column may be changed.

  • I define such a matrix $A$ to be a Strong Matrix if for any Proper Erasure, the resulting matrix $\tilde{A}$ has $rank(\tilde{A}) = n$.

  • Given a strong matrix $A$, we could let any party $P_j$ create a vector $v_j = (b_1,b_2,\ldots,b_n)$, where $b_i := a_i$ if $a_i$ is known to $P_j$, and $b_i := 0$ otherwise. Then $P_j$ will broadcast the $cj-c+1,cj-c,\ldots,cj$ elements of the vector $Av_j$, together with a bit-set representing the field elements it knows. Given the properties of $A$, every party will be able to reconstruct all the values. Also note that here every party broadcasts a message of size of one element (together with the bit set). The complexity will still be of $O(n^3)$ because of the bit-set, though it will take much less network complexity.

I'm stuck here:

  • How can one find a so called Strong Matrix? I have looked for something like this in the literature and found something called rigid matrix, or matrix rigidity. It deals with the question of the ability to change entries of a matrix to any values while keeping the rank of the matrix higher than some value. In this sense it is a stronger requirement than being a Strong Matrix. I have seen some results, though most of them are asymptotic, and I really want to have a real matrix that works.

  • I thought that the Vandermonde matrix might work as a strong matrix, though I haven't yet managed to prove it, or disprove it.

  • At the same time, I would like to get a matrix which is also easily solvable. I might be wanting too many things at this point, but it will be useful to actually be able to reconstruct all the field elements in something better than $O(n^3)$.

I will appreciate any idea about solving this, even if not related to my attempts.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.