# Shamir Secret Sharing - P not prime

I was wondering what will happen if I use the Shamir Secret Sharing scheme with $P$ not being a prime, let's say it is $255$. An adversary which holds $k'$ shares ($k'<$ threshold $k$ ) can attack the scheme and find the secret $S$? If he can attack the scheme, how the attack works?

• Shamir secret sharing is only possible when operating in a finite field. So, for moduli that are not a power of a prime ($p^k$), the calculations won't work. Jul 7, 2017 at 14:16
• Also, if you do use a power of a prime $p^k$ with $k>1$, you don't do the computation modulo $p^k$, instead, you need to use an extension field; addition and multiplication work differently than just computing things $\bmod p^k$ Jul 7, 2017 at 14:41

There are two problems that arise when you attempt to use a composite $P$:

The first is that the attacker can gain some information about the shared secret; he can't reconstruct the entire secret, however the goal of Shamir Secret Sharing is that the attacker obtains no information. For a simple case, consider a threshold $k=2$ case where the attacker has the single share $(3, 0)$. That is, the attacker knows that the polynomial is a linear equation $ax + s$, with $s$ being the shared secret, and with $3a + s = 0 \bmod 255$. What the attacker can immediately deduce is that, whatever the shared secret is, it must be a multiple of 3 (because $3a + s$ is a multiple of $3$); this happens because $3$ is a divisor of $255$.

The second issue is that the legitimate reconstructors, with $k$ different shares, cannot necessarily uniquely reconstruct the secret. For an example, consider that case $k=2$ and we have the two shares $(1, 0)$ and $(4, 0)$. In this case, we know we have a linear equation with $1a + s = 0 \bmod 255$ and $4a + s = 0 \bmod 255$.

Unfortunately, there are 3 possible equations that fit this criteria:

$$0 x + 0$$

$$85 x + 170$$

$$170 x + 85$$

It is easy to see that plugging in 0, 4 into each of these equations yields the values implied by the shares.

Hence, while we know that the secret is one of $\{0, 85, 170\}$, we have no idea which one it is.

Just to clarify, Shamir secret-sharing is possible over any finite ring $$R$$, even non-commutative ones, as long as the ring contains a set of evaluation points $$\alpha_0,\ldots,\alpha_n\in R$$ ($$n$$ here is the number of intended parties, or shares) with each non-zero difference $$\alpha_i - \alpha_j$$ being invertible.

If $$R$$ is the ring of integers modulo a power of a prime $$p^k$$, then it can be shown that there exists a set of evaluation points with $$p$$ elements. Hence, as long as $$p\geq n+1$$, you can use Shamir secret-sharing directly.

If $$p\leq n$$ (e.g. if $$p=2$$), then you can use the so-called Galois ring extensions, which are similar to Galois field extensions, to obtain enough evaluation points.

Details can be found in this paper.

• Ah, yes, it's obvious when you think about it... Dec 8, 2021 at 14:48