1
$\begingroup$

I'm implementing Shamir's Secret Sharing Scheme, but I've hit a conceptual roadblock. In Shamir's paper "How To Share A Secret" he creates his shares an a finite field of order p, where p is some prime larger than both the secret and the number of shares. I understand why this needs to be done to ensure an even distribution of the shares. However, in nearly every implementation I've seen, GF(256) is used. I know that this is technically okay, since it is still GF(p^k), but why is this preferable to just using a prime field? In the prime field, only modular arithmetic is needed, but with GF(256), you end up writing a ton more code and it is much less intuitive.

$\endgroup$
  • $\begingroup$ GF(256) is perfect when operating on bytes. Addition is just XOR in that field. Multiplication shouldn't be too hard to implement. $\endgroup$ – mikeazo Sep 11 '16 at 1:00
6
$\begingroup$

I know that this is technically okay, since it is still GF(p^k), but why is this preferable to just using a prime field?

They have equivalent security; however the nice thing about $GF(2^8)$ is that everything ends up to be an integral number of byte. We could use (say) $GF(257)$, however when the shares will end up being slightly larger than 1 byte, and so if we encode a secret that's an random set of bytes, the shares end up using a bit more space.

If we used a trinary computer, we'd probably end using something like $GF(3^6)$, because that would be an even number of trits.

with GF(256), you end up writing a ton more code

Not that much; most computer languages support $GF(256)$ addition as a standard operator, and multiplication/division can be done with two tables, and a few lines of code.

Compare this to the logic required to do modular division.

As for "far less intuitive", well, that depends on your experience with finite fields; I find it perfectly intuitive.

$\endgroup$
  • $\begingroup$ I think that last paragraph pretty much sums up the whole issue. :) $\endgroup$ – ilkkachu Sep 11 '16 at 9:12
  • $\begingroup$ am curious how often the shares would end up slightly higher than 1 byte incase GF(257) is used ? $\endgroup$ – sashank Sep 12 '16 at 2:34
  • $\begingroup$ @sashank: if you used a fixed length encoding, they'd always be larger than 1 byte. If you used a variable length encoding, well, that'd depend on the encoding. $\endgroup$ – poncho Sep 12 '16 at 3:21

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.