You are not logged in.
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.
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.
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.
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
So S,a,X1,and Y2 are unknown and F(X1) and F(X2) are public. In one of the conditions this theorem states that it may have infinite number of solutions.
F(x)= S+aX so F(X1)=S+aX1 and F(X2)=S+aX2;
We have under-determined system of equations where the number of equations is smaller than unknowns. Is that correct?
It was my mistake, this is the correct one:
http://www.vaxasoftware.com/doc_eduen/mat/throuche.pdf
I do appreciate for your effort again. I found this theorem:
Rouché–Capelli theorem:
file://staffhome.cis.strath.ac.uk/homes/system/Windows/Desktop/Secret%20sharing/throuche.pdf
Do you think that it is a proof of our problem?
Cool , so you`re hoping to filter out some solutions by considering mod. The question is are you gonna obtain a unique answer with high probability?
Cool , thanks.
Can you email me about the results, please.
Thanks. How can I formally prove that it is safe? (if it is)
Yes my friend, and as you know I`m not bothered to supply degree of poly and P , in my system but nothing else. And as you know if this linear equation cannot be cracked we can apply higher degree.
It is very important that this equation is safe, say, the constant value of it is safe.
OK, but in my post it is clear beneath the "cool" there is a p value(on the second line), must be some problem with comment transmission.
Is sent the p value
p=123457
Cool,
p=123457
y1=316
y2=637
degree of the polynomial is one
Yes , P is a prime number.
Please consider the latest comment(the second comment that separates coefficients range from x values range)
Thank you again for your help.
As I explained later , the [0,p) applies to coefficients and (0,p) applies to X values. Moreover the X values should be distinct random number.
The coefficients could be zero but X values cannot be zero.
Yes the second one excluding 0
We pick a prime P which is large enough, then we use modular arithmetic instead of real arithmetic. So these coefficient and x values are chosen from this field [0,p). P is greater than the constant term and constant term and the degree of polynomial.
Regards
The coefficients are uniformly random chosen from Fp (field)
The x values are distinct values randomly chosen from same field.
all operation are modulo arithmetic e.g. mod p, where p is a prime, preferable large enough.