Paper 2023/1562
Generalized Implicit Factorization Problem
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_1q_1$ and $N_2=p_2q_2$, where $p_1$ and $p_2$ 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 $p_1$ and $p_2$ 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 $any$ 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 ProblemLatticeLLL algorithmCoppersmith'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},
note = {\url{https://eprint.iacr.org/2023/1562}},
url = {https://eprint.iacr.org/2023/1562}
}
