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?
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$– mikeazoCommented 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$– ponchoCommented Jul 7, 2017 at 14:41
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ Ah, yes, it's obvious when you think about it... $\endgroup$– ponchoCommented Dec 8, 2021 at 14:48