3
$\begingroup$

I'm looking for a type of algorithm that could be used to encrypt text with a shared secret $S$. What I would like to have is the secret to be broken up in three pieces, where any combination of two pieces can be used to reconstruct shared key $S$ in order to decrypt the text.

Is there any mathematical or cryptographic scheme of approaching this? Physically breaking up shared secret $S$ is one approach but what about others?

Improve this question
$\endgroup$
  • $\begingroup$ There is an obvious lousy way which costs a factor of $n\choose k$ ciphertext expansion—in this case, $k = 2$, $n = 3$. Specifically, you can encrypt it independently three times using a 2-of-2 scheme where the ciphertext is $C_{ij} = P \oplus S_i \oplus S_j$ for each $i < j$. Here, of course, we can compute $S_i = \operatorname{AES}_{k_i}(0) \mathbin\Vert \operatorname{AES}_{k_i}(1) \mathbin\Vert \cdots$ for efficient storage of the secret. But that ciphertext storage cost is rather unsatisfying. (Also you should consider authentication.) $\endgroup$ – Squeamish Ossifrage Dec 17 '17 at 16:08
1
$\begingroup$

The common procedure for what's asked is to draw a random key $S$, use it to encipher the plaintext using a symmetric cipher such as AES-CTR, then split the key into so-called key shares per a threshold scheme, so that $k=2$ shares out of $n=3$ are required to reconstruct the key. A generic $(k,n)$ threshold scheme is Shamir Secret Sharing.

Here is a very simple $(2,3)$ threshold scheme: each bit $x$ of the key is splits into three shares values $a$, $b$, $c$. Share value $a$ is chosen uniformly at random among $\{0,1,2\}$, then the other two are determined as $b=(a+x)\bmod3$, $c=(b+x)\bmod3$ (where $\bmod3$ designates subtracting $3$ from the result if it is $3$ or more). For decoding, if any two share values among $a$, $b$, $c$ are equal, then the corresponding key bit $x$ was $0$; otherwise it was $1$. Demonstrably, a single share gives no clue about the key. See this question for schemes still workable by hand and giving a slightly more compact encoding.

As pointed in comment, this has the drawback that who/whatever draws, uses and/or splits $S$ could be dishonest, keep $S$, and decipher the plaintext.

Improve this answer
$\endgroup$
  • 3
    $\begingroup$ This doesn't really answer the question of how to do this without just splitting up the secret $S$. In particular, can we do it without granting one trusted party/computer unilateral access to the secret, so that decryption of the message always requires participation of two of the three parties? For n-of-n, it's easy, of course, but for k-of-n when k < n I don't have an easy answer before tea time. $\endgroup$ – Squeamish Ossifrage Dec 17 '17 at 15:57

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.