The Attack of the RSA Subgroup Assumption.

In TCC 2005, Groth proposed the cryptographic usefulness of a small subgroup G of Z*_N of hidden order. Sofar, the best attack of previous method for a subgroup of Z*_N had a complexity about O(√p'/2). In this paper, we propose the interval and the double walks method to speed up the computation of the semi-smooth RSA subgroup problem. Our new algorithm reduces the complexity to O(√p'/2) rather than O(√p')- Besides the theoretical analysis, we also compare the performances of our new algorithm with the previous algorithm in experiments, and the efficiency of our new algorithm is approach to 50% faster than the previous. [ABSTRACT FROM AUTHOR]