'Does the size of the prime number in Shamir's Secret Sharing affect the security of the sharding?
I've been working on an implementation of Shamir's Secret Sharing, and was wondering if the prime number selected will impact on the security. This is mainly because I've seen some implementations on GitHub using 257, and some implementations using large Mersenne primes like 2^53 - 1.
Appreciate input on this, thanks!
Solution 1:[1]
From a mathematical perspective the secrecy is perfect: as long as you are at least one share below threshold every possible secret is equally probable, and you know nothing.
The main reason for choosing bigger primes is to share bigger secrets. You need to turn the secret into a number smaller than the prime, and if your secret were a big computer file, that would obviously fail. If the shared secret is the key to some symmetric cypher encrypting the actual message, then you loose the perfect secrecy and the risk of breaking the cypher correlates strongly with the size of the key.
For practical purposes also note that if you pick the prime after the secret, your choice might reveal something about the size of the secret. And also note that with a small prime a single share might get compromised with just a glance, while for a large prime a share wold contain too much detail for a human to memorize quickly.
Of course you can always split one big secret into many smaller secrets, and encode each of them independently using a small prime. So in that way the size of the prime doesn't matter so much, but the specific choice might still dictate how easily you can do the splitting of the secret and the representation of the shares.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 |