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$?

  • 1
    $\begingroup$ 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. $\endgroup$ – poncho May 30 '14 at 14:05
  • $\begingroup$ Im 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 Im 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. $\endgroup$ – user13676 May 30 '14 at 14:09
  • $\begingroup$ So ... does this differ from homomorphic encryption? $\;$ $\endgroup$ – user991 May 30 '14 at 17:36
  • $\begingroup$ 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). $\endgroup$ – user13676 May 30 '14 at 17:39
  • $\begingroup$ My general feeling is that there is no way to make your idea secure without major modifications. $\endgroup$ – mikeazo May 30 '14 at 19:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.