Secret sharing between a very large number of participants What can be a method for sharing a secret between a large number of participants?

With Shamir's Secret Sharing (k,n), n can be arbitrarily large, but increasing k increases the complexity of the keys generation.

Is there an algorithm that can realistically generate keys for value of k between 1,000 and 1,000,000?
Is there an algorithm that can realistically generate keys for value of k between 1,000 and 1,000,000?


How about Shamir's Secret Sharing method?

For $k = 1000000$, generating a share would take a million field operations (multiplications and addition); this can be done in a few milliseconds per core (depending somewhat on the field you pick; there are CPU friendly ones out there).  Obviously, for the shares to be usable, you'll need to generate at least a million of them; this could be done in circa an hour on a laptop; that doesn't sound unrealistic to me.

If taking an hour to generate a million key shares is too expensive, what are the performance requirements?

Combining $k$ shares to reconstruct the secret takes $O(k)$ field operations; this is obviously quite reasonable; actually loading the shares is going to be the bulk of the work.