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("");

.

Relevant Pages

  • Re: corners ordening
    ... These corners are ordered on the basis of increasing x but I want to ... order them as I would find them walking on the edge of the object. ... y, and let be the postulated interior point. ... Then x2 and y2 would be column vectors with the desired ordering. ...
    (comp.soft-sys.matlab)
  • Re: Change of basis matrix
    ... is another possible basis for your space. ... assuming you are using column vectors and ... multiplying with the matrix on the left. ... vectors and transforming their coordinates. ...
    (sci.math)
  • ? decomposing B matrix in A matrixs e-vectors
    ... Given two square diagonalizable matrices A and B. ... Since column vectors of Va is a set of basis of N-dim space, ...
    (sci.math)