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. So far, the best attack of previous method for a subgroup of Z(N)* had a complexity about O(root p'). 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(root p'/2) rather than O(root 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.