Cryptology ePrint Archive: Report 2014/825

Towards Optimal Bounds for Implicit Factorization Problem

Yao Lu and Liqiang Peng and Rui Zhang and Dongdai Lin

Abstract: We propose a new algorithm to solve the Implicit Factorization Problem, which was introduced by May and Ritzenhofen at PKC'09. In 2011, Sarkar and Maitra (IEEE TIT 57(6): 4002-4013, 2011) improved May and Ritzenhofen's results by making use of the technique for solving multivariate approximate common divisors problem. In this paper, based on the observation that the desired root of the equations that derived by Sarkar and Maitra contains large prime factors, which are already determined by some known integers, we develop new techniques to acquire better bounds. We show that our attack is the best among all known attacks, and give experimental results to verify the correctness. Additionally, for the first time, we can experimentally handle the implicit factorization for the case of balanced RSA moduli.

Category / Keywords: public-key cryptography / Lattices, Implicit Factorization Problem, Coppersmith's method, LLL algorithm, Small root

Date: received 10 Oct 2014, withdrawn 25 May 2015

Contact author: lywhhit at gmail com

Available format(s): (-- withdrawn --)

Version: 20150525:123441 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]