More Detailed Justification for Recommending Large Primes for SSSS

[IamfromSpace]

In practice, p should be reasonably large. Breaking S into multiple parts introduces complexity and opportunities for malicious actors. Also, in some verifiable secret sharing schemes, a large p is needed to prevent discrete log attacks.

This advice seems to go against a very common field choice of GF(2^8). As such, I’m personally curious to better understand the argument against (if that is the argument), and generally I think a deeper explanation (or link or reference to one) would be a good idea!

[opal-escent]

Hi Nathan-- thanks for the questions and feedback!

There are a few implementations over GF(2^8) out there, and they certainly work for basic secret splitting, but they come with the drawback of not being compatible with verifiable secret sharing (VSS) techniques.

That incompatibility is a deal-breaker in many adversarial circumstances. For instance, some threshold signature schemes use Shamir's technique to jointly hold a signing key, and rely on Feldman VSS during the key generation and resharing processes to ensure that parties are behaving honestly. Because some share information is provided by untrusted parties, the ability to identify dishonest behavior is critical to security.

There are contexts where verifiability isn't as much of an issue, of course. Somebody splitting a BTC private key so they can keep a secure, distributed "backup" of it will probably not be worried about the bank overwriting the contents of the USB key in a safe deposit box, for instance. In non-adversarial cases, GF(2^8) works great.

But zkdocs is about zero knowledge settings, where we don't have as much room for trusted parties. So we recommend using "suitably large" primes to help ensure compatibility with verifiability schemes. That probably could have been made clearer.

I think you're right that our discussion could be more complete. Also, there could be more detailed discussion of how system parameters should be selected.

We'll work to make sure the next refresh of zkdocs includes a more detailed discussion of this topic. Thanks for bringing it to our attention!

Thanks, Opal

[IamfromSpace]

This is super helpful, thanks!

At some point in my research I think I misunderstood and thought that verification generally wasn’t known to be possible, rather than just applying to SSSS as is. This totally clicks as to how VSS works, how it would be useful, and how it implies large primes. And it makes sense then the distinction of environments where you may be able to get away without.

I was interested (mostly academically) to find a verifiable scheme that worked post-quantum computing, and as I understand it, VSS depends on the discrete logarithm problem. This eventually led me to Adept Secret Sharing (ADSS), which seems to generally have some nice properties over VSS, and seems to only use quantum resistant primitives. Purely coincidentally, it’s GF(256). I was curious if a comparison had been made or considered.

Also, feel free to close this issue (or use it to track any future revisions), this answered my question, and was much appreciated!