Use Shamir's Secret Sharing Scheme to split a key between a client, a server and multiple 3rd parties

glesage

3/25/24, 7:22 AM

I'm trying to design an encryption system for a new mobile app and am thinking of using Shamir's Secret Sharing Scheme in a way which I have not seen before. Does this seem possible or does it violate some mathematical concept I'm not understanding in SSS?

I want to split a key generated on the user's mobile device where:

n parts are necessary to rebuild it
n-1 parts are stored on the user's mobile device
1 part is sent to a server and is linked with user ID
n+x (where x is 0 or more) parts stored on n+x other users' mobile devices

Anytime the full key is needed on the device, the user needs to ask the server for an 1 extra key part that it stores.

If the user looses his phone or it is stolen, he is able to ask the n+x other mobile devices to agree to share their part to rebuild the key and decrypt

Does this make sense? The idea here is to prevent any one person from having 100% of the key, while allowing "backups" of the data of the user to be decrypted by other users/friends like facebook's trusted contact type thing.

Thanks!

152

1 + 0

security-definition

threshold-cryptography

Score:2

Crypto

fgrieu

3/25/24, 1:38 PM

Splitting a private key by Shamir secret sharing works fine. An equivalent method widely used in practice in HSMs is to have the full private key encrypted symmetrically under a relatively small symmetric key, itself shared by Shamir secret sharing; and the encrypted private key redundantly stored.

Among issues in the question (as per v5)

In normal use, there is a chicken-and-egg problem for the app authenticating to the server in order to obtain the 1 share the server holds (third bullet in the question). Authentication must be provided for that by another mean.
Any other user holding a share would be able to reconstruct the private key if they get hold on another user's lost mobile device and can extract it's data.
When the private key is split, in a Shamir $n$-out-of-$m$ system, we get to decide on $m$. If I read the question correctly, $m$ is $n+x+1$ and is the total number of users then involved (including the new one). What happens if the number of users grows is untold. With mere replication of the existing key shares, the expected numbers of random users that must agree to rebuilt the full key increases (per the same effect as in the coupon collector's problem). And if we don't replicate, it's to fear that the rebuild will fail after some time due to $x$ users leaving the system or loosing the backup shares they hold.
It's not told on what rational basis users holding backup key shares agree or not on a rebuild.

+ 1

glesage

3/25/24, 11:00 PM

Thank you for your answer! 1. Right, I was indeed planning on adding additional authentication prior to bullet 3 2. Right, I was planning on encrypting the shares on the user device with a key stored in HSMs 3. No actually the number of users with whom the key is split does not change unless the owner of the key decides to. However we do have the issue of the users that have parts of the key leaving the platform... I'll have to think about that

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Use Shamir's Secret Sharing Scheme to split a key between a client, a server and multiple 3rd parties

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.