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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.