4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are you doing $n$-out-of-$n$ secret sharing or $t$-out-of-$n$ with $t<n$? $\endgroup$ – mikeazo Jan 28 '16 at 13:26
  • $\begingroup$ @mikeazo As I want to give away all the shares, I'd say $n$-out-of-$n$ secret sharing. $\endgroup$ – user153465 Jan 28 '16 at 13:39
  • $\begingroup$ Is the permutation fixed or how is the permutation generated? $\endgroup$ – mikeazo Jan 28 '16 at 13:50
  • $\begingroup$ @mikeazo We assign a random index (in the matrix) to each share. In nutshell we are using a pseudorandom function whose key is secret and unknown to the adversary to generate a random index. The rest of indices are occupied with some dummy values. $\endgroup$ – user153465 Jan 28 '16 at 14:16
  • $\begingroup$ Does the adversary know the distribution of $\sigma$? $\endgroup$ – Dilip Sarwate Jan 29 '16 at 14:25
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ There is one problem here: the shares in Shamir secret sharing may not be uniformly random elements of the field. Thus, the adversary may distinguish them from dummy values. As I could not find any paper stating the shares are random elements of the field, also the shares are related to each other as the random coefficients remain the same for the shares. $\endgroup$ – user153465 Feb 1 '16 at 10:46
  • $\begingroup$ Well, but you could simply sample the dummy values from the same distribution. E.g., if we continue the Twitter + Shamir case you could simply produce shares for dummy Twitter messages. In general, you should be able to generate the same distribution by sharing messages that follow the same distribution as your real message. The only issue is that you end up with enormous storage requirements... $\endgroup$ – mephisto Feb 3 '16 at 14:33
  • $\begingroup$ Even without Shamir secret sharing, permute the characters of Twitter messages "Attack at dawn" "Attack at noon" "Retreat at noon" etc and hand them over to the adversary. $\endgroup$ – Dilip Sarwate Feb 3 '16 at 14:39
  • $\begingroup$ Just for your information: link.springer.com/chapter/10.1007/978-3-642-31540-4_12#page-1 $\endgroup$ – user153465 Feb 6 '16 at 13:10
  • $\begingroup$ In a paper client hides all $x_i$ values and gives only $f(x_i)$ values to a malicious server. The paper I cited shows that that scheme is insecure and can be attacked. However, I do not know whether the attack can be applied to the scheme I mentioned in the question. $\endgroup$ – user153465 Feb 6 '16 at 13:14

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.