Paper 2014/825
Towards Optimal Bounds for Implicit Factorization Problem
Yao Lu, Liqiang Peng, 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.
Metadata
- Available format(s)
- -- withdrawn --
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- LatticesImplicit Factorization ProblemCoppersmith's methodLLL algorithmSmall root
- Contact author(s)
- lywhhit @ gmail com
- History
- 2015-05-25: withdrawn
- 2014-10-12: received
- See all versions
- Short URL
- https://ia.cr/2014/825
- License
-
CC BY