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.
1
-
$\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$– mikeazoSep 11, 2016 at 1:00
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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.
-
$\begingroup$ I think that last paragraph pretty much sums up the whole issue. :) $\endgroup$– ilkkachuSep 11, 2016 at 9:12
-
$\begingroup$ am curious how often the shares would end up slightly higher than 1 byte incase GF(257) is used ? $\endgroup$– sashankSep 12, 2016 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$– ponchoSep 12, 2016 at 3:21