Shamir's Secret Sharing Scheme uses arithmetic in a finite field of prime order. In a secret image sharing scheme, what are the advantages of Galois field $\mathrm{GF}(p^m)$ over finite field $ F_p$?

  • $\begingroup$ Welcome to crypto.SE. Exactly how is the question's "secret image sharing scheme" different from a "secret sharing scheme"? Perhaps equivalently, what does "image" mean here? Is that its meaning in math/crypto, or does it stand for data representing a graphic? In the later case, consider hybrid encryption. $\endgroup$ – fgrieu Jun 13 '20 at 15:22

In a secret image sharing scheme, what are the advantages of Galois field $\mathrm{GF}(p^m)$ over finite field $ F_p$?

Well, Shamir Secret Sharing works over any finite field $GF(p^m)$, where $p$ is any prime, and $m$ is any integer $m \ge 1$ (N.B. the finite field $GF(p)$ (with $m=1$) is another name for $F_p$). Any selection of $p$ and $m$ is perfectly secure (assuming we select the polynomial randomly; this is a practical concern, but doesn't really depend on $p$ and $m$), with the only provisos is that the number of shares we can distribute is limited to $p^m-1$, and the value of the shared secret $s$ is in the range $[0, p^m)$.

So, any $p^m$ that is sufficiently large will work and meets the security goals; we then turn to practical considerations.

One strong practical consideration is the size of the shares. Each share is a value in the range $[0, p^m)$, for $p=2$, this can be conveniently expressed as $m$ bits; for $p>2$, this is a bit larger. This is not a huge difference; however it is generally viewed the only other practical difference, which is the familiarity we might have with math in $F_p$.

Here is one slightly contrived example to high-light the difference: suppose that we want to share a secret, and we have decided to split up the secret into bytes, and share each byte separately (if each polynomial is selected independently, this is fine). And, we do not have any need to generate more than 255 shares. In this scenario, we have two obvious options; we could use $GF(257)$; that makes the math fairly easy; however because each share is a value between 0 and 256, it doesn't fit into a byte; hence the obvious way to encode shares would be twice as long as the original secret. The other option would be to use $GF(256)$; the math is less obvious (however, with log and antilog tables, it isn't that bad), and each share turns out to be exactly as long as the original secret.

  • $\begingroup$ Addition; the question mentions "image". A possible interpretation is that the aim is to share a picture file. Say it requires $b$ bytes of storage. One option is to directly make the image the shared secret, by working in $\mathrm{GF}(2^m)$ with $m=8\,b$. Another option is to share each byte individually by working in $\mathrm{GF}(2^8)$. Yet another option is to share a (say) 256-bit key by one of these methods, and use that key to encipher the image (e.g. per chacha-poly1305 or AES-GCM-SIV), with the ciphertext common to all shares. $\endgroup$ – fgrieu Jun 14 '20 at 8:36

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.