Cryptography and Availability

Question

Here is a question in cryptography which is probably naive, and a reference request.

Suppose I have 3 matrices $I1$, $I2$, and $I3$ (same size) that I want to combine to to create a matrix $R$ (or 3 different matrices $R1$, $R2$, and $R3$) such that it would not be possible to recover any of $I1$, $I2$, and $I3$ from $R$ (or $R1$, $R2$, and $R3$). Also, I would be able to reconstruct $R$ (or $R1$, $R2$, and $R3$) if I am missing one of the $I$s.

Think of it this way. In secret sharing we create different shares from one secret where we can reconstruct the secret with combination of some of the shares whereas here is somehow the reverse of secret sharing. I have 3 secrets and want to find a combination(s) such that with any two of the Is, the combination can be reconstructed.

Thanks.

Answer 1

Let me drop the matrix context, but rephrase your problem like this: You want to encrpyt a clear text $R$ into three (or more) cypher texts $I_1, I_2, I_3$ (probably handed to three persons) such that

• it is "impossible" to find $R$ with only one of the cyphers
• it is possible to find $R$ by combining any two of the cyphers.

This is like a safe that can be opened only if the majority of a comittee approves.

First suggestion: The three persons create RSA key pairs, keeping their own secret keys $S_i$ and publishing the public keys $P_i$. Let $C_1=P_2(P_3(R))$, $C_2=P_1(P_3(R))$, $C_3=P_1(P_2(R))$. Then let $C$ be the concatenation of $C_1$, $C_2$, $C_3$. This can be published. The role of the $I_i$ is played by $C$ together with $S_i$.

I am afraid that this method is not as hard to attack as it seems. Note that the first key holder can obtain $P_3(R)$ and $P_2(P_3(R))$. Having a clear text and the corresponding capher text might help in finding $S_2$!

Alternative: Again, each user creates a key pair. Hand $P_2(R)$ to the first person, $P_3(R)$ to the second, and $P_1(R)$ to the third person. Nobody has the correct key for the cypher in his hand, but when two people cooperate, one has the key for the cypher held by the othre.

Disadvantage: If persons 1 and 2 cooperate, the second can use $S_2$ do decode 1's $P_2(R)$. However, he may lie to preson 1 about the content.

Yet another Alternative: Create a single temporary RSA key pair (private key $S$, public key $P$), compute and publish $C=P(R)$. Assume $S$ consists of $3n$ bits. For $i=1, 2, 3$, let $I_i$ be $S$ with all bits at positions $\equiv i\pmod 3$ replaced with $0$'s. (After that, $S$ must be "trustworthily discarded"). Then any two can reconstruct $S$ (and hence $R$ by decoding $C$) by ORing their partial secrets.

Even if we assume that brute force is the only attack against RSA, the key size in my second alternative must be three times as big as is usually considered sufficient (because a single partial secret owner knows already $2n$ of the $3n$ bits).

Answer 2

Even though your task is literally impossible, let me try again: We start with 3 secrets $I_1, I_2, I_3$, which I consider as sequences of $n$ bits each. And I consider them "random" - if this is not the case beforehand, replace the $I_i$ with some random-looking hash of it in what follows.

For $1\le i\le n$ set the bit in position $i$ of $R$ according to the "majority" of the $I_i$, that is if at least two of the $I_i$ have a 1 there, set it 1, otherwise set it 0. If we only have $I_1$ and $I_2$, say, then they agree at approximately half the bits. Therefore we know half the bits of $R$ and can only guess the other bits. As expected (see Henning's comment), we cannot reproduce $R$ exactly. But: If $R$ has been used before e.g. as a crypto-key, then guessing $R$ by brute force has come down from $2^n$ possibilities to only $\sqrt{2^n}$. This may just be good enough to be feasible.

Remark: If I have $R$ alone, I also have $\frac34$ of the bits of $I_1$, say, correct (that is: expected $\frac34$ of $I_1$ XOR $R$ consists of zeroes). However, here I do not know which bits are correct. Even having $R, I_2$ and $I_3$, I have not full knowledge of $I_1$: I know $\frac12$ of them exactly, the same situation as with the incomplete $R$ above.