Math Is Fun Forum

Aydin

Member

Registered: 2014-05-26

Posts: 31

Re: To reconstruct a Polynomial with only the knowledge of Y`s

I`m wondering if we can add some unknowns to a system polynomials to make it hard to solve it? I have the following systems:

F1(x1)=s+a1x1 , F1(x2)=s+a1x2
,F2(x1)=s'+a2x1 , F2(x2)=s'+a2x2 ,F3(x1)=s'+a3x1 , F3(x2)=s'+a3x2 ,F4(x1)=s'+a4x1 , F4(x2)=s'+a4x2

Unkowns:a1,x1,x2,a2,a3,a4,s,s'

If we have the vectors A=[F1(x1),F2(x1),F3(x1),F4(x1)] and
B=[F1(x2),F2(x2),F3(x2),F4(x2)] each of this vector is a share of the vector E=[1 0 0 0] using Shamir secret sharing scheme.

Now if someone multiple each of A or B by a 4x4 vector called C, he would obtain two vectors R1 and R2. Now with the help of Lagrange interpolation he can pick an entry from R1 and the other(with the same index) from R2 to recover a row of matrix C whose position is set 1 in E (e.g. in our case he would recover the first row since first entry in E is set 1). Since these 8 equations has 8 unknowns whoever possesses all F(x) can figure out what the value of S (or the other unknowns) is.

One party generates the F(x) and gives away F(x) values to whoever has matrix C.

** My question is how to add more unknowns to these equations, to prevent this data leakage happen but still be able to recover s (or the row of matrix C).

Regards

Last edited by Aydin (2014-05-30 00:05:17)

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: To reconstruct a Polynomial with only the knowledge of Y`s

How about increasing the order of the equations?

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Aydin

Member

Registered: 2014-05-26

Posts: 31

Re: To reconstruct a Polynomial with only the knowledge of Y`s

The number of equations eventually exceeds the number of unknowns, again. So it allows to get some more rows than before, but the same problem would appear again.
I need to correct my mistake that , it is multiplied by 4X4 matrix.

Last edited by Aydin (2014-05-30 00:10:39)

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: To reconstruct a Polynomial with only the knowledge of Y`s

How about a small example so I can see what is going on?

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Aydin

Member

Registered: 2014-05-26

Posts: 31

Re: To reconstruct a Polynomial with only the knowledge of Y`s

Assume that in above equations (e.g.F1(x1),...), we have 8 equations and 8 unknowns: a1,x1,x2,a2,a3,a4,s,s'. So whoever has all equations and its Y`s (or F1(x1),..F4(x2)) can recover all unknowns including S and S', since  there is 8 unknowns and 8 equations. If I can increase my equations' unknowns I would be able to prevent anybody recover unknowns. However I need to pass all equation on to untrusted party to multiply it by a 4x4 matrix. So two vectors are passed on him   A, and B (as explained in the question). I recieve the result which is two vector again and reconstruct the constant term ( that is my secret multiply by the first row of the matrix C).

I explained all to say that I cannot do any arbitrary modification to these polynomials to increase the number of unknowns. I need to be able to reconstruct the row on matrix C  that is multiplied by these A and B by using Lagrange interpolation.     Hope it help.

Last edited by Aydin (2014-05-30 00:46:56)

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: To reconstruct a Polynomial with only the knowledge of Y`s

What do the 4 x 4 matrices look like?

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Aydin

Member

Registered: 2014-05-26

Posts: 31

Re: To reconstruct a Polynomial with only the knowledge of Y`s

It is only a matrix of a database. Assume that each entry is a word and a row of the matrix is a block of this database.

Agnishom

Real Member

From: Riemann Sphere

Registered: 2011-01-29

Posts: 24,974

Website

Re: To reconstruct a Polynomial with only the knowledge of Y`s

Hi Aydin;

What is your favorite color?

---

'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: To reconstruct a Polynomial with only the knowledge of Y`s

It is only a matrix of a database. Assume that each entry is a word and a row of the matrix is a block of this database.

I need to know what the matrix multiplication is doing to the equations.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.