I'm searching for a method/algorithm that is able to manage different encryption keys and guarantee that some subset of that keys is needed to perform the decryption (not all).

For example: $$D_{K1, K2}(E_{K1, K2, K3}(X)) = D_{K1, K3}(E_{K1, K2, K3}(X)) = D_{K1, K2, K3}(E_{K1, K2, K3}(X)) = X$$

A real-world like example is where I have a bank account shared with my life, and I needs to withdraw money given only one sign.

So, used $$K_i \ with \ i \in {1, 10}$$ to encrypt some message, I need only $k<10$ keys to decrypt my message.


Extending from my comment:

Yes it exists and is known as "threshold decryption". See Shamir's Secret Sharing. You may encrypt each share with with the respective preshared symmetric key for each party, or otherwise distribute the shares. Alternatively you may use asymmetric solutions instead which tend to have less ciphertext expansion than SSS at the cost of asymmetric operations.

For an example I'll use an online implementation of SSSS

The following example splits a secret message "my secret root password" into 5 components where any 3 may be used to recover the message.

% ssss-split -t 3 -n 5
Generating shares using a (3,5) scheme with dynamic security level.
Enter the secret, at most 128 ASCII characters: my secret root password
Using a 184 bit security level.

As demonstrated

% ssss-combine -t 3
Enter 3 shares separated by newlines:
Share [1/3]: 3-fa1c3a9c6df8af0779c36de6c33f6e36e989d0e0b91309
Share [2/3]: 5-4756974923c0dce0a55f4774d09ca7a4865f64f56a4ee0
Share [3/3]: 2-fbc74a03a50e14ab406c225afb5f45c40ae11976d2b665
Resulting secret: my secret root password

Instead of splitting the message, it is cleaner to split the key used to encrypt (and authenticate) the message. These key shares may then be encrypted using per-participant preshared keys or with public keys.

There are more threshold decryption options but they are more complicated. For more information these slides should be helpful. I must add that they reference trusted dealers, you may use verified dealers instead so they cannot cheat the protocol.


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.