Impact of a non-uniform distribution in a secret sharing scheme

Question

When it comes to the secret sharing schemes, it seems that the random numbers need to be drawn uniformly. Is there any difference between the random numbers from uniform distribution and the non-uniform distribution? Do different distributions affect the security of the scheme?

Answer 1

The distribution for random values is extremely important, and using a non-uniform distribution can certainly affect the security of the secret sharing scheme (or, really, any cryptographic operation). How a random number from a non-uniform distribution affects the security depends on the specific algorithm/scheme being used.

A non-uniform distribution always implies a bias so that some values are more likely than others. At a minimum this would help an attacker that knows the bias by helping them to optimize a search for the more likely values first. (e.g. If half the time the value comes up all zeros, I'll guess try that first.)

Depending on the underlying operations, the biases in the non-uniform distribution could also allow for specialized attacks on the underlying cryptographically hard problem that wouldn't apply in the general case. The biases might not lead to an practically exploitable, but would only undermine some proof of security. (However, holes in proofs that are "only theoretical" today often turn into practical attacks later.)

Answer 2

Just to add to the other answers, you may also want to take a look at leakage resistance secret sharing, for example this work. The idea is to study the following question:

What is leaked about the underlying secret when the adversary gets some leakage from the shares?

This turns out to be a very interesting question, and in some sense, changing the distribution can be seen as "leaking" information since some shares may become more likely than others.

Interestingly, in some cases, even a 1-bit leakage can completely break security. For example, if you use Shamir's secret sharing over $GF(2^n)$, then leaking the first bit of a large enough amount of shares will leak the first bit of the secret! So if you have a distribution that generates shares for which it is more likely that the first bit is, say, $1$, then you will know something about the secret.

Answer 3

You ask in a comment to the first answer: "If the random values are drawn from the uniform distribution while the original numbers have some distribution, e.g., normally distributed, will the original distribution not be leaked?"

Consider $GF(q)$ and let $X$ have an arbitrary distribution while $U$ has a uniform distribution. If you add randomness by means of an independent variable $U$, uniformity is preserved. This is because for any $a\in GF(q)$ $$ \mathbb{P}[X+U=a]=\sum_{b\in GF(q)} \mathbb{P}[X=a-b]\mathbb{P}[U=b] $$ $$= \frac{1}{q} \sum_{b\in GF(q)} \mathbb{P}[X=a-b]=\frac{1}{q}. $$

In $GF(p)= \mathbb{Z}_p$ the map $x\rightarrow ax$ is a permutation for $a\neq 0.$ So, in the Shamir setup, one can derive uniformity for monomials, and thus for polynomials by adding monomials using the result above, if the coefficients are chosen uniformly from $\mathbb{Z}_p^{\ast}$. Since the missing monomials (when $a=0$ is chosen) don't appear in the sum defining the polynomial, this is not a problem.