Generalized Implicit Factorization Problem

Yansong Feng; Abderrahmane Nitaj; Yanbin Pan

Paper 2023/1562

Generalized Implicit Factorization Problem

Yansong Feng, Key Laboratory of Mathematics Mechanization, NCMIS, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China, School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing, China

Abderrahmane Nitaj, Normandie Univ, UNICAEN, CNRS, LMNO, 14000 Caen, France

Yanbin Pan, Key Laboratory of Mathematics Mechanization, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China, School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing, China

Abstract

The Implicit Factorization Problem (IFP) was first introduced by May and Ritzenhofen at PKC'09, which concerns the factorization of two RSA moduli $N_{1} = p_{1} q_{1}$ and $N_{2} = p_{2} q_{2}$ , where and share a certain consecutive number of least significant bits. Since its introduction, many different variants of IFP have been considered, such as the cases where and share most significant bits or middle bits at the same positions. In this paper, we consider a more generalized case of IFP, in which the shared consecutive bits can be located at positions in each prime, not necessarily required to be located at the same positions as before. We propose a lattice-based algorithm to solve this problem under specific conditions, and also provide some experimental results to verify our analysis.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Published elsewhere. Minor revision. Selected Areas in Cryptography (SAC) 2023
DOI: https://doi.org/10.1007/978-3-031-53368-6_18
Keywords: Implicit Factorization Problem Lattice LLL algorithm Coppersmith's algorithm
Contact author(s): ysfeng2023 @ 163 com
abderrahmane nitaj @ unicaen fr
panyanbin @ amss ac cn
History: 2024-03-04: revised; 2023-10-11: received; See all versions
Short URL: https://ia.cr/2023/1562
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1562,
      author = {Yansong Feng and Abderrahmane Nitaj and Yanbin Pan},
      title = {Generalized Implicit Factorization Problem},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1562},
      year = {2023},
      doi = {https://doi.org/10.1007/978-3-031-53368-6_18},
      url = {https://eprint.iacr.org/2023/1562}
}