Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I'm trying to come up with a new way to do oblivious transfer that is faster and requires less computation than existing methods. The basis of my method is shamir secret sharing. Below is an example of how the system would work.

Let $C$ be a matrix. The user would like to query the DB for a particular row of $C$ without revealing which row to the server. I can do shamir secret sharing to form a vector indicating which row of the DB to query for as follows.

I have the following systems:

$$F_1(x_1)=s+a_1x_1\\ F_2(x_1)=s′+a_2x_1\\ F_3(x_1)=s′+a_3x_1\\ F_4(x_1)=s′+a_4x_1\\ F_1(x_2)=s+a_1x_2\\ F_2(x_2)=s′+a_2x_2\\ F_3(x_2)=s′+a_3x_2\\ F_4(x_2)=s′+a_4x_2$$

Unknowns are: $a_1,x_1,x_2,a_2,a_3,a_4,s,s′$

If we have the vectors…

$\vec{A} =[F_1(x_1),F_2(x_1),F_3(x_1),F_4(x_1)]$ and $\vec{B} =[F_1(x_2),F_2(x_2),F_3(x_2),F_4(x_2)]$

each vector is a share of the vector $\vec{E} =[1,0,0,0]$ using Shamir secret sharing scheme. So $E$ indicates which row of the DB that the user wants (in this case, the first row).

We can send the vectors $\vec{A}$ and $\vec{B}$ to the server who computes $R_1=\vec{A}C$ and $R_2=\vec{B}C$, and returns $R_1$ and $R_2$ to the user. The user can use Lagrangian interpolation to recover the row of $C$ that was indicated by $\vec{E}$.

There is a problem with this method, however. The system of equations has 8 equations and 8 unknowns. So, by sending $\vec{A}$ and $\vec{B}$ to the server, the server would be able to reconstruct $\vec{E}$.

How can I add more unknowns to these equations, to prevent this data leakage from happening while still being able to recover the desired row of matrix $C$?

share|improve this question
1  
Might I ask what's the point of making it "harder to solve"? The entire point of Secret Sharing is that the problem is impossible to solve if you don't have enough shares, and that is it easy if you do have enough. –  poncho May 30 at 14:05
    
I`m gonna use it( as explained above) to multiply the secret by a matrix, so I should be able to recover the secret(which is the result of multiplication). Thus I`m only using this construction, but I don't want to allow anybody to reconstruct it. It is more to do with privacy concern than secret sharing. –  user13676 May 30 at 14:09
    
So ... does this differ from homomorphic encryption? $\;$ –  Ricky Demer May 30 at 17:36
    
Homomorphic encryption is not as efficient as this method. It doubles the computation cost at the server side(e.g. if we use Paillier encryption to encrypt the query). –  user13676 May 30 at 17:39
    
My general feeling is that there is no way to make your idea secure without major modifications. –  mikeazo May 30 at 19:35
show 7 more comments

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.