7
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – mikeazo
    Jul 7, 2017 at 14:16
  • 3
    $\begingroup$ 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$ $\endgroup$
    – poncho
    Jul 7, 2017 at 14:41

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Ah, yes, it's obvious when you think about it... $\endgroup$
    – poncho
    Dec 8, 2021 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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