4
$\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$
  • 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 '17 at 14:16
  • 2
    $\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 '17 at 14:41
4
$\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$

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.