3

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?

e-sushi
  • 17,617
  • 12
  • 80
  • 223
Lawrence Kok
  • 131
  • 2
  • 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.) – Squeamish Ossifrage Dec 17 '17 at 16:08

1 Answers1

1

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.

fgrieu
  • 131,696
  • 12
  • 284
  • 553
  • 3
    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. – Squeamish Ossifrage Dec 17 '17 at 15:57