2008 Reports : Cryptology ePrint Archive Forum

Discussion forum for Cryptology ePrint Archive reports posted in 2008.
Please put the report number in the subject.

about 2008/296

Posted by: **zhaoyaodong** (IP Logged)

Date: 31 July 2008 00:08

The authors studied the small private-key attacks of LSBS-RSA in the paper. They suspected there are some errors in the Zhao-Qi attack reported in [25].

But the error they pointed in the paper does not exist in the Zhao-Qi attack. In fact, in the Zhao-Qi attack, that they ignored the factor "a" will not lead to error.

Because in [25], they assumed that the publice key e was an odd number, so a^{-1} existed. Let u_{i} be a positive number that satisfied a^{-i}*a-u_{i}*e^m=1. They use the coeffient vectors of the ploynomial a^(-i)f(xX,yY,zZ)-u_{i}*e^m*I/(a^t) to build the lattice in order to eliminate the factor "a" in the terms in the diagonal of the matrix, where I is the term in the diagonal of the matrix of the polynomial f(xX, yY, zZ). It is obvious that a^(-i)f(x_0,y_0,z_0)-u_{i}*e^m*I/(a^t) mod e^m =0, where (x_0, y_0, z_0) is the small root they want to get. So using LLL-algorithm to the Zhao-Qi's lattice, the polynomials they get h1(x, y, z), h2(x, y, z) will still satisfy h1(x_0, y_0, z_0)= h2(x_0, y_0, z_0)=0 mod e^m. This technique decreases the det(L) which leads to a larger bound of the attack. I think this technique is very simple, so it is ignored in Zhao's work.

But the error they pointed in the paper does not exist in the Zhao-Qi attack. In fact, in the Zhao-Qi attack, that they ignored the factor "a" will not lead to error.

Because in [25], they assumed that the publice key e was an odd number, so a^{-1} existed. Let u_{i} be a positive number that satisfied a^{-i}*a-u_{i}*e^m=1. They use the coeffient vectors of the ploynomial a^(-i)f(xX,yY,zZ)-u_{i}*e^m*I/(a^t) to build the lattice in order to eliminate the factor "a" in the terms in the diagonal of the matrix, where I is the term in the diagonal of the matrix of the polynomial f(xX, yY, zZ). It is obvious that a^(-i)f(x_0,y_0,z_0)-u_{i}*e^m*I/(a^t) mod e^m =0, where (x_0, y_0, z_0) is the small root they want to get. So using LLL-algorithm to the Zhao-Qi's lattice, the polynomials they get h1(x, y, z), h2(x, y, z) will still satisfy h1(x_0, y_0, z_0)= h2(x_0, y_0, z_0)=0 mod e^m. This technique decreases the det(L) which leads to a larger bound of the attack. I think this technique is very simple, so it is ignored in Zhao's work.

Please log in for posting a message. Only registered users may post in this forum.