For millions of secrets and tens of people holding those secrets, there's a much more space-efficient solution. There's an added benefit that hiding each secre

For millions of secrets and tens of people holding those secrets, there's a much more space-efficient solution. There's an added benefit that hiding each secret is plain vanilla RSA encryption. Victor Shoup discovered a relatively straight forward way to take an RSA private key and apply Shamir secret sharing in a way that commutes with RSA public key operations. Just like Shamir secret sharing, each of the N shares of the secret is a point on a random polynomial on a finite ring (in this case, the set of quadratic residues modulo the key's public exponent). Each of the N secret holders, using their secret share, can generate a public share. Any T of the N public shares can be used to invert the RSA public key operation. Shoup's threshold RSA signature scheme (http://www.shoup.net/papers/thsig.pdf http://www.shoup.net/papers/thsig.pdf) when used for RSA encryption caries all of the caveats that using the raw RSA algorithm entails (use OAEP, etc.) I'm really surprised Shoup-Cramer encryption is more famous than Shoup's threshold RSA algorithm.