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.

Suppose Alice would like to obtain the product of two $m\times m$ matrices i.e. $A$ and $B.$ Alice has $A,$ whereas Bob has $B.$

Since Alice does not want to reveal $A$ to Bob, she chooses a $m\times m$ random invertible matrix $R.$ She sends $RA$ to Bob over a secure channel.

Bob obtains $RA,$ and calculates $RAB,$ and sends it to Alice over a secure channel.

Alice obtains $AB$ by inverting $R$ i.e. $R^{-1}RAB$.

$R$ is only utilized once.

Any ideas on how to proceed with the security analysis of the above protocol?

Specifically is H(A|RA) = H(A) ?

share|improve this question
    
oops sorry about that. –  user996522 Mar 7 '12 at 13:04
    
Relevant: Check out this paper cs.bgu.ac.il/~kobbi/papers/oge_tcc_camera2.pdf and the forward/backward citations. There are existing works on secure multiparty computation, and secure function evaluations. –  user2468 Mar 7 '12 at 13:31
    
What is this supposed to achieve compared to Bob simply sending $B$ to Alice over the secure channel? –  Henning Makholm Mar 8 '12 at 0:13
    
Its a primitive that i need as i have an idea for securely solving a linear equation which depends on the security of this. –  user996522 Mar 8 '12 at 0:26
    
Crossposted to crypto.SE as crypto.stackexchange.com/questions/2023/… –  Ilmari Karonen Mar 8 '12 at 9:05

1 Answer 1

up vote 4 down vote accepted

If A can be any matrix, then this protocol is not secure. In particular, if RA=0, then Bob can be reasonably confident that A=0 (or at least that A is sparse).

If A is invertible (over a fixed finite field), then this protocol is information-theoretically secure. To see this, first note that, for any $A$, the ciphertext $RA$ is uniformly distributed. Furthermore, the value of $RA$ is independent of $A$. Therefore, for any prior $P$ over messages, we have $\Pr[A|RA] = \Pr[A \wedge RA] / \Pr[RA] = \Pr[A]\Pr[RA] / \Pr[RA] = \Pr[A]$.

share|improve this answer
    
Thank you for the insight, however i don't quite see how for any A, RA is uniformly distributed. Call A the plain-text and RA the cipher-text, and R the key. I don't quite see how the probability of each cipher-text occurring is the same as each key occurring. –  user996522 Mar 8 '12 at 0:28
    
@user996522: The key is that R is chosen uniformly at random. By analogy, consider picking a point in $[0,1)$. Let A be an arbitrary point in the interval, and let let R by a uniform random value in $[0,1)$. Then $A+R$ is uniformly random over the interval $[A, A+1)$, and so the fractional part is uniform over $[0,1)$. –  Jeremy Hurwitz Jul 3 '12 at 4:53

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.