Re: Truncated multiplication (is it secure???)



On Mar 22, 9:47 pm, "Bill" <wherr...@xxxxxxxxxxxxxxxx> wrote:
This gives the matrix

| 1 0 0 |
| 0 N/M 0 |
| sh*N/M^2 -midA*N/M N^2/M^2 |

Now (idA, N/M, (idA*sh-midA*M)*N/M^2) is a linear combination of the
column vectors of this matrix.

I followed you til here, and then you lost me... Would you please
mind showing me the matrix used to transform the matrix that way? I
mean there should be a way to add or multiply the rows of the original
matrix to get that row, right?

Let Mat1 be

|1 0 0|
|0 1 0|
|sh -midA*M N|

and Mat2 be

|1 0 0|
|0 N/M 0|
|0 0 N/M^2|

then computing Mat2*Mat1 gives

| 1 0 0 |
| 0 N/M 0 |
| sh*N/M^2 -midA*N/M N^2/M^2 |

A vector v is a linear combination of columns of Mat1 if there exists
a column vector w such that
v = Mat1*w. This implies that Mat2*Mat1*w = Mat2*v is a linear
combination of Mat2*Mat1.
For the column vector v= (idA , 1, idA*sh-midA*M) we get
Mat2*v= (idA, N/M, (idA*sh-midA*M)*N/M^2).

Also, here is a Pari script that I used to solve the example given
earlier.


\\ Implementation of integer mod operation
\\ (It proabably already exists, but I couldn't find this function.)
imod(m,n) = m - floor(m/n)*n

\\ Example from sci.crypt
sh = 31356540235810673346618362866804034368776251178676;
idA = 4466022725645872080780142446;
idB = 3223756751453228576175422353;
M = 10^11;
N = 10^67;

\\ Computation of MidA and MidB
MidA = floor(imod(sh*idA,N)/M);
MidB = floor(imod(sh*idB,N)/M);
print("MidA = ", MidA);
print("MidB = ", MidB);
print("");

\\ Given MidA solve for idA
mat = [1,0,0; 0,1,0; sh, -MidA*M, N];
mul = matdiagonal([1, N/M, N/(M^2)]);
t = qflll(mul*mat,1);
red = mat*t;
print("Reduced basis for idA", red);
print("");

\\ Given MidB solve for idB
mat = [1,0,0; 0,1,0; sh, -MidB*M, N];
mul = matdiagonal([1, N/M, N/(M^2)]);
t = qflll(mul*mat,1);
red = mat*t;
print("Reduced basis for idB", red);
print("");

.