Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
If your $I_1$, $I_2$ and $I_3$ can be arbitary and you want to be able to reconstruct $R$ using only two of them, then the only possibility is to let $R$ be constant, that is, independent of all three inputs. So that probably isn't what you mean -- but it is what you have written. It doesn't seem to have much to do with cryptography either. I would advise you to rewrite your question from scratch, being careful to give all details about what you need to be able to do and what you need to prevent others from doing. –  Henning Makholm Sep 5 '12 at 20:33
1  
I think, now I get it. You want an easily computable function $f:(I_1, I_2, I_3)\mapsto R$ such that inverses of the form $g_1:(R, I_2, I_3)\mapsto I_1$ etc. exist, but $(R,I_1)\mapsto I_2$ should not be feasible. I sthat correct? For, as Henning said, reconstructing $R$ from two shares alone makes no sense: If $R$ can be computed from $I_1, I_2$, then the $R$ belonging to $I_1, I_2, I_3$ must be the same as for $I_1, I_2, 0$ and by symmetry also the same as for $I_1, 0, 0$ and finally $0,0,0$. –  Hagen von Eitzen Sep 5 '12 at 21:24
    
@HagenV: Thank. I am looking for the function f as you described with the condition that R should not reveal anything about Is and their combinations and G(R,I2,I3)--> T or G(R,I1,I3)--> T or G(R,I1,I2)--> T and T is the parameter that I use in my computation as a key type of thing –  user39576 Sep 5 '12 at 21:32
add comment

2 Answers

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).

share|improve this answer
    
Thanks for your comments. However, I do not have R. I do have 3 Is but not R and wants to find R such that it is "impossible" to find R with only one of the cyphers and it is possible to find R by combining any two of the cyphers. –  user39576 Sep 5 '12 at 21:08
    
Then prepend my methods with another step: Create a random $R$ (and throw it away after the partial secret have been distributed). However, this still seems to differ from your requirement as I produce (and then distribiute) the partial secrets and you seem to want to start from what the users already have. Did I get that right? –  Hagen von Eitzen Sep 5 '12 at 21:13
    
Thanks. We do not have 3 users here. Actually we have 3 secrets I1, I2, and I3 and we want to create R out of these three that can be used in a computation. However, R is generated on the fly and it is not stored anywhere. However, if we have access to two of the Is, we should be able to reconstruct the R 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. –  user39576 Sep 5 '12 at 21:21
add comment

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.

share|improve this answer
    
+1 That's a quite heroic effort to make sense of the question. –  Henning Makholm Sep 5 '12 at 21:53
    
@HagenV: Thanks. With this solution I still can not reconstruct the R. –  user39576 Sep 5 '12 at 23:51
    
@Hennings: I also try again to clarify the question more. Let me give you an example of usage. Assume you need to create a matrix R that is used in a computation( let say you need to compute R*X where X is a variable matrix) however, R should not be changed in order to have the desired results. The requirement is that you are not allowed to store R but you are given 3 matrices( at beginning) that you can use to calculate R and later you might not have access to all of three to calculate R. Thus, you need to find a way that allows you to compute R by at least two of Is if you missed one of them –  user39576 Sep 5 '12 at 23:53
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.