I'm looking for a solution to protect a message, such that both password1 (usually given to trusted person #1) and password2 (given to trusted person #2) are required to decrypt the message.

Thus, person #1 alone or person #2 alone can't decrypt the message.

A solution seems to be given by Shamir's Secret Sharing (using finite field arithmetic).

Question: how is the following simple solution weaker than Shamir's solution, and which are the benefits of Shamir's solution over this:

ciphertext = encrypt(encrypt(plaintext, password1), password2)

(where encrypt is any traditional symmetric encryption solution)?

Example use-case (off-topic but just as an example): plaintext is your digital "will" (containing helpful passwords that you would like to transmit to your loved ones after your death), password1 is kept by your attorney/notary, password2 is given to your life partner.

PS: this simple and obvious technique is discussed here and here.

  • 1
    $\begingroup$ How do you do 2-of-3? $\endgroup$ – Squeamish Ossifrage Oct 24 '19 at 20:50
  • $\begingroup$ (Note that secret-sharing is almost never what you really want in practice—for example, using it for a signing key means that whenever you reconstitute the signing key from the shares, there's one party with unilateral signing power. Generally you really want threshold cryptosystems where no party ever has that kind of unilateral power.) $\endgroup$ – Squeamish Ossifrage Oct 24 '19 at 20:51
  • $\begingroup$ Not sure to grasp the idea of your comments @SqueamishOssifrage, could you elaborate in an answer? PS: I edited to add a use case at the end. $\endgroup$ – Basj Oct 24 '19 at 20:54
  • $\begingroup$ For n-of-n your scheme works fine (all n of the n parties must participate to recover the secret), and similarly you can get 1-of-n (any 1 of the n parties, which you can get by concatenating rather than nesting encryption), but Shamir's scheme works for k-of-n where 1 < k < n. $\endgroup$ – Squeamish Ossifrage Oct 24 '19 at 20:56
  • $\begingroup$ Thanks, I guess this is the answer (if you would like to post it for future reference of other users) @SqueamishOssifrage. Can you describe how 1-of-n is possible with concatenation? $\endgroup$ – Basj Oct 24 '19 at 20:59

You've described an $n$-of-$n$ threshold encryption scheme by nesting: there are $n$ shares of a secret key, and it takes all $n$ of them (in the right order, so I hope you labeled them) to recover the plaintext. Similarly, there's a simple $1$-of-$n$ threshold encryption scheme by concatenation, which is what, e.g., OpenPGP uses for multiple-recipient messages.

What neither of these handles is $k$-of-$n$ for $1 < k < n$; e.g., $2$-of-$3$, where you want to ensure that either

  • you and your solicitor, or
  • you and your mistress, or
  • your mistress and your solicitor,

can collaborate to recover the secret, but none of them individually can (and definitely not your husband).

Obviously, it is possible to compose nesting and concatenation to have the same effect—do $1$-of-$3$ where each share is a $2$-of-$2$ threshold system itself, for instance, like the list above—but there is a bit of a combinatorial explosion of overhead this way especially when $k \approx n/2$ so that the overhead grows as the central binomial coefficients.

In contrast, Shamir's secret-sharing scheme costs only $\log_2 n + b$ bits per share of a $b$-bit secret no matter what the threshold $k$ is, for a total of $n \log_2 n + n b$ bits of overhead, or $k \log_2 n + k b$ bits of storage to recover the secret.

Note that secret-sharing schemes are almost never what you want in practice (except, perhaps, for revealing deathbed secrets).

For example, if you jointly control a bank account, and you want to ensure any transfers out of the bank account are authorized by two of three signatories, it is a bad system to use a single signing key split up with a secret-sharing scheme—if you do that, then every time you sign a check, you necessarily reconstitute the single signing key, and whoever owns the computer on which you reconstituted it now has unilateral power to sign checks.

It is generally better to use threshold signatures, the simplest system of which is just the concatenation of signatures by distinct authorized parties.

  • $\begingroup$ Thanks for this great answer. Just to be sure to understand 1-of-n threshold encryption scheme by concatenation, is this ciphertext=encrypt(plain, password1) + encrypt(plain, password2) + ... + encrypt(plain, passwordn) (where + is concat)? so that anyone having a password can decrypt it? $\endgroup$ – Basj Oct 24 '19 at 22:01
  • $\begingroup$ @Basj That's correct. $\endgroup$ – Squeamish Ossifrage Oct 24 '19 at 22:01

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.