I would like to encrypt some data and create 5 keys. These keys are stored in different places. If I want to decrypt the data I just need 3 of these 5 keys.

Is there a way to do this?

  • 3
    $\begingroup$ See secret sharing $\endgroup$ – kelalaka Nov 29 '19 at 12:16
  • $\begingroup$ ...and the secret-sharing tag on this site. $\endgroup$ – Ilmari Karonen Nov 29 '19 at 15:35
  • 1
    $\begingroup$ FYI, there is an intrinsic limitation to secret-sharing: if you ever want to use the secret then you have to assemble the shares in one place, and whoever assembles the shares to recover the secret then has unilateral power to do whatever the secret enables them to do. If, for example, the secret is a signing key that lets you sign an authorization to (say) transfer your money somewhere, then you may be better off using a threshold signature scheme instead of secret-sharing so that it takes joint participation of the signers but there is never a single secret assembled in one place. $\endgroup$ – Squeamish Ossifrage Nov 29 '19 at 16:42
  • $\begingroup$ @SqueamishOssifrage: Indeed. For the OP's task as described, however, it seems perfectly suited. $\endgroup$ – Ilmari Karonen Nov 29 '19 at 16:57

Yes, there is. And it generalizes easily to requiring any $k$ out of $n$ keys, not just 3 out of 5:

  1. Generate a random key for some symmetric encryption scheme (say, AES-SIV).

  2. Encrypt your data with that random key.

  3. Use a threshold secret sharing scheme such as Shamir's secret sharing to split the random key into $n$ shares, such that any $k$ of them are needed to reconstruct the key.

You can use those $n$ shares directly as the $n$ "keys" to be stored in different places. However, if you'd instead prefer to use $n$ pre-existing keys, you'll need one more step:

  1. Encrypt each share with one of the $n$ keys (using whatever encryption scheme you prefer, either symmetric or asymmetric) and store the encrypted shares alongside the encrypted data from step 2.

To decrypt the data, do the same in reverse: first decrypt at least $k$ of the shares (if needed), then reconstruct the random key from those shares, and finally decrypt the data using the random key.

Shamir's secret sharing is unconditionally secure, so the whole scheme is as secure as the encryption schemes you use in steps 2 and (optionally) 4.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.