When all shares of a secret are given to adversary as a permuted matrix

Question

Suppose we have a secret $\sigma$.

The secret comes from a universe in which the elements are not necessarily distributed uniformly.

We split $\sigma$ into $n$ shares $[\sigma_1,...,\sigma_n]$ (using Shamir secret sharing). So the order of shares matters.

We know given all the shares in the right order one can recover the secret.

We permute all the shares in a matrix (see below). We fill the empty indices with some dummy (or random) values $d_{i,j}$ \begin{matrix} d_{11} & \sigma_{n} & \sigma_{2} & \dots & d_{1,m} \\ d_{21} & d_{22} & \sigma_{i} & \dots & d_{2,m} \\ \dots \\ d_{k,1} & d_{k,2} & \sigma_{3} & \dots & \sigma_{1} \end{matrix}

---

Question: Given the matrix, can the adversary recover the secret with a high (or non-negligible) probability?

I emphasis that $\sigma$ may have very greater distribution probability than the other elements of the universe and the adversary knows that probability.

Please note that the values $k$ (number of rows) and $m$ (number of columns) are independent of the number of shares $n$ and we can increase them if it's needed.

====================================

Edit: Newly added:

Suppose we have two permuted matrices one contains shares of secret value $\sigma$ and dummy values; and the other matrix contains shares of $\gamma$ and random values. We give away the two permuted matrices and one-to-one mapping of the elements to the adversary. The mapping tells the adversary that value in $i,j$ position in one matrix corresponds to value $k,l$ position in the other matrix.

Question: Would the adversary learn the secret values $\sigma$ and $\gamma$ with a non-negligible probability.

Answer 1

Let us first consider the problem without involving Shamir secret-sharing at all. Suppose that $n = 140$ and that the secret $\sigma$ is a 140-byte Twitter message. The space is thus restricted considerably, from all possible $256$ byte values to the printable characters permitted to be used in Twitter messages, and the distribution in this restricted space might also be nonuniform because of etaion shrdlu. The secret sharing is trivial: each of the $140$ shareholders gets one byte, and the secret is recovered only when all $140$ shares are assembled in the correct order.

An adversary is given a large number composite number $N$ of bytes (arranged into a matrix if the OP so desires, though I am not sure why this imposes some structure on the data) including the $140$ shares and the other $N-140$ entries filled in "at random". Can the adversary recover the secret with large enough probability to be a significant concern? Well, the answer might depend on the assumptions. If the $N-140$ "other" bytes are "filled in at random" from the space of all $256$ bytes, then the adversary can simply discard all bytes that are not part of the Twitter character set. This reduces the workspace from $N$ bytes to approximately $p(N-n) + n$ bytes where $p$ is the ratio of the size of the Twitter character set (80? 96?) to $256$. It might also be possible to make some educated guesses and apply the known distribution of the message set to discount excessive numbers of letters x or q or z etc or punctuation marks, etc. So, with no secret sharing, the extraneous bytes that the adversary is handed should be chosen not at at random, but roughly with the probabilities with which they occur in Twitter messages.

Many of these concerns go away when Shamir secret sharing is used. Now, the shares are of the same length as the secret, but share $\sigma_i$ is the value of the polynomial $$S(x) = \sigma + a_1 x + a_2x^2 + \cdots + a_{n-1}x^{n-1}$$ (where the $a_i$ are randomly chosen nonzero entries) at some nonzero element $\alpha_i$ in the field. Even if $\sigma$ is restricted, these random polynomial coefficients ensure that the shares $$S(\alpha_1), ~S(\alpha_2),~ S(\alpha_3),~ \ldots,~ S(\alpha_n)$$ essentially look like random choices. In fact, some of them might even equal $0$. Thus, if we fill the $N-n$ other entries with other random choices (allowing $0$ as a choice too), the $N$ possible shares handed to the adversary will conceal the true shares very well. I don't have a formal proof for this, but I doubt that any statistical test can distinguish the actual shares from the fakes with even a minuscule chance of success. Of course, one must ensure that $N$ is much larger than $n$ so that there are enough . I venture to suggest that $N = O(n^2)$ will be found to be more than adequate, and perhaps even something like $10n$ might work well enough.